The diagonal argument · Computability Theory

In 1891, Cantor gave a short proof that no sequence of infinite binary sequences contains all of them. The method, called diagonalization, is the most frequently used argument in computability theory: it shows that the halting problem is undecidable, that there are total computable functions which are not primitive recursive, and, in more elaborate forms, it underlies most constructions of non-computable sets. This lesson presents the argument, isolates its general form, and derives the uncountability of $2^\nat$ , $\nat^\nat$ , $\mathcal P(A)$ and $\mathbb R$ .

4.1 Cantor space

Definition 4.1.#

Cantor space is the set $\cs$ of infinite binary sequences, that is, of functions $X : \nat \to \{0, 1\}$ . For $X \in \cs$ and $n \in \nat$ , the value $X(n)$ is the $n$ -th bit of $X$ , and one writes $X = X(0)\,X(1)\,X(2) \cdots$ .

A sequence $X \in \cs$ and the set $\{ n : X(n) = 1 \} \subseteq \nat$ determine each other: the map $X \mapsto \{ n : X(n) = 1 \}$ is a bijection from $\cs$ onto $\mathcal P(\nat)$ , whose inverse sends a set to its characteristic function. In computability theory the two points of view are used interchangeably: the same letter $X$ denotes a subset of $\nat$ and its characteristic function, so that $n \in X$ if and only if $X(n) = 1$ .

Finite binary strings are written $\sigma, \tau, \dots$ ; the set of finite binary strings is $2^{<\nat}$ , the length of $\sigma$ is $|\sigma|$ , and $X \upharpoonright n = X(0) \cdots X(n-1)$ is the prefix of length $n$ of $X$ . By Proposition 3.11, $2^{<\nat}$ is countable.

4.2 The diagonal argument

Theorem 4.2 (Cantor).#

The set $\cs$ is uncountable: for every sequence $X_0, X_1, X_2, \dots$ of elements of $\cs$ , the sequence $Y$ defined by

Y(n) = 1 - X_n(n)

is different from every $X_n$ .

Proof of Theorem 4.2.

For every $n$ , the sequences $Y$ and $X_n$ differ at position $n$ , since $Y(n) = 1 - X_n(n) \neq X_n(n)$ . So $Y$ is none of the $X_n$ . Hence no function $\nat \to \cs$ is surjective, and $\cs$ , which is non-empty, is not countable by Proposition 3.3.

The sequences

X_n

written as the rows of an infinite table. The sequence

Y

is obtained by flipping the bits of the diagonal, so that it differs from row

n

in column

n

.

The name of the argument comes from the table: the bits $X_n(n)$ form its diagonal. Two features matter. First, $Y$ is defined from the sequence $(X_n)$ , explicitly: the proof does not only show that some sequence is missing, it computes one. Second, each $X_n$ is defeated at a position of its own, so that the constraints on $Y$ never conflict.

4.3 A general form

The argument uses neither binary values nor the indexing by integers in an essential way. Its general form is the following.

Proposition 4.3 (Diagonal lemma).#

Let $A$ and $B$ be sets, $F : A \times A \to B$ a function, and $\delta : B \to B$ a function without fixed point, that is, $\delta(b) \neq b$ for every $b \in B$ . Then the function $g : A \to B$ defined by

g(a) = \delta\big(F(a, a)\big)

is different from each function $F(e, \cdot) : a \mapsto F(e, a)$ , for $e \in A$ .

Proof of Proposition 4.3.

For $e \in A$ , $g(e) = \delta(F(e, e)) \neq F(e, e)$ , so $g$ and $F(e, \cdot)$ differ at $e$ .

A function $F : A \times A \to B$ is the same thing as a family $(F(e, \cdot))_{e \in A}$ of functions $A \to B$ , indexed by $A$ , that is, a function from $A$ to the set $B^A$ of functions from $A$ to $B$ . The lemma says that such a family never contains all functions $A \to B$ , as soon as $B$ has a fixed-point-free map. Read contrapositively:

Corollary 4.4 (Lawvere’s fixed point theorem).#

If there is a surjection from $A$ onto $B^A$ , then every function $\delta : B \to B$ has a fixed point.

Proof of Corollary 4.4.

Let $e \mapsto F_e$ be a surjection from $A$ onto $B^A$ , and let $F(e, a) = F_e(a)$ . If $\delta$ had no fixed point, the function $g$ of Proposition 4.3 would differ from every $F_e$ , contradicting surjectivity.

