The word that cannot describe itself

The diagonal has been used three times so far, on three tables. On a list of infinite sequences it built a sequence the list misses. On the table of which sets contain which it built Russell’s set, which cannot be a set. On the table of which sentences are provable it built a sentence that says it has no proof. Each time the table had the same objects along both edges, and each time the diagonal, flipped, was something the table could not contain.

There is a fourth table that is older than the last two in spirit and newer in date, and it is the most ordinary of all. Its rows and columns are words, and its cells record whether a word describes a word. The paradoxes that come from it — Grelling’s, Richard’s, Berry’s — sound like puzzles about language rather than mathematics, and for a few years after 1905 they were treated as a crisis on a par with Russell’s. What they turned out to prove is a precise theorem: no language can define, inside itself, its own relation of describing, naming or being true. Alfred Tarski made that exact in 1933, and the diagonal is the whole of his proof.

A table of adjectives #

Take some adjectives whose meaning can be checked by looking at a word’s letters: short (at most five letters), lengthy (at least eight), vowelless, unhyphenated, double-lettered (a letter twice running), and a few more. Each is itself a written word, so each can be applied to each.

Some adjectives describe themselves. Short has five letters and is short. Unhyphenated has no hyphen. Double-lettered has two t’s together. E-bearing contains an e. These are called autological. The rest do not: lengthy has seven letters, so it is not lengthy; vowelless has vowels; seven-lettered, with thirteen letters, is not seven-lettered. Those are heterological.

Now read the bottom row of the figure. It marks, for each column, whether that adjective is heterological — the diagonal with every entry flipped. That row differs from the row of short in the column short, from the row of lengthy in the column lengthy, and from every row in its own column. So no adjective in the table has that row: no adjective in the list means “heterological”. The table is small, but the argument used nothing about its size or its contents.

Kurt Grelling and Leonard Nelson published the paradox in 1908 in the form of a question: is the word heterological heterological? If it is, it describes itself, so it is autological. If it is not, it does not describe itself, so it is heterological. The contradiction is the diagonal, and what it proves is not that language is broken but that heterological cannot be an adjective of the kind the table lists — one whose applicability to a word is settled by a rule the table can record — unless the language can also say what its own adjectives mean. The question “does this word describe that one?” has moved inside the language, and the diagonal is waiting there.

A number named by the diagonal of names #

Jules Richard found the version for numbers in 1905, and it was the one that worried mathematicians most, because it seemed to threaten the real numbers themselves.

List every phrase of English that names a number between $0$ and $1$ — shortest phrases first, and alphabetically among phrases of the same length. The list is countable, since there are only finitely many phrases of each length. Write each named number’s decimal digits along its row, and build a new number by changing the diagonal: its $n$-th digit is $5$ unless the $n$-th named number’s $n$-th digit is $5$, in which case it is $4$. The new number differs from every named number, so it is on no row. But the sentence just written describes it in a finite number of words, so it is named, so it is on some row. Contradiction.

Richard’s own resolution, and Poincaré’s, was that the phrase describing the new number refers to the whole list of named numbers, and so is illegitimately circular. That is the right diagnosis, stated vaguely. The precise version is that the phrase uses the notion “the number named by phrase $n$” — the naming relation of the language — and the diagonal shows that this relation cannot be expressed by a phrase of the language itself. If it could, the diagonal phrase would be an ordinary phrase, on the list, and it would differ from itself in its own digit.

How many numbers short phrases can name #

George Berry, an Oxford librarian, gave Bertrand Russell the shortest version in 1906, and it needs no table at all, only a count.

With twenty-seven characters there are fewer than $27^{90}$ strings of under ninety characters, so fewer than $27^{90}$ phrases, so they name at most that many whole numbers. There are infinitely many whole numbers, so some are named by no short phrase, and among those there is a smallest. It is the smallest whole number not named by any phrase of fewer than ninety characters — and that phrase has eighty-one characters. The number has been named by a short phrase after all.

The count is correct and so is the phrase’s length. What fails is the assumption that “named by” is a relation the phrases of the language can themselves refer to. Every step of Berry’s argument is fine about English; the last step uses English’s naming relation in English. That is the same step Richard took, stripped of the digits, and the same step Grelling took, stripped of the adjectives.

One structure under three paradoxes #

