Berry’s Paradox and Gödel’s Incompleteness Theorem

 

A young librarian at the Bodleian Library in Oxford devised an intriguing paradox. He defined a number by means of a statement of the form

THE SMALLEST NATURAL NUMBER THAT CANNOT BE
DEFINED IN FEWER THAN TWENTY WORDS.

This appears to indicate a specific positive integer, which we denote . But there is a problem: the statement contains only thirteen words. Thus, has been defined by a statement of fewer than twenty words, contradicting the definition itself!

This problem was first discussed in the open literature around 1908 by the British mathematician and philosopher Bertrand Russell. Russell had heard about it from the librarian, a Mr. G. G. Berry, after whom the paradox is now named (as is well known, Russell has another — totally different — paradox named after him).

Even if we admit the most obscure words, there are a finite number of words in the English language. Once a maximum word-length is set, let us say letters, the number of possible strings up to this length is a finite number where is the number of symbols in the alphabet. With this limitation, at most distinct numbers can be defined by sentences of not more than twenty words. Since there are numbers not included in this set, there must exist a smallest such number, or Berry’s Number.

Berry’s paradox arises from ambiguities in the meaning of the words used in his statement. American philosopher and logician Willard Quine proposed a resolution of the paradox by introducing a stratification of terms used in the definition, certain terms having multiple levels of meaning.

The Connection with Incompleteness

According to mathematician Gregory Chaitin, a letter from Berry to Russell actually asks about “The first ordinal that cannot be named in a finite number of words”. This statement leads to a contradiction similar to the statement considered above.

In an interesting article entitled Berry’s Paradox (1995), Chaitin described his interactions (via telephone) with Kurt Gödel. in 1931, Gödel had shown the essential incompleteness of mathematics: no matter what system of axioms we adopt, there are always true results that cannot be proved. Extending the axiom system to include them inevitably introduces new unprovable statements.

Gödel derived his incompleteness theorem starting from the “liar paradox”:

THIS STATEMENT IS FALSE.

He managed to modify this statement so that it became

THIS STATEMENT IS UNPROVABLE.

He then constructed a well-defined statement that is true but unprovable.

Chaitan took a similar approach but started from Berry’s Paradox in a form like

THE FIRST POSITIVE INTEGER THAT CANNOT BE
SPECIFIED IN FEWER THAN ONE BILLION WORDS.

Chaitin then followed a line of reasoning similar to Gödel’s and reached a similar conclusion about the incompleteness of his system. Moreover, he developed a general theory dealing with computer program size and complexity, that he called Algorithmic Information Theory.

A Simple Incompleteness Proof by George Boolos

A version of Berry’s Paradox was used by MIT philosopher George Boolos to prove Gödel’s Incompleteness Theorem. He considered the set

{(N,K) : N has a definition using K symbols}

This can be represented by a Gödel number. Then, the proposition

[M is the least number not definable in fewer than K symbols]

can be shown to be a well-formed definition. But, clearly, if such a number is assumed to exist, a contradiction cannot be avoided.

*         *         *

Is it not amazing that such profound consequences follow from a simple — almost playful — puzzle dreamt up by the junior librarian, G. G. Berry?

Sources

Boolos, George, 1989: A new proof of the Gödel Incompleteness Theorem, Not. Amer. Math. Soc., 36, 388-390; 676. PDF.

Chaitin, Gregory, 1995: The Berry Paradox. Complexity, 1, 26-30. Here.

Wikipedia article Berry’s Paradox