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

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 B = 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.

	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:

α(z) = { f(z), for z in X, and z,    for z in 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.

(There may be even a simpler proof. Do have a look.)

Related material Read more...
	Set Theory
	Addition of Sets
	de Morgan's Laws
	Equivalence Relations
	Mutiplication of Sets
	Nested Subsets
	Russell's Paradox
	Subsets and Intersections
	The set of all subsets of a given set is bigger than the set itself

|Contact| |Front page| |Contents| |Up| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny