Cantor’s Diagonal Argument

Georg Cantor (1845-1918)’s correspondence with mathematician Richard Dedekind (1831-1916) in the years 1873-74 has been narrated in a previous newsletter. Their letters detail the process by which Cantor arrived at the discovery that the set of the real numbers is uncountably infinite. That is, Cantor showed that although both the natural numbers and the real numbers are infinite in number and so go on forever, there “aren’t enough” natural numbers to create a one-to-one correspondence between them and the real numbers. Cantor’s brilliant discovery, in other words, showed rigorously and undeniably that infinity comes in different sizes, some of which are larger than others. One of his methods of proving this assertion, Cantor’s diagonal argument, was later employed by both Gödel and Turing in their most renowned results.

The Uncountability of Real Numbers (Cantor, 1891)

Cantor first demonstrated the uncountability of real numbers using a topological proof based on the Bolzano-Weierstrass theorem in the 1874 paper Ueber eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen (“On a Property of the Collection of All Real Algebraic Numbers“) in Crelle’s Journal. Here, Cantor showed:

The Uncountability of Real Numbers
Given any sequence of real numbers and any interval [α ... β], one can determine a number η in [α ... β] that does not belong to the sequence. Hence, one can determine infinitely many such numbers η in [α ... β].

A real number ℝ is a value of a continuous quantity that can represent a distance along a line. Any real number can be determined by a possibly infinite decimal representation, such as that of e.g. 8.632, 0.00001, 10.1 and so on, where each consecutive digit is measured in units one tenth the size of the previous one. The statement that the real numbers are uncountable is equivalent to the statement 

|ℝ| ≠ |ℕ|.

Although Cantor had already shown the statement to be true in 1874, he reproved it again seven years later using what would later be known as the diagonal argument. 

His proof was published in the 1891 paper Ueber eine elementare Frage der Mannigfaltigkeitslehre (“On an Elementary Question of Manifold Theory”). In his paper, Cantor presents the argument as follows:

Proof that the set of all infinite binary sequences are not denumerable. Consider the set M of all infinite sequences of the binary numbers m and w. Sequences such as:

E₁ = (m, m, m, m, m, ...),
E₂ = (w, w, w, w, w, ...),
E₃ = (m, w, m, w, m, ...),
E₄ = (w, m, w, m, w, ...),
E₅ = (m, m, w, w, m, ...)

Cantor asserts that there exists a set M that does not have the “breath” of the series E₁, E₂, E₃ … , meaning M is of a different size than the sum of each sequence En, i.e. that even though M is constructed of all the infinite sequences of the binary numbers m and w, he can always construct a new sequence E₀ which “is both an element of M and is not an element of M.”

The new sequence E₀ is constructed using the complements of one digit from each sequence E₁, E₂, … En. A complement of a binary number is defined as the value obtained by inverting the bits in the representation of the number (swapping m for w and visa versa). So, the new sequence is made up of the complement of the first digit from the sequence E₁ (m), the complement of the second digit from the sequence E₂ (w), the complement of the third digit from the sequence E₃ (m) and so on to finally the complement of the nth digit from the sequence En. From the example sequences above, the new sequence E₀ would then be:

E₀ = (w, m, w, w, w, ...)

By its construction, E₀ differs from each sequence En since their nth digits differ. Hence, E₀ cannot be one of the infinite sequences in the set M.

The proof provided below applies the argument specifically to prove the uncountability of the real numbers ℝ. It is an excerpt from the book Real Analysis and Applications* by Frank Morgan (2005).

Proof of the Uncountability of the Real numbers ℝ (Morgan, 2005)
Assume that the following proposition is false:

The set of reals ℝ is uncountable.

We will derive a contradiction. In particular, we will assume that the reals can be listed, and then exhibit a real number missing from the list, the desired contradiction. Since the argument applies to any list, that will complete the proof. 
Suppose that the reals were countable. Then the positive reals would also be countable and could be listed, for example as such:

1. 6 5 7 . 8 5 3 2 6 0 ...
2. 2 . 3 1 3 3 3 3 ...
3. 3 . 1 4 1 5 9 2 ...
4. . 0 0 0 3 0 7 ...
5. 4 9 . 4 9 4 9 4 9 ...
6. . 8 7 3 2 5 7 ...
...

