Uncountability and Cantor's Diagonal Argument

When No List Can Contain Every Element

The Countable Union Theorem showed how to collect countably many countable sets into a countable union. That result concerns sets that can be listed. A different question is whether every infinite set can be listed in this way. The answer is no: there are sets whose elements cannot be put into a sequence indexed by the natural numbers.

The method that proves this is Cantor’s diagonal argument. Begin by assuming that every object of a certain kind appears in a list. Then construct a new object whose \(n\)th component differs from the \(n\)th component of the \(n\)th listed object. This guarantees that the new object is absent from every position in the list.

The argument is easiest to see for infinite sequences of zeros and ones. Let \(S\) be the set of all sequences \(s=(s_1,s_2,\ldots)\) with \(s_n\in\{0,1\}\) for every \(n\in\mathbb N\). An element of \(S\) is an entire sequence, not merely one of its entries.

The Diagonal Argument for Binary Sequences

Proof. Suppose, for contradiction, that \(S\) is countable. Since \(S\) contains the infinitely many distinct sequences with a single one in position \(n\) (\(n\in\mathbb N\)), \(S\) is infinite, so it would then be possible to list its elements in a sequence \(s^{(1)},s^{(2)},s^{(3)},\ldots\), with every member of \(S\) appearing somewhere in the list. Write \(s^{(n)}_k\) for the \(k\)th entry of the \(n\)th sequence. The list can be displayed as an array:

Define a new sequence \(t=(t_1,t_2,\ldots)\) by changing the \(n\)th entry of the \(n\)th listed sequence:

Each \(s^{(n)}_n\) is either zero or one, so \(t_n\) is also either zero or one. Therefore \(t\in S\). But for every \(n\), the entries \(t_n\) and \(s^{(n)}_n\) differ. Hence \(t\ne s^{(n)}\) for every \(n\): the two sequences disagree at least in their \(n\)th entry. The list was assumed to contain every member of \(S\), yet \(t\) is not on it. This contradiction proves that \(S\) is uncountable. \(\square\)

The important feature is that the construction targets a different entry for each row: the diagonal entry in row \(n\). Changing just one entry in row \(n\) is enough to ensure that the new sequence is not row \(n\). The construction does not try to guess which sequence the list may have missed; it builds one that must be missing.

From Binary Sequences to Real Numbers

A diagonal argument also proves that the open interval \((0,1)\) is uncountable. We use decimal expansions, with each number represented by its decimal expansion that is not eventually all nines. In particular, a terminating decimal is represented with zeros after its final nonzero digit. This convention avoids the two representations of numbers such as \(0.5000\ldots=0.4999\ldots\).

The relevant uniqueness fact follows from the size of the decimal tail. If two decimal expansions first differ at position \(k\), the contribution of the difference at that position has size at least \(10^{-k}\). The total possible difference from all later positions is at most

For the two expansions to represent the same number, equality in this tail bound would be necessary. That can happen only when the expansion with the smaller \(k\)th digit has nines at every later position and the expansion with the larger \(k\)th digit has zeros at every later position. In particular, two expansions that are both not eventually all nines cannot represent the same number. Therefore the chosen convention gives a unique expansion for each real number in \((0,1)\).

Proof. Suppose, for contradiction, that \((0,1)\) is countable. It is infinite, so its elements could be listed as \(x_1,x_2,x_3,\ldots\). Write the chosen decimal expansion of each listed number as \(x_n=0.a_{n1}a_{n2}a_{n3}\ldots\), where every \(a_{nk}\) is a digit from zero to nine.

For each \(n\), choose a digit \(b_n\) by setting \(b_n=1\) if \(a_{nn}\ne1\), and \(b_n=2\) if \(a_{nn}=1\). In either case \(b_n\ne a_{nn}\), and \(b_n\) is either one or two. Form the decimal number

The digits \(b_n\) define a real number in \((0,1)\): it is positive, and its decimal value is at most \(0.2222\ldots<1\). This decimal is not eventually all nines, so it is the chosen representation of \(y\). For every \(n\), the decimal expansion of \(y\) differs from the chosen expansion of \(x_n\) in position \(n\), since \(b_n\ne a_{nn}\). By uniqueness of the chosen decimal expansions, \(y\ne x_n\) for every \(n\). Thus the list omits \(y\), contradicting the assumption that it contains every element of \((0,1)\). Hence \((0,1)\) is uncountable. \(\square\)

What the Argument Establishes

The binary-sequence theorem has a direct set-theoretic interpretation. To each subset \(A\subseteq\mathbb N\), associate its indicator sequence: its \(n\)th entry is one when \(n\in A\), and zero when \(n\notin A\). This correspondence is a bijection between the power set of \(\mathbb N\) and the set of binary sequences. Indeed, the sequence determines the subset of positions at which its entries are one, and every subset determines exactly one such sequence. Consequently, the power set of \(\mathbb N\) is uncountable as well.

The decimal proof also establishes that the real numbers are uncountable, since \((0,1)\subseteq\mathbb R\). If \(\mathbb R\) were countable, then every subset of \(\mathbb R\) would be countable by the earlier result that every subset of a countable set is countable. In particular \((0,1)\) would be countable, contrary to the theorem.

A common pitfall is to think that the diagonal construction merely changes one sequence in a list, or that it works only if the list has no repetitions. Neither is true. Repetitions do not matter: the constructed sequence differs from row \(n\) at its \(n\)th entry whether or not that row appears elsewhere. The contradiction is that every possible position in the list is defeated at its own diagonal entry.

There is also an important distinction between countably infinite and uncountable. Both are infinite, but only a countably infinite set admits a complete sequence listing. Cantor’s argument does not show that the real numbers are “very large” in a numerical sense; it shows that no natural-number indexing can list all of them. This is a new kind of conclusion: a direct construction rules out every proposed enumeration at once.