|
|
|
|
Cantor's diagonal argument
|
(Topic)
|
|
|
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
 it is possible to construct a real number  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  . 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:
where
and the expansion avoids an infinite trailing string of the digit  .
For each
 we choose a digit  that is different from  and not equal to  , and consider the real number  with decimal expansion
By construction, this number  is different from every member of the given sequence. After all, for every  , the number  differs from the number  in the
 decimal digit. The claim is proven.
|
"Cantor's diagonal argument" is owned by rmilson. [ full author list (2) | owner history (1) ]
|
|
(view preamble)
Cross-references: digit, string, decimal expansions, subset, sequence, argument, Cantor's theorem, power set, bijective, cardinality, uncountable, real numbers, infinite, enumerate, countably infinite, rational numbers, infinity, degrees, set theory, development, points
There are 10 references to this entry.
This is version 6 of Cantor's diagonal argument, born on 2002-02-18, modified 2003-01-09.
Object id is 2109, canonical name is CantorsDiagonalArgument.
Accessed 26582 times total.
Classification:
| AMS MSC: | 03E10 (Mathematical logic and foundations :: Set theory :: Ordinal and cardinal numbers) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
