Cantor-Bernstein-Schroeder theorem
In set theory, the Cantor-Bernstein-Schroeder theorem is the theorem that 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 terms of the cardinality of the two sets, this means that if |A| ≤ |B| and |B| ≤ |A|, then |A| = |B|. This is obviously a very desirable feature of the ordering of cardinal numbers.
Here is a proof [due to Eilenberg?]:
Let
- ,
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.