Cantor-Bernstein-Schroeder Theorem

The Cantor-Bernstein-Schroeder theorem underlies the theory of transfinite cardinals. In an infinite set there are subsets of the exactly same cardinality. But then there are also different transfinite cardinalities. So how does one compares infinite sets. Given two infinite sets A and B, assume there is a 1-1 correspondence between B and a subset of A. It is reasonable and viable to expect that |B| ≤ |A|. Similarly, it is reasonable to say that |B| < |A| provided it is not true that |A| ≤ |B|, which would hold if there was a 1-1 correspondence between A and a subset of B.

But what happens when there are 1-1 correspondences in both directions? This is the subject of the Cantor-Bernstein-Schroeder theorem:

Theorem

Let there be an injection f: A→B and another g: B→A. Then there is a bijection α A→B.

In other words, if |A| ≤ |B| and |B| ≤ |A|, then |A| = |B|.

The same basic idea of the proof may be presented in various ways. I shall follow the simplest one I found on the web. The proof relies on the following

Lemma

Let there be injection f: A→B from a set A into its subset B⊂A. Then there exists a bijection between A and B. I.e., |A| = |B|.

Proof of Lemma

Let Y = A - B and X = Y ∪ f(Y) ∪ f(f(Y)) ∪ f(f(f(Y))) ∪ ... To make notations more manageable, we'll write f ^k(t) meaning k applications of function f to t, a set or an element of a set. By f⁰ will denote the identity function: f ⁰(t) = t. I shall show that

1. All f ^k(Y), k = 0, 1, 2, ..., are disjoint,
2. f(X) = f(Y) ∪ f ²(Y) ∪ f ³(Y) ∪ ...,
3. A = X ∪ (A - X) and Y = f(X) ∪ (B - f(X)),
4. |X| = |f(X)| and A - X = B - f(X),
5. the above implies the existence of bijection between A and B.

First, Y∩B = Ø so that Y can't intersect any of f ^k(Y)⊂B. And since f is injection, S∩T = Ø implies f(S) ∩ f(T) = Ø. It follows that for any k and m, k > 0, f ^m(Y) ∩ f ^k+m = Ø.

Restricted to X, f is a bijection.

The sought bijection α on A is defined to be f on X and the identity on A - X:

Proof of Theorem

Let f: A→B and g: B→A be two injections. First of all g(B) ⊂ A and, since there is an injection from A to B and a bijection from B to g(B), there is an injection (the composition of the two) from A to g(B). We are in a position to apply Lemma which now implies the existence of a bijection between A and g(B). The composition of the latter and the inverse g^-1 of g is a bijection from A onto B.