Math Fun Facts!
hosted by the Harvey Mudd College Math Department created, authored and ©1999-2010 by Francis Su
Subscribe to our RSS feed   or follow us on Twitter.
Get a random Fun Fact!
or
No subject limitations
Search only in selected subjects
    Algebra
    Calculus or Analysis
    Combinatorics
    Geometry
    Number Theory
    Probability
    Topology
    Other subjects
  Select Difficulty  
Enter keywords 

  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
All rights reserved.

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

Cantor Diagonalization

Figure 1
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:
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.
4.37
 
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!