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 $x_{1},x_{2},x_{3},\ldots$ 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:

\begin{array}[]{rlllll}0\;.&d_{11}&d_{12}&d_{13}&d_{14}&\ldots\\ 0\;.&d_{21}&d_{22}&d_{23}&d_{24}&\ldots\\ 0\;.&d_{31}&d_{32}&d_{33}&d_{34}&\ldots\\ 0\;.&d_{41}&d_{42}&d_{43}&d_{44}&\ldots\\ \vdots&\;\vdots&\;\vdots&\;\vdots&\vdots&\ddots\end{array}

where

x_{n}=0.d_{n1}d_{n2}d_{n3}d_{n4}\ldots,

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

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

0.c_{1}c_{2}c_{3}\ldots

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 $x_{n}$ in the $n^{\scriptscriptstyle\text{th}}$ 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