To obtain a contradiction, it suffices to show that there exists some real α that is missing from the list. The construction of such an α works by making its first decimal place different from the first decimal place of the first number of the list, by making the second decimal place different from the second decimal place of the second number, and in general by making the nth decimal place different from the nth decimal place of the nth number on the list.

Even simpler, for our α we'll make the nth decimal place 1 unless it is already 1, in which case we'll make it 2. By this process, for our example list of numbers, we obtain:

α = . 1 2 2 1 1 1 ...

Which, by construction cannot be a member of the list we created. And so, by contradiction, our list of all reals cannot contain every number, and so must be uncountable.

Summarized, to prove the uncountability of the reals we first list all such numbers and assume this list is exhaustive. Next, starting from the top, we construct a new real number using one decimal place from each of the numbers in the list, altering each digit to not match the digits from the list we use in the construction, to infinity. We observe that this new number, the nth number on the list will always differ from all of those already the list. Thus, our list of the real numbers is not exhaustive, and so they must be uncountable. 

Another way of thinking about it is provided in Richard Hammock’s Book of Proof*(2013):

Imagine making a table for the function f(n): ℕ → ℝ where values of n in ℕ are the left-hand column and the corresponding values of f(n) are on the right. The first few entries might look something as follows:

n | f(n)
1 | 0 . 4 0 0 0 0 0 0 0 0 0 ...
2 | 8 . 5 0 0 6 0 7 0 8 6 6 ...
3 | 7 . 5 0 5 0 0 9 4 0 0 4 ...
4 | 5 . 5 0 7 0 4 0 0 8 0 4 ...
5 | 6 . 9 0 0 2 6 0 0 0 0 0 ...
6 | 6 . 8 2 8 0 9 5 8 2 0 0 ...
7 | 6 . 5 0 5 0 5 5 5 0 6 5 ...
8 | 8 . 7 2 0 8 0 6 4 0 0 0 ...
9 | 0 . 5 5 0 0 0 0 8 8 8 8 ...
10 | 0 . 5 0 0 2 0 7 2 2 0 7 ...

In this table, the real numbers f(n) are written with all their decimal places trailing off to the right. Thus, even though f(1) happens to be the real number 0.4, we write it as 0.4000000...., etc. There is a diagonal bolded band in the table. For each n ∈ ℕ, this diagonal covers the nth decimal place of f(n):

The 1st decimal place of f(1) is the 1st entry
The 2nd decimal place of f(2) is the 2nd entry
The 3rd decimal place of f(3) is the 3rd entry etc

The diagonal helps us construct a number b ∈ ℝ that is unequal to any f(n). Just let the nth decimal place of b differ from the nth entry of the diagonal. Then the nth decimal place of b differs from the nth decimal place of f(n).

- Excerpt, Book of Proof* by Richard Hammock (2013)

The Incompleteness of First-Order Logic (Gödel, 1931)

Forty years later, logician Kurt Gödel (1906-78) utilized Cantor’s diagonal argument to show that any system of logic is inherently incomplete, in his famous paper:

• Gödel, K. (1931). Über formal unentscheidbare der Principia Mathematica und verwandter Systeme I (“On formally undecidable propositions of Principia Mathematica and related systems I”) Monatshefte für Mathematik und Physik 38. pp. 173–198.

Biographer John W. Dawson describes Gödel’s result as follows:

"Gödel's achievement was to show how to construct a statement whose undecidability could be (informally) demonstrated. He did so by showing in very detailed fashion that a large number of basic syntactic notions are representable, through their code numbers, by formulas of formalized arithmetic.

Specifically, he showed that there is a binary, primitive recursive predicate B(x,y) that formalizes the notion "x is the code number of a proof of the formula whose code number is y", so that if n and m are natural numbers and n and m are the symbols denoting those numbers within the formal theory, then B(n,m) is disprovable otherwise.

