Cantor–Bernstein–Schroeder theorem

From Wikipedia, the free encyclopedia

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 in the ordering of cardinal numbers.

1 A proof
2 Another proof
3 Visualization
4 Original proof
5 References

[edit] A proof

Here is a proof:

Let

$C_0=A\setminus g[B],\!$

and

$C_{n+1}=g[f[C_n]]\quad \mbox{ for }n\ge 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.$

If x is not in C, then x must be in g[B], so there is a unique element $g - 1 (x)$ , 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, for any given sets A and B and injections f and g, whether an element x of A does not lie in C. For special sets and maps this might, of course, be possible.

[edit] Another proof

Below follows an alternate proof, attributed to Julius König.

Assume without loss of generality that A and B are disjoint. For any a in A or b in B we can form a unique two-sided sequence of elements that are alternatively in A and B, by repeatedly applying $f$ and $g$ to go right and $g - 1$ and $f - 1$ to go left (where defined).

$\cdots \rightarrow f^{-1}(g^{-1}(a)) \rightarrow g^{-1}(a) \rightarrow a \rightarrow f(a) \rightarrow g(f(a)) \rightarrow \cdots$

For any particular a, this sequence may terminate to the left or not, at a point where $f - 1$ or $g - 1$ is not defined.

Call such a sequence (and all its elements) an A-stopper, if it stops at an element of A, or a B-stopper if it stops at an element of B. Otherwise, call it doubly-infinite if all the elements are distinct or cyclic if it repeats.

By the fact that $f$ and $g$ are injective functions, each a in A and b in B is in exactly one such sequence to within identity, (as if an element occurs in two sequences, all elements to the left and to the right must be the same in both, by definition).

By the above observation, the sequences form a partition of the whole of the disjoint union of A and B, hence it suffices to produce a bijection between the elements of A and B in each of the sequences separately.

For an A-stopper, the function $f$ is a bijection between its elements in A and its elements in B.

For a B-stopper, the function $g$ is a bijection between its elements in B and its elements in A.

For a doubly infinite sequence or a cyclic sequence, either $f$ or $g$ will do.

[edit] Visualization

The definition of h can be visualized with the following diagram.

Displayed are parts of the (disjoint) sets A and B together with parts of the mappings f and g. If the set A ∪ B, together with the two maps, is interpreted 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 infinite in 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 that maps each element of A in the path to an element of B directly before or after it in the path. For the path that is infinite in both directions, and for the finite cycles, we choose to map every element to its predecessor in the path.

[edit] 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 crediting him for the original version. It is also called the Cantor-Bernstein theorem.