Cantor-Bernstein-Schroeder Theorem, a Second Proof
The proof below is from a 1994 paper by Peter G. Doyle and John Horton Conway.
We want to show that given injections f : A → B and g : B → A we can determine a one-to-one correspondence between A and B. We can and will assume that A and B are disjoint. Here's how it goes. We visualize the set A as a collection of blue dots, and the set B as a collection of red dots. We visualize the injection f as a collection of blue directed arcs connecting each element
Such a graph decomposes into a union of connected components, each of which is either a finite directed cycle, a doubly-infinite path, or a singly-infinite path. As you go along one of these paths or cycles, the vertices you encounter belong alternately to A and B. In the case of a cycle or a doubly-infinite path, the blue arcs define a one-to-one correspondence between the blue vertices of the component and the red vertices. In the case of a singly-infinite path, the blue edges will still determine a one-to-one correspondence between the blue and red vertices of the path if the path begins with a blue vertex, but not if the path begins with a red vertex. However in this latter case we can take the red edges instead. Thus we can pair up the vertices of A and B along each connected component, and the union of these correspondences determines a one-to-one correspondence between A and B.
A 2000 paper by B. Schweizer (Cantor, Schröder, and Bernstein in Orbit, Math Magazine, v 71, No, 4, October 200) offers essentially the same proof in, perhaps, a more formal format.
The four kinds of possible cycles - the connected components of A∪B - can be illustrated as follows (with a and b being generic elements of A and B:
- a → b → a → b → ...
- b → a → b → a → ...
- ... → a → b → a → b → ...
a → b → a → b ↑ ↓ b a ↑ ↓ a ← ... ... ... ← b
The required 1-1 onto mapping φ: A → B is defined as follows:
- If a belongs to a component of Type I, III, or IV, map it onto its immediate successor, i.e. let
φ(a) = f(a).
- If a belongs to a component of type II, map it onto its immediate predecessor, i.e., let
φ(a) = g-1(a).