If $B$ has at least two elements $b_0 \neq b_1$ , the map exchanging $b_0$ and $b_1$ and fixing every other element has no fixed point, so there is no surjection from $A$ onto $B^A$ . The fixed point form is not a curiosity: Kleene’s fixed point theorem in the course on fundamentals (Fixed point theorem) has the same structure, with a numbering of partial computable functions in place of the surjection, and with the conclusion that every total computable transformation $f$ of programs has a fixed point up to the function computed: $\Phi_{f(e)} = \Phi_e$ for some $e$ .

Example 4.5.#

$A = \nat$ , $B = \{0, 1\}$ , $\delta(b) = 1 - b$ , and $F(n, m) = X_n(m)$ gives Theorem 4.2.
$A = B = \nat$ , $\delta(b) = b + 1$ : for every sequence $(f_n)$ of functions $\nat \to \nat$ , the function $g(n) = f_n(n) + 1$ differs from every $f_n$ . So the Baire space $\nat^\nat$ of functions $\nat \to \nat$ is uncountable.
$A$ arbitrary, $B = \{0, 1\}$ : functions $A \to \{0, 1\}$ are characteristic functions of subsets of $A$ ; this gives the theorem of the next section.

4.4 Every set is smaller than its power set

Theorem 4.6 (Cantor).#

For every set $A$ , there is no surjection from $A$ onto its power set $\mathcal P(A)$ . Hence $|A| < |\mathcal P(A)|$ .

Proof of Theorem 4.6.

Let $f : A \to \mathcal P(A)$ , and let

D = \{ a \in A : a \notin f(a) \}.

If $D = f(d)$ for some $d \in A$ , then $d \in D$ if and only if $d \notin f(d) = D$ , a contradiction. So $D$ is not in the image of $f$ . Finally, $a \mapsto \{a\}$ is an injection $A \to \mathcal P(A)$ , so $|A| \leq |\mathcal P(A)|$ ; and $|A| \neq |\mathcal P(A)|$ , since a bijection would be a surjection.

Iterating, $\nat$ , $\mathcal P(\nat)$ , $\mathcal P(\mathcal P(\nat))$ , … is a sequence of infinite sets of strictly increasing cardinalities: there is no largest cardinality.

Remark 4.7 (Russell’s paradox).#

Apply the proof to a hypothetical set $V$ of all sets, with $f$ the identity: every subset of $V$ is a set, hence an element of $V$ , so $f(x) = x$ for $x \in \mathcal P(V)$ (and, say, $f(x) = \emptyset$ for the elements of $V$ that are not sets) is a surjection onto $\mathcal P(V)$ . The diagonal set is $D = \{ x : x \notin x \}$ , essentially Russell’s set, and the contradiction is Russell’s paradox (1901). In axiomatic set theory, the conclusion is that there is no set of all sets; the collection $\{x : x \notin x\}$ exists only as a class.

4.5 The real numbers

The diagonal argument gives a short proof of Cantor’s first uncountability theorem (1874). Decimal expansions need some care, because some real numbers have two of them: $0.1999\cdots = 0.2000\cdots$ . For a real number $x$ and $k \geq 1$ , let

d_k(x) = \lfloor 10^k x \rfloor - 10 \lfloor 10^{k-1} x \rfloor \in \{0, 1, \dots, 9\}

be the $k$ -th decimal digit of the fractional part $x - \lfloor x \rfloor$ , in the expansion that does not end with infinitely many $9$ s.

Theorem 4.8 (Cantor).#

The set $\mathbb R$ is uncountable: for every sequence $(x_n)_{n \in \nat}$ of real numbers, the number

r = \sum_{n \in \nat} c_n \, 10^{-(n+1)}, \qquad c_n = \begin{cases} 4 & \text{if } d_{n+1}(x_n) = 5,\\ 5 & \text{otherwise,}\end{cases}

is different from every $x_n$ .

Proof of Theorem 4.8.

We first show $d_{k}(r) = c_{k-1}$ for every $k \geq 1$ . For every $k \geq 0$ , write

10^k r = \sum_{n < k} c_n \, 10^{k-1-n} + t_k, \qquad t_k = \sum_{n \geq k} c_n \, 10^{k-1-n}.

The first sum is an integer $N_k$ , and since every $c_n$ lies in $\{4, 5\}$ , the tail satisfies $0 < \tfrac49 \leq t_k \leq \tfrac59 < 1$ . So $\lfloor 10^k r \rfloor = N_k$ , and $d_k(r) = N_k - 10 N_{k-1} = c_{k-1}$ .

Now if $r = x_n$ , then $d_{n+1}(x_n) = d_{n+1}(r) = c_n$ , which contradicts the definition of $c_n$ , chosen different from $d_{n+1}(x_n)$ .

