Schröder–Bernstein theorem

In set theory, the Cantor-Bernstein-Schroeder theorem is the theorem that if there exist injective functions f : A → B and g : B&nbsp→ A between the sets A and B, then there exists a bijective function h : A → B. In terms of the cardinality of the two sets, this means that if |A| ≤ |B| and |B| ≤ |A|, then A and B have the same cardinality: |A| = |B|. This is obviously a very desirable feature of the ordering of cardinal numbers.

Here is a proof [due to Eilenberg?]:

Let

$C_{0}=A\setminus g[B]$,

and

$C_{n+1}=g[f[C_{n}]]\quad {\mbox{ for }}n\geq 0$

and

$C=\bigcup _{n=0}^{\infty }C_{n}.$

Then for x∈A let

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

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.

The theorem is also known as the Schroeder-Bernstein Theorem, but the trend is towards adding Cantor's name to properly credit him. Some also call it the Cantor-Bernstein Theorem.

See also

Ernst Schröder