Berry paradox

From Wikipedia, the free encyclopedia

The Berry paradox is the apparent contradiction that arises from expressions such as the following:

The smallest positive integer not definable in under eleven words.

For the sake of simplicity, we assume here that hyphenated words like "self-evident" do not count as a single word but as several words ("self" and "evident").

We can argue that this phrase specifies a unique integer as follows: there are finitely many phrases of fewer than eleven words. Some of these phrases denote a unique integer: For example, "one hundred thirty six", "the smallest prime number greater than five hundred million" or "ninety raised to the centillionth power". On the other hand, some of these phrases denote things which are not integers: For example "Miguel de Cervantes" or "Mount Kilimanjaro." In any case, the set A of integers that can be uniquely specified in under eleven words is finite. Since A is finite, not every positive integer can be in A. Thus by well-ordering of the positive integers, there is a smallest positive integer that is not in A.

But the Berry expression itself is a specification for that number in only ten words!

This is clearly paradoxical, and would seem to suggest that "definable in under eleven words" may not be well-defined. However, using programs or proofs of bounded lengths, it is possible to construct an analogue of the Berry expression in a formal mathematical language, as has been done by Gregory Chaitin. Though the formal analogue does not lead to a logical contradiction, it does prove certain impossibility results, including an incompleteness theorem similar in spirit to Gödel's incompleteness theorem; see Kolmogorov complexity for details.

The Berry paradox was proposed by Bertrand Russell (Russell, 1906). He attributed it to G. G. Berry of the Bodleian library (cf. Russell and Whitehead 1910), who had suggested the idea of considering the paradox associated to the expression "the first undefinable ordinal".

1 Resolution of the paradox
2 References
3 See also
4 External links

[edit] Resolution of the paradox

It is generally accepted that the Berry paradox and other similar paradoxes (such as Richard's paradox) result from interpreting sets of possibly self-referential expressions. According to (Russell and Whitehead, 1910) these paradoxes "embody vicious circle fallacies". To resolve one of these paradoxes means to pinpoint exactly where our use of language went wrong and to provide restrictions on the use of language which may avoid them.

Note that some Berry type expressions present only minor problems of interpretation:

The smallest positive integer not definable in under two words.

under reasonable definitions of English denotes 21, since "twenty one" (or "twenty-one") is two words and any indirect definition of the number (such as "the number of dots on a six-sided die", or indeed "the smallest positive integer not definable in under two words") is necessarily two or more words long.

However, Berry's paradox can be forced into a formal system. George Boolos used a specific formalization to provide an alternate proof of Gödel's Incompleteness Theorem. The basic idea of the proof is that a proposition that holds of x if x = n for some natural number n can be called a definition for n, and that the set {(n, k): the natural number n has a definition in this sense that is k symbols long} can be shown to be representable (using Gödel numbers). Then the proposition "m is the first number not definable in under k symbols" can be formalized and shown to be a definition in this sense.

[edit] References

Charles H. Bennett, On Random and Hard-to-Describe Numbers, IBM Report RC7483 (1979)
http://www.research.ibm.com/people/b/bennetc/Onrandom.pdf
George Boolos, A new proof of the Gödel Incompleteness Theorem. Notices of the American Mathematical Society, 36(4), pp. 388-390.
Bertrand Russell, Les paradoxes de la logique, Revue de métaphysique et de morale, vol 14, pp 627-650
Bertrand Russell and Alfred N. Whitehead, Principia Mathematica, Cambridge University Press/ A paperback reissue up to *56 was published in 1962.