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
- ,
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.