Put the three side by side and the shared shape is exact. Each has a language, a relation between its expressions and the things they are about — an adjective applies to a word, a phrase names a number — and a question the language asks about that relation. And each time the diagonal produces an expression whose meaning is defined through the relation applied to itself, with a flip: the adjective that applies to exactly the adjectives that do not apply to themselves; the number that differs from each named number in its own place; the number that no short phrase names.

In every case the conclusion is the same: if a language could express its own naming relation, the diagonal would produce an expression that both does and does not stand in that relation to itself. So no language can. The paradoxes are not puzzles about English’s untidiness; they are three proofs of one impossibility, each disguised as a contradiction because each assumed at the start what it ends by refuting.

That is also exactly the structure of the incompleteness argument, with one difference that matters. There the relation was provability, which a formal system can express, because checking a proof is a mechanical matter of matching symbols; the diagonal then produces a true sentence that is unprovable, rather than a contradiction. Here the relations are naming and describing and, underneath both, truth — and those a language cannot express at all, so the diagonal produces a contradiction and the conclusion is that the relation is not in the language. Gödel’s sentence exists because provability is definable; the paradoxes are impossible because truth is not.

Self-reference that does no harm #

It would be a mistake to read the paradoxes as a verdict against self-reference, and the table shows why. Short describes itself, and nothing goes wrong: the question “is short short?” has an answer that is settled by counting letters, and the answer does not depend on the answer. Self-reference is harmless whenever the property being applied can be checked without consulting the table it sits in. The sentence this sentence has seven words refers to itself and is simply true, because counting words does not involve truth.

The trouble starts only when two ingredients meet: a property defined through the language’s own semantic relation — describing, naming, being true — and a flip. Drop the flip and the result is odd but not contradictory. The sentence this sentence is true, the truth-teller, can consistently be declared true and can consistently be declared false; nothing forces either, and in Kripke’s construction below it is left with no value at all, because its truth depends only on its own truth and so is never grounded in anything else. Drop the semantic relation instead and keep the flip — this sentence does not have seven words — and the sentence is merely false. The liar needs both: it applies the language’s truth relation to itself, and negates.

The diagonal is exactly that combination. A table of objects against themselves supplies the self-application; the flip supplies the negation; and the conclusion is that the relation in the table cannot be one the language contains. Every diagonal argument in this subject has the same two ingredients, and every escape from the paradoxes removes one of them.

Truth, one level up #

Tarski stated the conclusion for truth, which is the relation behind the other two. For a formal language rich enough to talk about its own sentences — arithmetic is enough — there is no formula $T(x)$ in the language such that, for every sentence $\sigma$, $T(\ulcorner \sigma \urcorner)$ holds exactly when $\sigma$ is true. The proof is the fixed-point lemma applied to $\neg T$: it produces a sentence $\lambda$ equivalent to $\neg T(\ulcorner\lambda\urcorner)$, which says of itself that it is not true — the liar, made exact — and $T$ cannot be right about it.

What can be done is to define truth one level up. A language $L_1$ that contains all of $L_0$ plus a predicate for “true sentence of $L_0$” can define $L_0$’s truth perfectly well — the definition is the familiar clause-by-clause one, a conjunction is true when both parts are, a universal statement when every instance is. But $L_1$ has new sentences, involving its new predicate, and their truth needs $L_2$. The grid is Tarski’s hierarchy of languages: each defines truth for everything below, and the diagonal — a language defining its own truth — is the one place the grid must be empty. The empty diagonal is the table-shaped statement of the theorem, and it is the same shape as every diagonal before it, with the entries that would make trouble removed rather than flipped.

Mathematicians work this way without noticing. Truth in arithmetic is defined in set theory, which is a larger language; truth in set theory, if it is needed, in a larger one still. Each theory is described from outside, by a theory with more resources. The paradoxes arise only when a theory is asked to describe itself from inside.

Other ways out, and what they cost #

Tarski’s hierarchy is not the only escape, and the alternatives are instructive about what exactly the diagonal forbids. Saul Kripke showed in 1975 that a language can contain its own truth predicate if the predicate is allowed to be partial: some sentences are declared true, some false, and some — the liar among them — neither. Build the predicate in stages, each stage deciding the sentences whose truth depends only on sentences already decided, and it settles at a fixed point in which every grounded sentence has its correct value and the liar has none. The diagonal still applies; it forces the liar into the gap, and the cost is that the language cannot say the liar is in the gap, since “not true” would then apply to it.

