Cantor's Diagonal Argument for the Real Numbers

Why a Decimal Diagonal Needs Care

To show that \((0,1)\) is uncountable, it is enough to show that no sequence of its points lists every point. The diagonal idea is to change the \(n\)th decimal digit of the \(n\)th listed number. But a difference between decimal strings does not always mean a difference between real numbers: \(0.2000\ldots=0.1999\ldots\). We will use decimal expansions that are never eventually all nines, then construct a new decimal using only the digits 1 and 2. These choices make the comparison of digits valid as a comparison of real numbers.

Here, a sequence \((x_n)\) lists a set if every point of the set occurs as at least one term; repetitions are allowed. A set is countable if it is finite or can be listed by a sequence. Since \((0,1)\) is nonempty, the empty set of terms cannot list it.

Canonical Decimal Expansions

We first establish that every \(x\in(0,1)\) has a canonical decimal expansion. For each \(k\geq 0\), let \(m_k=\lfloor 10^kx\rfloor\), where \(\lfloor t\rfloor\) is the greatest integer not exceeding \(t\), and set \(m_0=0\). For \(k\geq1\), define \(a_k=m_k-10m_{k-1}\). Since \(m_k\leq 10^kx<m_k+1\), the integer \(m_k\) is either \(10m_{k-1}+r\) for some integer \(r\) from 0 through 9. Thus \(a_k\) is a decimal digit.

Proof. From \(a_k=m_k-10m_{k-1}\), summing after division by \(10^k\) gives, for every \(N\geq1\), \(\sum_{k=1}^{N}a_k10^{-k}=m_N10^{-N}\): the terms involving \(m_1,\ldots,m_{N-1}\) cancel. The floor inequalities give \(0\leq x-m_N10^{-N}<10^{-N}\). As \(N\) increases, this error tends to zero, so \(x=\sum_{k=1}^{\infty}a_k10^{-k}\).

It remains to check that the digits are not eventually all 9. If \(a_k=9\) for every \(k\geq N\), then the expansion just obtained gives \(x=m_{N-1}10^{-(N-1)}+\sum_{k=N}^{\infty}9\,10^{-k}=(m_{N-1}+1)10^{-(N-1)}\). For \(N=1\), this says \(x=1\), contrary to \(x\in(0,1)\). For \(N>1\), it says \(10^{N-1}x=m_{N-1}+1\), so \(\lfloor10^{N-1}x\rfloor=m_{N-1}+1\), contradicting the definition of \(m_{N-1}\). The expansion is therefore canonical. \(\square\)

We also need the reason canonical expansions can be compared digit by digit.

Proof. Suppose two canonical sequences \((a_k)\) and \((b_k)\) represent the same real number but are not identical. Let \(j\) be the first index at which they differ. Interchanging the sequences if necessary, assume \(a_j<b_j\). The difference between the represented numbers is \((b_j-a_j)10^{-j}+\sum_{k>j}(b_k-a_k)10^{-k}\). For every \(k>j\), \(b_k-a_k\geq-9\), and \(\sum_{k>j}9\,10^{-k}=10^{-j}\). Therefore this difference is at least \((b_j-a_j)10^{-j}-10^{-j}\geq0\). For the numbers to be equal, both inequalities must be equalities. In particular \(b_j-a_j=1\), and every later difference must be \(-9\). That forces \(a_k=9\) and \(b_k=0\) for every \(k>j\), so \((a_k)\) is eventually all 9. This contradicts its being canonical. Hence distinct canonical sequences represent distinct real numbers. \(\square\)

The Diagonal Construction

Proof. Suppose a sequence \((x_n)\) of points in \((0,1)\) is given. Repetitions are permitted. Write the canonical decimal expansion of each term as \(x_n=0.a_{n1}a_{n2}a_{n3}\ldots\), using the construction above. Define a digit \(d_n\) by \(d_n=1\) if \(a_{nn}\ne1\), and \(d_n=2\) if \(a_{nn}=1\). Then \(d_n\in\{1,2\}\), and \(d_n\ne a_{nn}\) for every \(n\). Set \(y=\sum_{n=1}^{\infty}d_n10^{-n}\). Since \(1\leq d_n\leq2\), the geometric series gives \(0<\sum_{n=1}^{\infty}10^{-n}\leq y\leq\sum_{n=1}^{\infty}2\,10^{-n}=2/9<1\). Thus \(y\in(0,1)\). Its displayed decimal digits are all 1 or 2, so this expansion is canonical.

For each \(n\), the \(n\)th digit of \(y\) differs from the \(n\)th digit of \(x_n\). If \(y=x_n\), the uniqueness proposition for canonical expansions would force all corresponding digits to agree, including the \(n\)th digit. This is a contradiction. Hence \(y\) is not any term \(x_n\), and the sequence does not list \((0,1)\).

To conclude uncountability, the empty finite list cannot list \((0,1)\), which is nonempty. Any nonempty finite list can be extended to a sequence by repeating one of its entries. The theorem shows that this sequence misses a point, so the finite list does too. An infinite countable listing is already a sequence and is ruled out by the theorem. Thus \((0,1)\) is not countable. \(\square\)

A Common Pitfall: Changing Digits Is Not Enough

Changing every diagonal digit does not automatically prove that the resulting real number differs from each listed real. If the new decimal is allowed to end in repeating nines, it may equal another decimal with different digits. For a concrete failure, consider the sequence \(x_1=0.8000\ldots\), \(x_2=0.2000\ldots\), and \(x_n=0.1000\ldots\) for \(n\geq3\). The incorrect rule \(d_n=9-a_{nn}\) gives \(d_1=9-8=1\), \(d_2=9-0=9\), and \(d_n=9-0=9\) for every \(n\geq3\). The resulting decimal is \(0.1999\ldots\), which equals \(0.2000\ldots=x_2\): indeed, \(\sum_{n=2}^{\infty}9\,10^{-n}=1/10\), so \(0.1+\sum_{n=2}^{\infty}9\,10^{-n}=0.2\). The digit at position 2 differs from the corresponding digit of \(x_2\), but the real numbers are equal.

The repair is not to assume that different decimal strings always mean different numbers. Instead, use canonical expansions for the listed reals and choose new digits from \(\{1,2\}\). The constructed expansion is then canonical too, and the uniqueness proposition makes the digit-by-digit contradiction valid. The restriction to digits 1 and 2 also keeps the new number strictly within \((0,1)\).