View source for Berry paradox

{{short description|Self-referential paradox}}
The '''Berry paradox''' is a [[self-referential]] [[paradox]] arising from an expression like "The smallest positive integer not definable in under sixty letters" (a phrase with fifty-seven letters).

[[Bertrand Russell]], the first to discuss the paradox in print, attributed it to G. G. Berry (1867–1928),{{sfn|Griffin|2003|p=63}} a junior [[librarian]] at [[University of Oxford|Oxford]]'s [[Bodleian Library]]. Russell called Berry "the only person in Oxford who understood mathematical logic".{{sfn|Moore|2014|loc=Appendix IV}} The paradox was called "[[Richard's paradox]]" by [[Jean-Yves Girard]].{{sfn|Girard|2011|p=16}}

== Overview ==
Consider the expression:

:"The smallest [[Positive number|positive]] [[integer]] not 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 [[name]]able in less..." the term "nameable" is also one that has this systematic ambiguity. Terms of this kind give rise to [[vicious circle principle|vicious circle]] fallacies. Other terms with this type of ambiguity are: satisfiable, true, false, function, property, class, relation, cardinal, and ordinal.{{sfn|Russell|Whitehead|1927}} 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 nameable<sub>0</sub> in less than eleven words" may be nameable<sub>1</sub> in less than eleven words under this scheme.{{sfn|Quine|1976|p=10}}

However, one can read [[Alfred Tarski]]'s contributions to the [[Liar Paradox]] to find how this resolution in languages falls short. Alfred Tarski diagnosed the paradox as arising only in languages that are "semantically closed", by which he meant a language in which it is possible for one sentence to predicate truth (or falsehood) of another sentence in the same language (or even of itself). To avoid self-contradiction, it is necessary when discussing truth values to envision levels of languages, each of which can predicate truth (or falsehood) only of languages at a lower level. So, when one sentence refers to the truth-value of another, it is semantically higher. The sentence referred to is part of the "object language", while the referring sentence is considered to be a part of a "meta-language" with respect to the object language. It is legitimate for sentences in "languages" higher on the semantic hierarchy to refer to sentences lower in the "language" hierarchy, but not the other way around. This prevents a system from becoming self-referential.

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).{{sfn|Kripke|1975}}<ref name=PlatoProject.LiarParadox.TarskiHier>{{harvnb|Beall|Glanzberg|Ripley|2016}}</ref> [[Saul Kripke]] is credited with identifying this incompleteness in Tarski's hierarchy in his highly cited paper "Outline of a theory of truth,"<ref name=PlatoProject.LiarParadox.TarskiHier/> and it is recognized as a general problem in hierarchical languages.{{sfn|Glanzberg|2015}}<ref name=PlatoProject.LiarParadox.TarskiHier/>

== 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.{{sfn|Chaitin|1995}}

{{harvtxt|Boolos|1989}} built on a formalized version of Berry's paradox to prove [[Gödel's incompleteness theorem]] in a new and much simpler way. The basic idea of his proof is that a [[proposition]] that holds of ''x'' if and only if ''x'' = ''n'' for some natural number ''n'' can be called a ''definition'' for ''n'', and that the set {(''n'', ''k''): ''n'' has a definition that is ''k'' symbols long} can be shown to be representable (using [[Gödel number]]s). Then the proposition "''m'' is the first number not definable in less than ''k'' symbols" can be formalized and shown to be a definition in the sense just stated.{{sfn|Boolos|1989}}

