Cantor–Bernstein–Schroeder theorem

In set theory, the Schröder–Bernstein theorem (named after Felix Bernstein and Ernst Schröder, also known as Cantor–Bernstein theorem, or Cantor–Schröder–Bernstein after Georg Cantor who first published it without proof) states that, if there exist injective functions $f : A \to B$ and $g : B \to A$ between the sets $A$ and $B$ , then there exists a bijective function $h : A \to B$ . In terms of the cardinality of the two sets, this means that if $| A | \leq | B |$ and $| B | \leq | A |$ , then $| A | = | B |$ ; that is, $A$ and $B$ are equipollent. This is a useful feature in the ordering of cardinal numbers.

This theorem does not rely on the axiom of choice. However, its various proofs are non-constructive, as they depend on the law of excluded middle, and are therefore rejected by intuitionists.

The following proof is attributed to Julius König.

Assume without loss of generality that A and B are disjoint. For any a in A or b in B we can form a unique two-sided sequence of elements that are alternately in A and B, by repeatedly applying $f$ and $g$ to go right and $g^{-1}$ and $f^{-1}$ to go left (where defined).

...
Wikipedia