CantorBernsteinSchroeder theorem
The CantorBernsteinSchroeder 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 11 correspondence between B and a subset of A. It is reasonable and viable to expect that
But what happens when there are 11 correspondences in both directions? This is the subject of the CantorBernsteinSchroeder 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
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.,
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.)
Contact Front page Contents Up Algebra
Copyright © 19962018 Alexander Bogomolny68549667