The row that is not on the list

Suppose somebody supplies a list — an infinite list, numbered $1, 2, 3, \dots$ — of infinite sequences of ones and zeros. There is a sequence that is not on it, and the recipe for building it fits in one sentence.

Take the $n$th entry of the $n$th row, flip it, and use that as the $n$th entry of a new sequence. The new sequence differs from row 1 in place 1, from row 2 in place 2, and from row $n$ in place $n$. So it is not row 1, not row 2, and not row $n$ for any $n$. It is not on the list.

What is and is not being claimed #

This argument attracts objections, and almost all of them come from misreading the quantifiers. It is worth being precise about them before anything else.

It is not claimed that some particular list is incomplete and a better one would work. The list is arbitrary — given in advance, unexamined, any list whatever — and the construction works on it. So the conclusion is universal: no list of binary sequences contains them all.

It is not claimed that the missing sequence is special or interesting. It is built from the list and depends on it entirely; a different list gives a different missing sequence, and the argument does not care which.

It is not an argument about lists being hard to write down. The construction is completely explicit: given the list, the new sequence’s $n$th digit is a one-step computation.

The logical shape is: for every list, there is a sequence not on it. Compare with the shape it is often misread as: there is a sequence not on any list, which is a different and false-sounding claim. The order of the quantifiers is the whole content, and which order a sentence is in is exactly the distinction the previous field-mate essay is about.

Why the rows must be a list to begin with #

There is a step before the diagonal that is easy to skip and is where the argument actually gets its strength.

Listing the sequences means putting them in one-to-one correspondence with $1, 2, 3, \dots$ — that is what a numbered list is. So the assumption being refuted is that such a correspondence exists, and what the diagonal produces is a sequence outside the correspondence’s range.

That is why the conclusion is about cardinality rather than about lists. Two collections have the same size when there is a one-to-one correspondence between them; the whole numbers have a standard size, called countable; and the argument shows the binary sequences are not that size. There are strictly more of them, in the only sense of more that survives being infinite.

The reason the diagonal works at all is that the list gives the argument a numbering to index into. Row $n$, position $n$ — the construction needs the rows and the positions to be indexed by the same thing, and the assumption of countability is what supplies that.

The same argument, four ways #

The argument does not care what the rows are sequences of, which is why it reappears constantly under different names.

Binary sequences. As drawn: the built sequence differs from row $n$ at place $n$.

Sets of whole numbers. A set is a sequence of yes/no answers, so the same table read differently. The built set contains $n$ exactly when $S_n$ does not.

Real numbers between 0 and 1. A number is its binary expansion, so the same table again. This is the version Cantor is usually quoted for and it is the one with a technicality — see below.

Functions from whole numbers to whole numbers. Change the flip from 0↔1 to add one and the same construction gives a function differing from the $n$th at $n$.

Four statements, one argument, and the fact that it transfers so freely is the first hint that it is about the shape of the situation rather than about numbers.

The technicality, which is real #

The real-number version has a genuine wrinkle and it is worth not hiding, because a reader who spots it and finds it glossed over will reasonably distrust everything else.

Binary expansions are not unique: $0.0111\ldots$ and $0.1000\ldots$ are the same number. So a sequence differing from every row as a sequence might still equal one of them as a number, if the difference is only in a tail of that kind.

The repair is small. Work in base ten and flip digits to something other than 0 or 9 — say, replace each diagonal digit by 5 unless it is already 5, in which case use 4. Then the built number’s expansion has no tail of nines and no tail of zeros, so its expansion is unique, so differing as a sequence means differing as a number.

It is worth doing this repair once and then noticing that it changes nothing structural. The wrinkle is about a representation, not about the argument, and the version for sets and the version for functions have no such wrinkle at all. That is a reasonable test of whether an objection is about the mathematics: does it survive translating the argument into one of its other forms?

Cantor’s theorem, which is the general case #

The diagonal is one instance of a much shorter statement.

For any set $X$, there is no map from $X$ onto its collection of subsets.

For a finite set the theorem is a count: $2^n > n$, always, and the picture shows it at $n = 3$. For an infinite set the count is unavailable and the diagonal supplies the argument.

The proof is two lines. Suppose $f$ sends each element $x$ of $X$ to a subset $f(x)$. Let

$$D = \{\, x \in X : x \notin f(x) \,\}$$

and ask whether $D$ is $f(d)$ for some $d$. If it is, then $d \in D$ exactly when $d \notin f(d) = D$, which is a contradiction. So $D$ is not in the image, and $f$ is not onto.

That is the diagonal with the table removed. $D$ is precisely the flipped diagonal: for each $x$, it disagrees with $f(x)$ about $x$. The table version and this version are the same construction, and the second is shorter because it never had to draw anything.

The other half: what a list can hold #

An impossibility is more informative when its neighbours are possible, and it is worth putting the two sides next to each other, because the boundary between them is not where intuition puts it.

The fractions can be listed. There are infinitely many of them between any two whole numbers and they can still be arranged in a single sequence — every fraction, exactly once is that listing, and it is a construction rather than an existence proof.

Finite strings over a finite alphabet can be listed. Sort by length, then alphabetically within each length. So there are countably many words, sentences, formulas, computer programs and proofs, in any notation whatever.

