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


Cantor-Bernstein Therorem

Two sets A and B have the same cardinality if there is a 1-1 and onto mapping or correspondence from A to B. Often, it is easier to find a 1-1 mapping rather than one that is 1-1 and onto. The theorem says that, when looking for bijection between two sets A and B, it suffices to find a 1-1 mapping (that is not necessarily onto) from A to B and a 1-1 mapping (that is not necessarily onto) from B to A. The effort of finding the two 1-1 mappings - one from A to B and the other from B to A - is often far less than that of finding just one mapping that is both 1-1 and onto.

A mapping that is 1-1 (one-to-one) is also called an injection. A mapping that is onto is also called a surjection. Let us pause a bit on these two words: injection and surjection. In Latin, the verb jacere means "to throw." in + jacere = inicere = throw in. The past participle of inicere is injectus. Similary, the word surjection is derived by combining jacere with the Latin word sur, meaning "upon." A mapping that is both an injection and a surjection is called a bijection. When there is a bijection between sets A and B, the sets are said to be equinumerous (having the same cardinality) or equipollent or equivalent.

The Cantor-Bernstein Theorem
Let A and B be sets. If there is a 1-1 correspondence from A to B and a 1-1 corespondence from B to A, then there is a bijection between A and B.

The proof is given elsewhere on these pages.

The theorem is trivial for finite sets. For if A and B are finite sets, then a 1-1 correspondence from A to B would produce a unique partner in B for each element in A and so the cardinality of A is atmost that of B. Similarly the 1-1 correspondence from B to A means the cardinality of B is at most that of A. The two inequalites together imply that A and B have the same cardinality and so each 1-1 correspondence is also onto and so they are both bijections. The reason we point out the obvious here is that this result also holds for correspondences that are only onto in the finite case. That is, if A and B are finite sets and if there is correspondence from A onto B and also a correspondence from B onto A, then there exists a 1-1 and onto correspondence from A to B (and hence from B to A). The surprising thing is that this "seems" to hold also for infinite sets - the result is called the Dual of the Cantor-Bernstein Theorem.

Here, we illustrate the use of the Cantor-Bernstein Theorem by showing an important and much-used bijection in mathematics. That is, the set of all positive real numbers is bijective with the set of all real numbers just from -1 to +1, including -1 and +1. The latter set is often denoted as [-1,1] and is called the CLOSED set of real numbers from -1 to +1.

Illustration of the S-B Theorem
Consider the correspondence f:[-1,1]-->R+, with f(x) = 2+x. Notice that this correspondence is 1-1 (why?)and takes [-1,1] to [1,3]. But there are elements in R+ that are outside [1,3] and so this correspondence is not onto. Now consider a correspondence, call it g, from R+ to [-1,1]. That is g: R+ --> [-1,1], with g(x) = 1/(1+x). This is a 1-1 correspondence (why?) that takes R+ to the positive real numbers that are less than 1. The latter set is contained in [-1,1]. Since [-1,1] contains also other numbers than the positive reals less than 1, g is not onto. Now, according to the Schroder-Bernstein Theorem, there exists a 1-1 onto correspondence between [-1,1] and R+. So these sets have the same cardinality.

I remember a student of mine in a Real Analysis class volubly expressing amazement at the equivalence of these two sets. So I drew on the board the popular pictorial illustration shown below.

The red lines represent a segment of length 2 from -1 to +1. Each point P on the red line has an image P' on the real line.

You would object that this establishes the equivalence of R, not R+, with [-1,1]. If you want that you could first establish the equivalence of [-1,1] with, say, [1,5] and then use the red line on the right in the picture to show the equivalence of [1,5] and R+. Here is the picture that shows the equivalence of any two closed intervals.

Here, each point P in an interval of length a has a corresponding point P' in an interval of length b.

Bernstein, F. "Untersuchungen aus der Mengenlehre." Ph.D. thesis. Göttingen, Germany, 1901
Bernstein, F. "Untersuchungen aus der Mengenlehre." Math. Ann. 61, 117-155, 1905
Cantor, E. "Ueber zwei Definitionen der Endlichkeit und G. Cantor'sche Sätze." Nova Acta Academiae Caesareae Leopoldino-Carolinae (Halle a.d. Saale) 71, 303-362, 1898
Cantor, E. "Die selbständige Definition der Mächtigkeiten 0, 1, 2, 3 und die explicite Gleichzahligkeitsbedingung." Nova Acta Academiae Caesareae Leopoldino-Carolinae (Halle a.d. Saale) 71, 365-376, 1898




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