Cantor’s diagonal argument

One of the starting points in Cantor’s development of set theoryMathworldPlanetmath was his discovery that there are different degrees of infinityMathworldPlanetmath. The rational numbersPlanetmathPlanetmathPlanetmath, for example, are countably infiniteMathworldPlanetmath; it is possible to enumerate all the rational numbers by means of an infiniteMathworldPlanetmath 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 bijectiveMathworldPlanetmathPlanetmath correspondence between them.

In essence, Cantor discovered two theorems: first, that the set of real numbers has the same cardinality as the power setMathworldPlanetmath 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 sequenceMathworldPlanetmath 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:




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


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