Pairs, triples and finite sequences of listable things can be listed. A list of lists is a list, and the standard zig-zag through a grid does it. So the algebraic numbers — roots of polynomials with whole-number coefficients — are listable, since each is specified by a finite tuple of whole numbers and an index.

Put those together and something sharp falls out, which was Cantor’s own first application in 1874. The algebraic numbers are listable and the reals are not, so there are numbers that satisfy no polynomial equation with whole-number coefficients — transcendental numbers — and there are far more of them than there are algebraic ones.

That result had been established once before, by Liouville in 1844, by constructing a specific transcendental number with enormous effort. Cantor’s argument produces none, names none, and shows there are more of them than everything Liouville’s method could ever reach. It is one of the cleanest cases in mathematics of a counting argument beating a construction, and it is the reason the diagonal was taken seriously rather than dismissed as a curiosity.

What follows, and it is a lot #

There is no largest size. Cantor’s theorem applies to any set including infinite ones, so from any infinite set there is a strictly larger one, and from that a larger one again. The sizes do not stop.

Almost all real numbers are not describable. There are countably many finite strings over any finite alphabet, so countably many definitions, formulas, programs and proofs. There are uncountably many real numbers. So the numbers a person could ever specify are a vanishingly small part of the whole — and this is a rare case where a counting argument establishes something about language.

A related counting argument bounds any formal system. There are only countably many proofs, because a proof is a finite string. Anything requiring uncountably many distinct pieces of finite evidence is therefore out of reach. That observation is not Gödel’s theorem and is often confused with it; it is a much cruder counting bound, and the interesting result is the one that survives once attention is restricted to statements that can be written down.

The reception, which is part of the result #

Cantor published the diagonal argument in 1891. The 1874 proof of the same conclusion was different and harder — a nested-intervals construction — and the diagonal was the second proof, offered because the first was thought obscure.

The reception was hostile in a way that is now hard to reconstruct. Kronecker, who had been Cantor’s teacher’s colleague and was a power in Berlin, regarded completed infinities as illegitimate and the whole programme as meaningless rather than wrong. Poincaré is supposed to have called set theory a disease. Cantor spent the second half of his career in and out of hospital and much of it trying to settle a question — whether there is a size strictly between the whole numbers and the reals — that turned out to be independent of the axioms, and therefore not settleable by trying harder.

The reason this belongs in the essay rather than in a footnote is that the objection was not a failure of understanding. Kronecker’s position is coherent and has a modern descendant, and what the twentieth century did was not refute it but make it precise enough to be one option among several. What settled the mathematical question was Hilbert’s judgement rather than Kronecker’s:

No one shall expel us from the paradise that Cantor has created.

That is a statement about which mathematics is worth doing, not a proof of anything.

Where the same move goes next #

The construction has a shape that is worth extracting on its own, because it is about to be used three more times in this field.

There is a table indexed by the same thing along both edges. Read the diagonal. Change it. The result cannot be a row.

That is all of it. The table can be sequences by position, sets by element, sets by membership in one another, or sentences by what they say about sentences. Each time, something indexes itself, and the diagonal is where the self-indexing bites.

The reason it is so productive is that the requirement is weak. It does not need arithmetic, or infinity, or any structure at all beyond a table whose rows and columns are indexed by the same set, and a way of changing an entry. Whenever a system can talk about its own objects — list them, number them, quote them — the diagonal is available, and the conclusion is always of the same kind: the system cannot contain a complete account of itself.

The objections, and why they fail #

The argument attracts more disbelief than any other elementary result in mathematics, so it is worth taking the three commonest objections seriously and saying exactly where each goes wrong.

“Add the new sequence to the list and the problem is solved.” It is not, because the argument then applies again to the new list and produces a different missing sequence. The claim is not that a particular list has one gap; it is that every list has one, and repairing a list produces a new list to which the theorem still applies.

“Both sets are infinite, so they are the same size.” This is the objection that treats infinite as a size. It is not one — it is the absence of a finite size — and the whole of Cantor’s contribution was to notice that there is a workable notion of same size for infinite collections, namely one-to-one correspondence, and that under it not all infinite collections match. The fractions can be listed and the sequences cannot, and both facts are proved with the same standard of proof.

“The diagonal sequence is not really a sequence.” It is: its $n$th entry is defined for every $n$, by a rule referring to the list, and nothing more is required of a sequence than that. If the objection is that the rule refers to the whole list at once, then the objection is to infinite objects generally, which is a coherent position — it is roughly the constructivist one — and it rejects far more than this argument.

That last objection is the only one that goes anywhere, and where it goes is a different mathematics rather than a mistake in this one. A logic that declines to assume every question is already settled treats the diagonal argument as establishing something weaker: not that an uncountable set exists, but that no listing can be complete, which is a statement about listings. The construction survives; what changes is what it is taken to have shown.

That is the right note to end on, because it is unusual. Most results in mathematics are either accepted or refuted, and this one has instead been re-read several times without ever being doubted as a piece of arithmetic. Every school of foundations agrees that the flipped diagonal differs from row $n$ at place $n$; they disagree about what follows, and the disagreement is about what kind of object a completed list is. A theorem whose content everybody accepts and whose meaning is still argued about is a rarer thing than a hard theorem, and it is worth recognising on sight.