The digits $4$ and $5$ are chosen so that the tail $t_k$ stays below $1$ , which makes $0.c_0c_1c_2\cdots$ the expansion of $r$ that does not end with $9$ s; any two digits other than $9$ would do as well. The digit $9$ must be avoided: a rule that only requires $c_n \neq d_{n+1}(x_n)$ could produce $c_0 = 0$ and $c_n = 9$ for all $n \geq 1$ , so that $r = 0.0999\cdots = 0.1$ , while $x_0 = 0.1$ has $d_1(x_0) = 1 \neq c_0$ .

4.6 Exercises

Exercise 4.9 ★.

Show that the set of infinite subsets of $\nat$ , and the set of strictly increasing functions $\nat \to \nat$ , are uncountable.

Solution

The map $X \mapsto \{ 2n + X(n) : n \in \nat \}$ is an injection of $\cs$ into the set of infinite subsets of $\nat$ : the image contains exactly one element of $\{2n, 2n+1\}$ for each $n$ , and $X(n)$ is its parity. Similarly, $X \mapsto (n \mapsto 2n + X(n))$ is an injection of $\cs$ into the set of strictly increasing functions, since $2n + X(n) \leq 2n + 1 < 2(n+1) + X(n+1)$ . A set into which $\cs$ injects is uncountable, since otherwise $\cs$ would be countable by Corollary 3.4.

Exercise 4.10 ★★.

Show that the set of bijections $\nat \to \nat$ is uncountable.

Solution

To $X \in \cs$ , associate the permutation $\pi_X$ that exchanges $2n$ and $2n + 1$ when $X(n) = 1$ , and fixes them when $X(n) = 0$ . It is a bijection (it is its own inverse), and $X \mapsto \pi_X$ is injective, since $X(n) = 1$ if and only if $\pi_X(2n) = 2n + 1$ . Conclude as in the previous exercise.

Exercise 4.11 ★★.

(Cantor’s proof of 1874.) Let $(x_n)$ be a sequence of real numbers. Construct closed intervals $[a_0, b_0] \supseteq [a_1, b_1] \supseteq \cdots$ with $b_n - a_n = 3^{-n}$ and $x_n \notin [a_{n+1}, b_{n+1}]$ , and deduce that some real number differs from every $x_n$ . Which property of $\mathbb R$ is used?

Solution

Start from $[a_0, b_0] = [0, 1]$ . Given $[a_n, b_n]$ , cut it into three closed thirds; $x_n$ belongs to at most two of them, since the first and the last third are disjoint. Let $[a_{n+1}, b_{n+1}]$ be the leftmost third not containing $x_n$ . The sequence $(a_n)$ is non-decreasing and bounded by $b_0$ , so it has a limit $r$ , by the completeness of $\mathbb R$ ; and $a_m \leq r \leq b_m$ for every $m$ , since $a_n \leq b_m$ for all $n$ and $m$ . Then $r \in [a_{n+1}, b_{n+1}]$ , so $r \neq x_n$ , for every $n$ . Over $\mathbb Q$ , which is countable, the limit $r$ need not exist.

Exercise 4.12 ★★.

Let $(X_n)$ be a sequence of elements of $\cs$ . Show that the set of $Y \in \cs$ different from every $X_n$ is uncountable.

Solution

Let $M = \cs \setminus \{ X_n : n \in \nat \}$ . It is non-empty by Theorem 4.2. If it were countable, there would be a surjection $m \mapsto Z_m$ from $\nat$ onto $M$ , and the sequence $X_0, Z_0, X_1, Z_1, \dots$ , that is, $W_{2n} = X_n$ and $W_{2n+1} = Z_n$ , would enumerate all of $\cs$ , contradicting Theorem 4.2. The lesson on the continuum shows more: $M$ is equipotent to $\cs$ .

4.7 Notes and references

The diagonal argument appears in Cantor’s note of 1891, where it is applied to binary sequences and then to the power set of an arbitrary set. The 1874 proof of the uncountability of $\mathbb R$ uses nested intervals. The general form of the diagonal lemma and its fixed point reading are due to Lawvere, in the setting of cartesian closed categories; Yanofsky gives an elementary account, with applications to the paradoxes and to incompleteness. Russell communicated his paradox to Frege in a letter of 1902, and published it in the Principles of Mathematics.

G. Cantor, Über eine elementare Frage der Mannigfaltigkeitslehre, Jahresbericht der Deutschen Mathematiker-Vereinigung 1 (1891), 75–78.
F. W. Lawvere, Diagonal arguments and cartesian closed categories, in Category Theory, Homology Theory and their Applications II, Lecture Notes in Mathematics 92, Springer, 1969, 134–145.
N. S. Yanofsky, A universal approach to self-referential paradoxes, incompleteness and fixed points, Bulletin of Symbolic Logic 9 (2003), 362–386.
B. Russell, The Principles of Mathematics, Cambridge University Press, 1903.