hosted by the Harvey Mudd College Math Department created, authored and ©1999-2010 by Francis Su

The Math Fun Facts App!

List All : List Recent : List Popular
About Math Fun Facts / How to Use
Contributors / Fun Facts Home
© 1999-2010 by Francis Edward Su

From the Fun Fact files, here is a Fun Fact at the Advanced level:

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

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

References:

Keywords:    how many real numbers, uncountable infinity, Cantor's diagonalization argument, Cantor's diagonal argument, diagonalization proof
Subjects:    combinatorics
Fun Fact suggested by:   Francis Su
Suggestions? Use this form.
4.18
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!
New: get the MathFeed iPhone App!

Brings you news and views on math:
showcasing its power, beauty, and humanity

Want another Math Fun Fact?

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