Cantor’s diagonal argument

One of the starting points inCantor’s development of set theory was his discovery that there aredifferent degrees of infinity. The rational numbers, for example, arecountably infinite; it is possible to enumerate all the rationalnumbers by means of an infinite list. By contrast, the real numbersare uncountable. it is impossible to enumerate them by means of aninfinite list. These discoveries underlie the idea of cardinality,which is expressed by saying that two sets have the same cardinalityif there exists a bijective correspondence between them.

In essence, Cantor discovered two theorems: first, that the set ofreal numbers has the same cardinality as the power set of thenaturals; and second, that a set and its power set have a differentcardinality (see Cantor’s theorem). The proof of the second resultis based on the celebrated diagonalization argument.

Cantor showed that for every given infinite sequence of real numbers$x_1,x_2,x_3,\mathrm{\dots }$ it is possible to construct a real number $x$that is not on that list. Consequently, it is impossible to enumeratethe real numbers; they are uncountable. No generality is lost if wesuppose that all the numbers on the list are between $0$ and $1$.Certainly, if this subset of the real numbers in uncountable, then thefull set is uncountable as well.

Let us write our sequence as a table of decimal expansions:

where

$$x_n=0.d_{n1}{d}_{n2}{d}_{n3}{d}_{n4}\mathrm{\dots },$$

and the expansion avoids an infinite trailing string ofthe digit $9$.

For each $n=1,2,\mathrm{\dots }$ we choose a digit $c_n$ that is different from$d_{nn}$ and not equal to $9$, and consider the real number $x$ withdecimal expansion

$$0.c_1{c}_2{c}_3\mathrm{\dots }$$

By construction, this number $x$ is different from every member of thegiven sequence. After all, for every $n$, the number $x$ differs fromthe number $x_n$ in the $n^{\text{th}}$ decimaldigit.The claim is proven.