Berry's Paradox: Naming the Unnameable in 57 Letters

Thank you for visiting this site. This article covers “Berry’s Paradox.”

Consider the phrase “the smallest positive integer not definable in under sixty letters.” Such a number genuinely exists — but look closely and the phrase itself is only 57 letters long. We have just defined, in under sixty letters, a number that is not supposed to be definable in under sixty letters. It is a famous puzzle found by an Oxford librarian and introduced to the world by Russell.

Numbers you cannot name briefly

Start with naming positive integers in English.

“Three” names 3 in five letters. “One million” gets to 1,000,000 in ten. “Two to the tenth power” reaches 1,024 in eighteen. With a little ingenuity, quite large numbers can be reached in very few letters.

But put a ceiling on the letters you may use and the numbers you can reach become limited too. Let us set that ceiling at sixty.

So: is there “a positive integer that cannot be defined, by any means, in under sixty letters”? If there is, then among all such numbers exactly one must be the smallest.

To pick that number out, we write:

the smallest positive integer not definable in under sixty letters

Count the letters and the phrase comes to exactly 57. Comfortably under sixty.

In short, this number is supposed to be undefinable in under sixty letters, and we have just defined it in 57.

Does such a number really exist?

Let me close off one escape route first: “perhaps no such number exists.”

The English alphabet has finitely many letters. Strings of fewer than sixty letters therefore number, at the very most, 26 to the 60th power. An unimaginably large figure, but still finite.

The positive integers, by contrast, are infinite. Finitely many phrases cannot name infinitely many numbers, so some numbers are necessarily left over: “numbers not definable in under sixty letters.”

And any non-empty collection of positive integers has a least element. That is a basic property of the integers.

So the number in question definitely exists. It exists, and the moment you name it, it contradicts itself. That is what makes it awkward.

Where the contradiction actually happens

The weak point in the argument is the word “definable” itself.

The argument above proceeded as if what each phrase of under sixty letters denotes could be settled one by one. But “the smallest positive integer not definable in under sixty letters” is itself a phrase of under sixty letters.

Which means that to settle what this phrase denotes, what every phrase under sixty letters denotes must already be settled. Including this one.

To determine what it refers to, you must already know what it refers to. That is a circle, and it is exactly the same structure that jams the liar paradox at “this sentence is false.”

Put differently, what this argument demonstrates is not a contradiction about the integers. It is the fact that the word “definable” cannot be defined inside the language it belongs to.

The librarian Berry, and Russell

G. G. Berry, whose name is on the paradox, was not a mathematician but a librarian at Oxford’s Bodleian Library.

He set the problem out in a letter to Bertrand Russell. Russell presented it in a 1908 paper and named Berry explicitly as its originator, which is why it has been Berry’s paradox ever since.

Russell at the time was in the middle of the problem his own paradox had opened in the foundations of set theory. The contradiction arising from “the set of all sets not containing themselves” and Berry’s contradiction are of different kinds.

Russell’s paradox occurs in a mathematical object, a set; Berry’s occurs on the side of what the word “define” means. The two are usually distinguished as logical paradoxes and semantic paradoxes respectively.

The slipperiness of “definable”

For the semantic paradoxes, Alfred Tarski gave the decisive treatment in the 1930s.

What Tarski showed is that the concept of “true” for a language cannot be defined within that same language. Attempt it and contradiction is guaranteed.

Handling truth requires a language one level up. Handling the truth of that language requires another level above it. Split language into a hierarchy and the circle never closes.

The “definable” of Berry’s paradox gets exactly the same treatment. The problem was trying to talk about English’s expressive power from inside English; viewed from outside, the contradiction is gone.

When I first met this resolution it felt a little like dodging the question, but on reflection it is also the entirely ordinary point that “a ruler cannot measure itself”, and these days it strikes me as the natural conclusion.

The use Chaitin found for it

The interesting part is that this paradox was later turned into a powerful tool.

In the 1970s Gregory Chaitin formalised Berry’s paradox and used it to prove his own incompleteness theorem. The insight was to replace “not briefly definable” with “not producible by a short program.”

Take the length of the shortest program that outputs a number as that number’s complexity. It then follows that complexity above a certain threshold cannot be proved within the system.

A system has a ceiling above which it cannot measure its own limits. It amounts to restating Gödel’s incompleteness theorem from the angle of quantity of information.

A librarian’s piece of wordplay turned into a theorem about the limits of computation. Paradoxes are not only for breaking things; sometimes they become instruments. This is a good example.

Ramsey’s split into two kinds

It was the British mathematician Frank Ramsey who fixed Berry’s paradox in its place, classifying contradictions arising from self-reference into two types in 1926.

Logical versus semantic

The criterion for splitting them is whether the material of the contradiction sits inside mathematics or on the side of language.

Logical paradoxes break the foundations of mathematics itself, so the axioms have to be rewritten. Semantic paradoxes only arise when language tries to speak about its own meaning. Mathematics is untouched, so tidying up how language is handled suffices.

Others of the same type

Berry has several close relatives among the semantic paradoxes.

• Richard’s paradox (1905): from a list of all definable real numbers, build by diagonalisation a real number that is not on the list
• The Grelling–Nelson paradox (1908): call an adjective that does not apply to itself “heterological.” Is the word “heterological” heterological?

Grelling’s version is the easiest to feel. “Short” is a short word, so it is autological; “long” is not a long word, so it is heterological. What about “heterological” itself?

If it applies it does not, and if it does not it does. Exactly the same jam as Berry. Meaning failing to settle the moment a word points at itself turns out to be that common.

Related paradoxes of self-reference

Related paradoxes where meaning collapses the moment something tries to speak about itself.

Summary

This article covered “Berry’s Paradox.”

A number that cannot be named briefly, named briefly. The real source of the contradiction is not the integers but the fact that the word “definable” counted itself among the things it was ranging over.

Less a mathematical argument than a question about how far you can trust your own use of language. Falling into a bottomless problem just by counting to 57 is, I think, what makes this paradox so satisfying.

To return to the full list of paradoxes, follow the link below.

Thank you for reading. We hope to see you in the next article.

World Paradoxes: The Complete List, Explaineden.senkohome.com/paradox-list/