Russell’s own response to all of these, including his own paradox, was the theory of types: every expression has a level, and an expression may only talk about expressions of lower level. That is Tarski’s hierarchy imposed on every predicate rather than only on truth, and it is the repair Russell reached for after his postcard to Frege. Modern set theory takes a third route, restricting which collections count as sets rather than which expressions count as meaningful. Each escape removes the diagonal’s premise in a different place: the hierarchy denies that the relation is in the language, Kripke denies that it is total, types deny that expressions can refer to their own level.

The numbers nobody can name #

The counting behind Richard’s and Berry’s paradoxes has a consequence that survives the paradoxes intact. The phrases of any language are countable, so the numbers they name are countable, and the real numbers are not. So almost every real number cannot be named by any phrase in any language — the nameable ones form a countable set, of measure zero, in a line that is uncountable.

The two arguments — Cantor’s and Richard’s — are the same construction, and the figure is the one to hold beside Richard’s table. Applied to the list of nameable numbers from outside, by someone who can see the whole list and is not claiming the resulting number has a name in the list’s language, the diagonal simply proves that the list misses something: there is a real number no phrase names. Applied from inside, by a phrase of the language that tries to name the missed number, it produces a contradiction. The difference is only in who is doing the naming. Outside the language, “the diagonal of the list of named numbers” is a perfectly good description, in a richer metalanguage, of a perfectly good number — one that the object language cannot name. Inside, it is Richard’s paradox.

That is Tarski’s hierarchy again, seen from the side of the numbers rather than the sentences. A real number is nameable or not relative to a language. Every language leaves most numbers unnamed, a richer language names some of those, and no language names them all, because the diagonal of any language’s list is nameable only one level up.

That sounds like it should allow an example: “the first real number that cannot be named”. It does not, and the reason is Richard’s paradox itself. Any attempt to single out an unnameable number by a phrase names it, so the diagonal forbids exactly the demonstration the counting suggests should be easy. The unnameable numbers exist in overwhelming abundance, and every one of them is, individually, impossible to point to — a situation with close relatives in choices nobody can write down, where objects exist by an argument that cannot produce any of them.

What the tables cannot show #

They cannot show a real language. The adjectives in the first table were chosen because their meanings can be checked by looking at letters; most adjectives in English cannot, and the table of all of them is not a finite object anyone can draw. The figure shows the argument on a table where everything is decidable, which is the honest way to show that the argument does not depend on anything undecidable.

They cannot show that the phrases really name. The eight phrases in Richard’s table name numbers because their meanings are fixed by ordinary mathematics; a list of every phrase that names a number would need a notion of naming, which is exactly what the argument shows cannot be defined inside the language doing the naming.

And the hierarchy grid is a diagram of a theorem, not a computation. The cells are marked by the rule that a language defines truth for those strictly below it; that the diagonal must be empty is Tarski’s theorem, argued above, and no finite grid could establish it.

Where the diagonal goes next #

Four tables, four conclusions, one move. The table of sequences cannot list them all; the table of sets cannot contain its own diagonal set; the table of sentences cannot prove its own diagonal sentence; the table of words cannot name its own naming. Lawvere showed in 1969 that all four are one theorem about fixed points, read backwards.

What remains is to turn the diagonal round and use it to build. The same fixed-point construction that produces the liar produces, in a system that can express provability, sentences that say anything at all about themselves: that they are provable, that they are short, that they are true in some model. Which of those self-referential sentences are provable is not decided by the diagonal alone, and the answers — some surprising — belong to the logic of provability, where necessity means provable.

A relation no language holds #

The paradoxes of Grelling, Richard and Berry are diagonal arguments on a table of words describing words. Each assumes that a language can express its own relation of describing or naming, builds from that relation’s flipped diagonal an expression that must both stand and not stand in the relation to itself, and so refutes the assumption. Tarski’s theorem is the exact form: no language rich enough to talk about its sentences can define its own truth.

Truth can be defined one level up, and Tarski’s hierarchy of languages is the grid with its diagonal left empty; Kripke’s partial truth predicate and Russell’s types are other ways of removing the diagonal’s premise. And because the phrases of any language are countable, almost every real number can be named by none of them — while the diagonal forbids naming any particular one of the unnameable.

When a language talks about itself, ask whether the relation it uses is one the language can contain — if the diagonal can be run on it, it cannot.