Berry paradox
|
|
The Berry paradox arises when one attempts to evaluate expressions like the following:
- The smallest positive integer not nameable in under eleven words.
It is reasonable to assume that this is a specification for a number: after all, there are a finite number of sentences of less than eleven words, and some finite subset of them specify unique positive integers, so there is clearly some positive number that is the smallest integer not in that finite set.
But the Berry sentence itself is a specification for that number in only ten words!
This is clearly paradoxical, and seems to indicate that "nameable in under eleven words" is not cleanly enough defined. Using programs or proofs of bounded lengths, one may in fact construct a rigorous version of the paradox; this has been done by Gregory Chaitin in order to produce an incompleteness theorem similar in spirit to Gödel's incompleteness theorem; see algorithmic information theory for an exposition.
The Berry paradox was actually created by Bertrand Russell, who named it after G. G. Berry. Berry had provided the original idea in a letter to Russell about the less specific "the first ordinal that cannot be named in a finite number of words".
Other versions of the Berry paradox exist as well, including the following:
- The smallest positive integer that requires more characters than there are in this sentence to be specified.
- The smallest positive integer not nameable in under one billion words.
- The first number not nameable in under ten words.
| Contents |
Solutions
It is generally accepted that the Berry paradox and its ilk hang on underdetermined language. That is, "not nameable in fewer than n words" is not well-defined, for several reasons. First, the number of words in which a thing is nameable is surely relative to the language in which it is named. So we might attempt to prop up the paradox as follows: "The smallest number not nameable in English in fewer than thirteen words" (adjusting word counts as the length of the expression requires). But this is not really enough either, because we can name any number in as few words as we want, just by stipulation. Pick out whatever number you want using as long an expression as you need, and declare, "I shall henceforth call that number Jones." Now you can ask whether Jones is odd, or even, or prime, and name it using only one word.
We can invent new words in this way whenever we please. Yet it is a well known fact that there are more numbers than there are possible names in any language, so given any vocabulary there must be some number it cannot name in less than n words, for any n.
The real problem, then, is that the paradox must be formulated relative to a fixed vocabulary. So we might say, "The smallest number that cannot be named, by the totality of English that existed by the end of December 31, 1999, in fewer than twenty-eight words." (counting 31, 1999, twenty, and eight each as a single word.)
However, it was shown by Tarski that certain predicates, such as the truth-predicate for a language, can be formulated coherently only in a richer language than the one they apply to, a metalanguage. That is, the above predicate can only exist without contradiction in a language other than "the totality of English that existed by December 31, 1999." So the "paradox" expression is not in fact a counterexample to the condition it states.
(A minor quibble is that "the smallest number not nameable in fewer than eleven words" is not a name at all but a description. The paradox easily accommodates this with, "the smallest number not denotable by any expression of fewer than fourteen words." The solution is similar.)
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
See also
External links
- http://www.cs.auckland.ac.nz/CDMTCS/chaitin/unm2.html A discussion by Gregory Chaitin
- http://www.cs.yorku.ca/~peter/Berry.html
- http://mathworld.wolfram.com/BerryParadox.html The entry for the Berry paradox at Wolfram Research's MathWorld
- http://www.hgsc.bcm.tmc.edu/~kdurbin/texts/alg.info.chiatin.htmlhe:הפרדוקס של ברי
ja:ベリーのパラドックス pl:Paradoks nieciekawej liczby it:Paradosso di Berry