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 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 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:
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.
|Title||Cantor’s diagonal argument|
|Date of creation||2013-03-22 12:22:03|
|Last modified on||2013-03-22 12:22:03|
|Last modified by||rmilson (146)|