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"!
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
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.