Cantor-Bernstein-Schroeder theorem
|
|
In set theory, the Cantor-Bernstein-Schroeder theorem, named after Georg Cantor, Felix Bernstein, and Ernst Schröder, states 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 useful feature of in 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 0<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>
If x is not in C, then x must be in g(B), so there is a unique element <math>g^{-1}(x)<math>, and h is well-defined. One can then check that h : A → B is the desired bijection.
Note that this definition of h is nonconstructive, in the sense that there exists no general method to decide in a finite number of steps whether, for any given sets A and B, and injections f and g, if an element x of A lies in C or not. For special sets and maps this might, of course, be possible.
Visualization
The definition of h can be visualized with the following diagram.
Needs translation from German image (http://de.wikipedia.org/wiki/Bild:Cantor-Bernstein.png).
Displayed are parts of the (disjoint) sets A and B together with parts of the mappings f and g. By interpreting the set A ∪ B, together with the two maps, as a directed graph, then this bipartite graph has several connected components.
These can be divided into four types: paths extending infinitely to both directions, finite cycles of even length, infinite paths starting in the set A, and infinite paths starting in the set B (the path passing through the element a in the diagram is infinitely long into both directions, so the diagram contains one path of every type). In general, it is not possible to decide in a finite number of steps, which type of path a given element of A or B belongs to.
The set C defined above contains, precisely, the elements of A which are part of an infinite path starting in A. The map h is then defined in such a way, that for every path, it yields a bijection of the elements of A onto the elements of B directly before or after it in the path. For the both-side infinite path, and for the finite cycles, we choose to map every element to its predecessor in the path.
Original proof
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 using the axiom of choice.
The theorem is also known as the Schroeder-Bernstein theorem, but the trend has been to add Cantor's name, thus properly crediting him for the original version. It is also called the Cantor-Bernstein theorem.
See also
fr:Théorème de Cantor-Bernstein he:משפט קנטור שרדר ברנשטיין ja:ベルンシュタインの定理 pl:Twierdzenie Cantora-Bernsteina