==Relationship with Kolmogorov complexity==
{{main | 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 [[formal language]]s, or [[Turing machines]] which avoids ambiguities about which string results from a given description. It can be proven that the Kolmogorov complexity is not computable. The proof by contradiction shows that if it were possible to compute the Kolmogorov complexity, then it would also be possible to systematically generate paradoxes similar to this one, i.e. descriptions shorter than what the complexity of the described string implies. That is to say, the definition of the Berry number is paradoxical because it is not actually possible to compute how many words are required to define a number, and we know that such computation is not possible because of the paradox.

==See also==

* [[Self-reference]]
* [[List of self–referential paradoxes]]
* {{annotated link|Busy beaver}}
* {{annotated link|Chaitin's incompleteness theorem}}
* {{annotated link|Definable real number}}
* {{annotated link|Paradoxes of set theory}}

==Notes==
{{Reflist}}

==References==
* {{cite SEP|author-last=Beall|author-first=J. C.|last2=Glanzberg|first2=Michael|last3=Ripley|first3=David|title=Liar Paradox|date=December 12, 2016|url-id=liar-paradox}}
* {{cite journal |last=Boolos |first=George|author-link=George Boolos|title=A New Proof of the Gödel Incompleteness Theorem|year=1989 |journal=[[Notices of the American Mathematical Society]]|volume=36|pages=388–390, 676}} Reprinted in {{cite book |last=Boolos |first=George|author-link=George Boolos|title=Logic, logic, and logic|year=1998|publisher=[[Harvard University Press]]|isbn=0-674-53766-1|pages=383–388}}
* {{cite journal
 | last = Chaitin | first = G. J. | author-link = Gregory Chaitin
 | doi = 10.1002/cplx.6130010107
 | issue = 1
 | journal = Complexity
 | mr = 1366300
 | pages = 26–30
 | title = The Berry paradox
 | url = https://pdodds.w3.uvm.edu/files/papers/others/everything/berry1995a.pdf
 | volume = 1
 | year = 1995}}
* {{cite book
 | last = Girard | first = Jean-Yves | author-link = Jean-Yves Girard
 | isbn = 9783037190883
 | publisher = European Mathematical Society
 | title = The Blind Spot: Lectures on Logic
 | year = 2011}}
* {{cite book
 | last = Glanzberg | first = Michael
 | editor1-last = Achourioti | editor1-first = Theodora
 | editor2-last = Galinon | editor2-first = Henri
 | editor3-last = Fernández | editor3-first = José Martínez
 | editor4-last = Fujimoto | editor4-first = Kentaro
 | contribution = Complexity and hierarchy in truth predicates
 | doi = 10.1007/978-94-017-9673-6_10
 | isbn = 978-94-017-9672-9
 | location = Dordrecht
 | pages = 211–243
 | publisher = Springer
 | series = Logic, Epistemology, and the Unity of Science
 | title = Unifying the Philosophy of Truth
 | volume = 36
 | year = 2015}}
* {{cite book
 | last = Griffin | first = Nicholas
 | isbn = 978-0-521-63634-6
 | publisher = Cambridge University Press
 | title = The Cambridge Companion to Bertrand Russell
 | year = 2003}}
*{{cite journal
 | last = Kripke | first = Saul | author-link = Saul Kripke
 | date = November 1975
 | department = Seventy-Second Annual Meeting American Philosophical Association, Eastern Division (Nov. 6, 1975)
 | doi = 10.2307/2024634
 | issue = 19
 | journal = The Journal of Philosophy
 | jstor = 2024634
 | pages = 690–716
 | title = Outline of a theory of truth
 | volume = 72}}
* {{cite book
 | last = Moore | first = Gregory H.
 | isbn = 9780415820981
 | publisher = Routledge
 | title = The Collected Papers of Bertrand Russell, vol. 5
 | year = 2014}}
* {{cite book
 | last = Quine | first = Willard Van Orman | author-link = Willard Van Orman Quine
 | edition = 2nd
 | isbn = 9780674948358
 | publisher = Harvard University Press
 | title = The Ways of Paradox, and Other Essays
 | year = 1976}}
* {{cite book
 | last1 = Russell | first1 = Bertrand | author1-link = Bertrand Russell
 | last2 = Whitehead | first2 = Alfred N. | author2-link = Alfred N. Whitehead
 | publisher = Cambridge University Press
 | title = Principia Mathematica
 | title-link = Principia Mathematica
 | year = 1927}}

==Further reading==
* {{cite journal | last = Bennett | first = Charles H. | date = 1979 | title = On Random and Hard-to-Describe Numbers. | citeseerx=10.1.1.27.3492  | url = http://researcher.watson.ibm.com/researcher/view_pubs.php?person=us-bennetc&t=1 | journal = IBM Report RC7483 }}
* French, James D. (1988) "[https://www.jstor.org/pss/2274615 The False Assumption Underlying Berry's Paradox]," ''Journal of Symbolic Logic 53'': 1220–1223.
* [[Bertrand Russell|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) "[https://web.archive.org/web/20020205181710/http://www.cs.yorku.ca/~peter/Berry.html Berry's Paradox.]"
* {{MathWorld |title=Berry Paradox |urlname=BerryParadox}}

{{Paradoxes}}

{{DEFAULTSORT:Berry Paradox}}
[[Category:Eponymous paradoxes]]
[[Category:Mathematical paradoxes]]
[[Category:Self-referential paradoxes]]
[[Category:Algorithmic information theory]]
[[Category:Logical paradoxes]]