Cantor Diagonalization

Figure 1

We have seen in the Fun Fact How many Rationals? that the rational numbers are countable, meaning they have the same cardinality as the set of natural numbers.

So are all infinite sets countable?

Cantor shocked the world by showing that the real numbers are not countable... there are "more" of them than the integers! His proof was an ingenious use of a proof by contradiction. In fact, he could show that there exists infinities of many different "sizes"!

Presentation Suggestions:
If you have time show Cantor's diagonalization argument, which goes as follows. If the reals were countable, it can be put in 1-1 correspondence with the natural numbers, so we can list them in the order given by those natural numbers. Now use this list to construct a real number X that differs from every number in our list in at least one decimal place, by letting X differ from the N-th digit in the N-th decimal place. (A little care must be exercised to ensure that X does not contain an infinite string of 9's.) This gives a contradiction, because the list was supposed to contain all real numbers, including X. Therefore, hence a 1-1 correspondence of the reals with the natural numbers must not be possible.

The Math Behind the Fact:
The theory of countable and uncountable sets came as a big surprise to the mathematical community in the late 1800's.

By the way, a similar "diagonalization" argument can be used to show that any set S and the set of all S's subsets (called the power set of S) cannot be placed in one-to-one correspondence. The idea goes like this: if such a correspondence were possible, then every element A of S has a subset K(A) that corresponds to it. Now construct a new subset of S, call it J, such that an element A is in J if and only if A is NOT in K(A). This new set, by construction, can never be K(A) for any A, because it differs from every K(A) in the "A-th element". So K(A) must not run through the entire power set of A, hence the 1-1 correspondence asserted above must not be possible.

This proof shows that there are infinite sets of many different "sizes" by considering the natural numbers and its successive power sets! The "size" of a set is called is cardinality.

How to Cite this Page:
Su, Francis E., et al. "Cantor Diagonalization." Math Fun Facts. <http://www.math.hmc.edu/funfacts>.

References: A classic text on real analysis is Walter Rudin's Principles of Mathematical Analysis. Keywords:    how many real numbers, uncountable infinity, Cantor's diagonalization argument, Cantor's diagonal argument, diagonalization proof Subjects:    combinatorics Level:    Advanced Fun Fact suggested by:   Francis Su Suggestions? Use this form. 3.99 current rating Click to rate this Fun Fact...     *   Awesome! I totally dig it!     *   Fun enough to tell a friend!     *   Mildly interesting     *   Not really noteworthy and see the most popular Facts! Get the Math Fun Facts iPhone App!

Want another Math Fun Fact?

For more fun, tour the Mathematics Department at Harvey Mudd College!