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|; A and B are said to be "equipollent". This is obviously a very useful feature in the ordering of cardinal numbers.

1 Proof
2 Visualization
3 Another proof
4 Original proof
5 See also
6 References

[edit] Proof

Idea of the proof: Redefine f in certain points to make it surjective. At first, redefine it on the image of g for it to be the inverse function of g. However, this might destroy injectivity, so correct this problem iteratively, by making the amount of points redefined smaller, up to a minimum possible, shifting the problem "to infinity" and therefore out of sight. More precisely, this means to leave f unchanged initially on C₀ := A \ g[B]. However, then every element of f[C₀] has two preimages, one under f and one under g^–1. Therefore, leave f unchanged on the union of C₀ and C₁ := g[f[C₀]]. However, then every element of f[C₁] has two preimages, correct this by leaving f unchanged on the union of C₀, C₁, and C₂ := g[f[C₁]] and so on. Leaving f unchanged on the countable union C of C₀ and all these C_n+1 = g[f[C_n]] solves the problem, because g[f[C]] is a subset of C and no additional union is necessary.

Proof: Define

$C_0=A\setminus g[B],\qquad C_{n+1}=g[f[C_n]]\quad \mbox{ for all }n\ge 0,$

and

$C=\bigcup_{n=0}^\infty C_n.$

Then, for every a ∈ A define

$h(a)= \begin{cases} f(a) & \mbox{if }a\in C, \\ g^{-1}(a) & \mbox{if }a\notin C. \end{cases}$

If a is not in C, then, in particular, a is not in C₀. Hence a ∈ g[B] by the definition of C₀. Since g is injective, its preimage g^–1(a) is therefore well defined.

It remains to check the following properties of the map h : A → B to verify that it is the desired bijection:

Surjectivity: Consider any b ∈ B. If b ∈ f[C], then there is an a ∈ C with b = f(a). Hence b = h(a) by the definition of h. If b is not in f[C], define a = g(b). By definition of C₀, this a cannot be in C₀. Since f[C_n] is a subset of f[C], it follows that b is not in any f[C_n], hence a = g(b) is not in any C_n+1 = g[f[C_n]] by the recursive definition of these sets. Therefore, a is not in C. Then b = g^–1(a) = h(a) by the definition of h.

Injectivity: Since f is injective on A, which comprises C, and g^–1 is injective on g[B], which comprises the complement of C, it suffices to show that the assumption f(c) = g^–1(a) for c ∈ C and a ∈ A \ C leads to a contradiction (this means the original problem, the lack of injectivity mentioned in the idea of the proof above, is solved by the clever definition of h). Since c ∈ C, there exists an integer n ≥ 0 such that c ∈ C_n. Hence g(f(c)) is in C_n+1 and therefore in C, too. However, g(f(c)) = g(g^–1(a)) = a is not in C — contradiction.

Note that the above 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 a of A does not lie in C. For special sets and maps this might, of course, be possible.

[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] 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] 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.