Cantor’s diagonal argument
One of the starting points in
Cantor’s development of set theory was his discovery that there are
different degrees of infinity
. The rational numbers
, for example, are
countably infinite
; it is possible to enumerate all the rational
numbers by means of an infinite
list. By contrast, the real numbers
are uncountable. it is impossible to enumerate them by means of an
infinite list. These discoveries underlie the idea of cardinality,
which is expressed by saying that two sets have the same cardinality
if there exists a bijective
correspondence between them.
In essence, Cantor discovered two theorems: first, that the set of
real numbers has the same cardinality as the power set of the
naturals; and second, that a set and its power set have a different
cardinality (see Cantor’s theorem). The proof of the second result
is based on the celebrated diagonalization argument.
Cantor showed that for every given infinite sequence of real numbers
x1,x2,x3,… it is possible to construct a real number x
that is not on that list. Consequently, it is impossible to enumerate
the real numbers; they are uncountable. No generality is lost if we
suppose that all the numbers on the list are between 0 and 1.
Certainly, if this subset of the real numbers in uncountable, then the
full set is uncountable as well.
Let us write our sequence as a table of decimal expansions:
0.d11d12d13d14…0.d21d22d23d24…0.d31d32d33d34…0.d41d42d43d44…⋮⋮⋮⋮⋮⋱ |
where
xn=0.dn1dn2dn3dn4…, |
and the expansion avoids an infinite trailing string of the digit 9.
For each n=1,2,… we choose a digit cn that is different from dnn and not equal to 9, and consider the real number x with decimal expansion
0.c1c2c3… |
By construction, this number x is different from every member of the given sequence. After all, for every n, the number x differs from the number xn in the nth decimal digit. The claim is proven.
Title | Cantor’s diagonal argument |
---|---|
Canonical name | CantorsDiagonalArgument |
Date of creation | 2013-03-22 12:22:03 |
Last modified on | 2013-03-22 12:22:03 |
Owner | rmilson (146) |
Last modified by | rmilson (146) |
Numerical id | 9 |
Author | rmilson (146) |
Entry type | Topic |
Classification | msc 03E10 |
Synonym | Cantor’s diagonalization |
Related topic | CantorsTheorem |