Berry paradox

From Wikipedia, the free encyclopedia

The Berry paradox is a paradox that arises from self-referential expressions about the smallest possible integer which can be composed in a certain number of words. It was proposed by Bertrand Russell who attributed it to G. G. Berry, a librarian at the Bodleian in Oxford, who had suggested the idea of considering the more limited paradox associated with the expression "the first undefinable ordinal".

1 The paradox
2 Resolution
3 References
4 See also
5 External links

[edit] The paradox

Consider the following expression:

The smallest positive integer not definable in under eleven words.

Since there are finitely many words, there are finitely many phrases of under eleven words, and hence finitely many positive integers that are defined by phrases of under eleven words. Since there are infinitely many positive integers, this means that there are positive integers that cannot be defined by phrases of under eleven words — that is, positive integers satisfying the property "not definable in under eleven words". By the well ordering principle, if there are positive integers that satisfy a given property, then there is a smallest positive integer that satisfies that property; therefore, there is a smallest positive integer satisfying the property "not definable in under eleven words". This is the integer to which the above expression refers; that is, this integer is defined by the above expression. But note that the above expression is only ten words long; so, this integer is defined by an expression that is under eleven words long; so it is definable in under eleven words, and is not the smallest positive integer not definable in under eleven words, and is not defined by this expression. This is a paradox: there must be an integer defined by this expression, but since the expression is self-contradictory (any integer it defines is, clearly, definable in under eleven words), there cannot be any integer defined by it.

[edit] Resolution

It is generally accepted that the Berry paradox results from interpreting sets of possibly self-referential expressions: it and similar paradoxes embody so-called "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.

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.

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.

The validity of the paradox was challenged in a paper in the Journal of Symbolic Logic, Volume 53, Number 4, Dec. 1988. See External links below.

[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.