Cantor-Bernstein-Schroeder theorem

In set theory, the Cantor-Bernstein-Schroeder Theorem is the theorem that for if there exist injective functions f : A → B and g : B → A between the sets A and B, then there exists a bijective function h : A → B. In effect, this means that if the cardinality of A is less than or equal to that of B, and the cardinality of B is less than or equal to that of A, then A and B have the same cardinality. This is obviously a very desirable feature of the ordering of cardinal numbers.

Here is a proof [due to Eilenberg?]:

Let

<math>C_0=A\setminus g[B]</math>,

and

<math>C_{n+1}=g[f[C_n]]\quad \mbox{ for }n\ge 1</math>

and

<math>C=\bigcup_{n=0}^\infty C_n.</math>

Then for x∈A let

<math> h(x)=\left\{ \begin{matrix} f(x) & \,\,\mbox{if }x\in C \\ g^{-1}(x) & \mbox{if }x\not\in C \end{matrix} \right. </math>

One can then check that h : A → B is the desired bijection.

An earlier proof by Cantor relied, in effect, on the Axiom of Choice by inferring the result as a corollary of the well-ordering theorem. The argument given above shows that the result can be proved without the Axiom of Choice.