Cantor-Bernstein-Schroeder Theorem, a Second Proof

The Cantor-Bernstein-Schroeder theorem states that if, for two sets A and B, there injections A → B and B → A then the two sets are of the same cardinality, meaning that there is an bijection A ↔ B.

The proof below is from a 1994 paper by Peter G. Doyle and John Horton Conway.

Proof

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 x ∈ A to its image f(x) ∈ B. Similarly, we visualize g as a collection of red directed arcs. If we put in both the blue and the red arcs, we get a directed graph where every vertex has one arc going out and at most one arc coming in.

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

71536163

a	→	b	→	a	→	b
↑						↓
b						a
↑						↓
a	←	...	...	...	←	b