CantorBernsteinSchroeder Theorem, a Second Proof
The CantorBernsteinSchroeder theorem states that if, for two sets A and B, there injections
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 onetoone 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 doublyinfinite path, or a singlyinfinite 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 doublyinfinite path, the blue arcs define a onetoone correspondence between the blue vertices of the component and the red vertices. In the case of a singlyinfinite path, the blue edges will still determine a onetoone 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 onetoone 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 11 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).
Contact Front page Contents Up Algebra
Copyright © 19962018 Alexander Bogomolny