It follows that the monadic predicate Bew(y) defined as an abbreviation for the formula (∃x)B(x,y), formalizes the notion "y is provable". The negation of Bew(y) then formalizes the notion "y is not provable"; and that notion, Gödel realized, could be exploited by resort to a diagonal argument reminiscent of Cantor's."

- Excerpt, Logical Dilemmas* by John W. Dawson (2006)

Complicated as Gödel’s proof by contradiction is, its construction may be superficially described as follows:

• Statements in the system (which may be true of false) can be represented by natural numbers, later known as Gödel numbers. Statements which are true have certain properties which are different than statements which are false. The truth and falsehood of statements in the system in other words may be demonstrated by examining their Gödel numbers. 
• As a consequence, one can construct a mathematical formula which expresses the idea that “statement S is provable in the system”. This formula can applied to any statement S in the system in order to investigate its provability.
• Using Cantor’s diagonal argument, in all formal systems which are complete, we must thus be able to construct a Gödel number whose matching statement, when interpreted, is self-referential. 
• The meaning of one such statement is equivalent to the English statement “I am unprovable” (read: “The Liar Paradox”). Such a self-referential statement demonstrates that there must exist statements in the system which are neither provable nor disprovable.

The fact that there exists a statement in the system which is neither provable nor disprovable demonstrates that that the system cannot be consistent if it is both complete (every formula may be derived from its axioms) and decidable (there exists an effective method for deriving the correct answer to any question).

The Undecidability of the Entscheidungsproblem (Turing, 1937)

The Entscheidungsproblem (so-called “decision problem”) was a mathematical challenge originally posed by David Hilbert (1862–1943) and his doctoral student Wilhelm Ackermann (1896–1962) in 1928. The challenge asked for an algorithm which takes a logical statement in a formal language and outputs “True” or “False” depending on the truth value of the statement. It was published in Turing’s publication:

• Turing, A. (1937). On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society 2 (42). pp. 230–265.

By introducing his theoretical “universal computing machine” (now called a Turing machine), defined as:

A Turing machine (a-machine) is a mathematical model of computation that defines an abstract machine which manipulates symbols on a strip of tape according to a table of rules.

Turing in the paper proved that:

• A Turing machine would be capable of performing any conceivable mathematical computation if it were representable as an algorithm (a finite sequence of well-defined instructions). Moreover:
• There cannot be a solution to the Entscheidungsproblem because the halting problem for Turing machines is undecidable, meaning that it is not possible to decide algorithmically whether a Turing machine will ever halt (read: Turing Uncomputability).

Briefly, sets of numerical strings have two properties that are of particular relevance to Turing’s paper. They are enumerability and decidability:

Enumerability 
A set E of strings is computably enumerable if it is possible to program a computer to compute and print out the members of E.

Decidability
A set E of strings is computably decidable if it is possible to program a computer to decide, given any string s of symbols, whether or not is in E.

Turing’s proof of the so-called undecidability theorem is structured as follows (Franzén, 2004):

Create a computable enumerable list of all possible programs:

P₀, P₁, P₂, ..., Pᵢ

Define i to be the index of the program Pᵢ. Now let K be the set of all i such that Pᵢ terminates and outputs a value when given the index i of the program as an input. The set K is computably enumerable by definition. 

However, the set K is not decidable. To show this, suppose that K was decidable. We can then define a procedure which given any input i first checks whether i is in K. If not, we give 0 as output. If i is in K so that Pᵢ does terminate with i as input, we let Pᵢ compute its result and then give as output that result with a further symbol added as the end. 

Since this defines a program P that given any string computes another string as output, P must be identical with Pm for some m. But P and Pm do not agree on m, so they are not identical. Hence, K is not decidable.

Here we see the diagonal argument appear in the sentence “If i is in K so that Pᵢ does terminate with i as input, we let Pᵢ compute its result and then give as output that result with a further symbol added as the end.”

The properties and implications of Cantor’s diagonal argument and their later uses by Gödel, Turing and Kleene are outlined more technically in the paper:

• Gaifman, H. (2006). Naming and Diagonalization, from Cantor to Gödel to Kleene. Logic Journal of the IGPL 14 (5). pp. 709–728.

* This story contains Amazon Affiliate links