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 compare 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
But what happens when there are 1-1 correspondences in both directions? This is the subject of the Cantor-Bernstein-Schroeder 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
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
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.,
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
- All f k(Y), k = 0, 1, 2, ..., are disjoint,
- f(X) = f(Y) ∪ f 2(Y) ∪ f 3(Y) ∪ ...,
- A = X ∪ (A - X) and B = f(X) ∪ (B - f(X)),
- |X| = |f(X)| and A - X = B - f(X),
- the above implies the existence of bijection between A and B.
First, Y∩B = Ø so that Y can't intersect any of
Restricted to X, f is a bijection.
|A - X||= [B ∪ Y] - [Y ∪ f(X)]|
|= B - f(X).|
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
(There may be even a simpler proof. Do have a look.)