A resource for profoundly gifted middle school students, their parents, and teachers

Proof of Cantor-Bernstein Theorem

Cantor-Bernstein Theorem

We provide further clarifying remarks on the proof.

Examples of the construction of h

Let A = {positive integers}, B={positive even integers}. Let f(x) = 4x and let g(y)=y. As you can see, both mappings are very much into, not onto. It is clear that the mapping k: A ® B, given by k(x) = 2x is a bijection. But suppose you want to find another. You may want to verify that the set S in the proof, for this problem, is the set of integers that are of the form 4m(2n+1), where m,n=0,1,2,... and the bijection h sends x in S to 4x, and x outside S to x.

Say the sets A and B are both the real interval [0,1]. Draw the graph of y = (3x + 1) / 5 which is an injection from A to B. Draw likewise x = (4 - 3y) / 5 which is an injection from B to A. From the union of the two graphs, you can pick out a subset which is the graph of a bijection A to B.

These two graphs intersect at the point (1/2, 1/2). Construct a square with (1/2,1/2) as center and side lenths of 1 unit so that A = [0,1] is on the bottom and B = [0,1] is the vertical side on the left. In the picture you can see that f takes A injectively into a portion of B and g takes B injectively into a posrtion of A. To construct the bijection, we look for the set S.

Where is A\g(B) in the picture?
It is the set consisting of the two red line segments, one of them touching the left end of A, the other the right end of A.
Where is (g o f)(A\g(B))?
To get it, we apply f first to the two red segments at the ends of A. For instance, applying f to the left red segment give us the blue line segment on the lower end of the graph of f. Then we apply g to the blue segment. This gives us the red line segment on the left of the right-most red segment.
Repeating this on the right-most red segment would give us the red segment symmetrically located w.r.t. the last red segment we obtained. The union of the last two red segments obtained is (g o f)(A\g(B)). We now apply f to this union and then g to the result, and so on. Thus we see that S is the union of the red segments in A.

Where is h?
h acts like f on S. So take any red segment and project up to the graph of f. We show that projection on the graph of f in blue. h acts on A\S in a different way. So take a point x on A that is not on the red segments. The image of the point x under h is obtained by projecting up to the graph of g. The point of the graph of g thus reached gives you the point in B by projecting horizontally on to B. Then h(x)= g-1(x). The graph of h is now the union of the blue segments on the two graphs. Notice that all the blue segments are closed at one end and open at the other. This is because each red segment was so too. In fact, the (countably infinity of) missing points on the ends of the blue segments allowed the blue segments to be the graph of a function!

We used the same intervals for A and B. Now that we see the construction, we can change, say, B to another interval. Also, it is not necessary to define functions to be linear with opposite slopes. Moreover, it is not necessary for both or any to be linear functions, for the theorem applies to all injections!

This example is due to Larry Hammick [3] who wrote that it was motivated by Banach's Mapping Theorem [1]: given any sets X and Y and mappings (not necessarily injections) f:X-->Y and g:Y-->X, one can partition X into disjoint subsets X' and X" and partition Y into disjoint subsets Y' and Y" so that f[X'] = Y' and g[Y"] = X".

For a discussion of the history of the theorem, see [2].

-- GRT

[1] S. Banach, "Un theoreme sur les transformations biunivoques," Fund. Math. 6 (1924), 236-239, or Leo Mirsky, "Transversal Theory", Academic Press, 1971, Corollary 1.3.3.
[2] Banaschewski, B. and G.C.L. Brümmer, "Thoughts on the Cantor-Bernstein Theorem", Questions Mathematicae, Vol. 9(1986), pp 1-27
[3] Larry Hammick, Private communication to George R. Thomas and public communciation on the Usenet, 2005

Ü Back



Send suggestions to webmaster@mathpath.org
Copyright © 2001- MathPath
Last updated - March 20, 2005