Berry paradox
The Berry paradox is a
Bertrand Russell, the first to discuss the paradox in print, attributed it to G. G. Berry (1867–1928),[1] a junior librarian at Oxford's Bodleian Library. Russell called Berry "the only person in Oxford who understood mathematical logic".[2] The paradox was called "Richard's paradox" by Jean-Yves Girard.[3]
Overview
Consider the expression:
- "The smallest positive integernot definable in under sixty letters."
Since there are only twenty-six letters in the English alphabet, there are finitely many phrases of under sixty letters, and hence finitely many positive integers that are defined by phrases of under sixty letters. Since there are infinitely many positive integers, this means that there are positive integers that cannot be defined by phrases of under sixty letters. 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 sixty letters". This is the integer to which the above expression refers. But the above expression is only fifty-seven letters long, therefore it is definable in under sixty letters, and is not the smallest positive integer not definable in under sixty letters, 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 definable in under sixty letters), there cannot be any integer defined by it.
Mathematician and computer scientist Gregory Chaitin in The Unknowable (1999) adds this comment: "Well, the Mexican mathematical historian Alejandro Garcidiego has taken the trouble to find that letter [of Berry's from which Russell penned his remarks], and it is rather a different paradox. Berry’s letter actually talks about the first ordinal that can’t be named in a finite number of words. According to Cantor’s theory such an ordinal must exist, but we’ve just named it in a finite number of words, which is a contradiction."
Resolution
The Berry paradox as formulated above arises because of systematic ambiguity in the word "definable". In other formulations of the Berry paradox, such as one that instead reads: "...not nameable in less..." the term "nameable" is also one that has this systematic ambiguity. Terms of this kind give rise to vicious circle fallacies. Other terms with this type of ambiguity are: satisfiable, true, false, function, property, class, relation, cardinal, and ordinal.[4] 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.
This family of paradoxes can be resolved by incorporating stratifications of meaning in language. Terms with systematic ambiguity may be written with subscripts denoting that one level of meaning is considered a higher priority than another in their interpretation. "The number not nameable0 in less than eleven words" may be nameable1 in less than eleven words under this scheme.[5]
However, one can read
However, this system is incomplete. One would like to be able to make statements such as "For every statement in level α of the hierarchy, there is a statement at level α+1 which asserts that the first statement is false." This is a true, meaningful statement about the hierarchy that Tarski defines, but it refers to statements at every level of the hierarchy, so it must be above every level of the hierarchy, and is therefore not possible within the hierarchy (although bounded versions of the sentence are possible).[6][7] Saul Kripke is credited with identifying this incompleteness in Tarski's hierarchy in his highly cited paper "Outline of a theory of truth,"[7] and it is recognized as a general problem in hierarchical languages.[8][7]
Formal analogues
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.[9]
Relationship with Kolmogorov complexity
It is not possible in general to unambiguously define what is the minimal number of symbols required to describe a given string (given a specific description mechanism). In this context, the terms string and number may be used interchangeably, since a number is actually a string of symbols, e.g. an English word (like the word "eleven" used in the paradox) while, on the other hand, it is possible to refer to any word with a number, e.g. by the number of its position in a given dictionary or by suitable encoding. Some long strings can be described exactly using fewer symbols than those required by their full representation, as is often achieved using data compression. The complexity of a given string is then defined as the minimal length that a description requires in order to (unambiguously) refer to the full representation of that string.
The Kolmogorov complexity is defined using
See also
- Bhartrhari's paradox, a 1981 paper on Bhartṛhari's 5th century discussion of self-referential paradox, including the fact that stating something to be unnameable makes it nameable
- Busy beaver – Longest-running turing machine of a given size
- Chaitin's incompleteness theorem– Measure of algorithmic complexity
- Definable real number – Real number uniquely specified by description
- Hilbert–Bernays paradox – limit of classical logic
- Interesting number paradox – On the smallest non-interesting number
- Paradoxes of set theory
- Richard's paradox – Apparent contradiction in metamathematics
Notes
- ^ Griffin 2003, p. 63.
- ^ Moore 2014, Appendix IV.
- ^ Girard 2011, p. 16.
- ^ Russell & Whitehead 1927.
- ^ Quine 1976, p. 10.
- ^ Kripke 1975.
- ^ a b c Beall, Glanzberg & Ripley 2016
- ^ Glanzberg 2015.
- ^ Chaitin 1995.
References
- Beall, Jc; Glanzberg, Michael; Ripley, David (December 12, 2016). "Liar Paradox". In Zalta, Edward N. (ed.). Stanford Encyclopedia of Philosophy.
- MR 1366300.
- ISBN 9783037190883.
- Glanzberg, Michael (2015). "Complexity and hierarchy in truth predicates". In Achourioti, Theodora; Galinon, Henri; Fernández, José Martínez; Fujimoto, Kentaro (eds.). Unifying the Philosophy of Truth. Logic, Epistemology, and the Unity of Science. Vol. 36. Dordrecht: Springer. pp. 211–243. ISBN 978-94-017-9672-9.
- Griffin, Nicholas (2003). The Cambridge Companion to Bertrand Russell. Cambridge University Press. ISBN 978-0-521-63634-6.
- JSTOR 2024634.
- Moore, Gregory H. (2014). The Collected Papers of Bertrand Russell, vol. 5. Routledge. ISBN 9780415820981.
- ISBN 9780674948358.
- Whitehead, Alfred N. (1927). Principia Mathematica. Cambridge University Press.
Further reading
- Bennett, Charles H. (1979). "On Random and Hard-to-Describe Numbers". IBM Report RC7483. CiteSeerX 10.1.1.27.3492.
- Boolos, George (1989). "A New Proof of the Gödel Incompleteness Theorem". Notices of the American Mathematical Society. 36: 388–390, 676.
Reprinted in Boolos (1998, pp. 383–388)
- ISBN 0-674-53766-1.
- French, James D. (1988) "The False Assumption Underlying Berry's Paradox," Journal of Symbolic Logic 53: 1220–1223.
- Russell, Bertrand (1906) "Les paradoxes de la logique", Revue de métaphysique et de morale 14: 627–650
External links
- Roosen-Runge, Peter H. (1997) "Berry's Paradox."
- Weisstein, Eric W. "Berry Paradox". MathWorld.