fbpx
Wikipedia

Berry paradox

December 15, 2023

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),[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 edit

Consider the expression:

"The smallest 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.

Perhaps another helpful analogy to Berry's Paradox would be the phrase "indescribable feeling".[4] If the feeling is indeed indescribable, then no description of the feeling would be true. But if the word "indescribable" communicates something about the feeling, then it may be considered a description: this is self-contradictory.

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 edit

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.[5] 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.[6]

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).[7][8] Saul Kripke is credited with identifying this incompleteness in Tarski's hierarchy in his highly cited paper "Outline of a theory of truth,"[8] and it is recognized as a general problem in hierarchical languages.[9][8]

Formal analogues edit

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.[citation needed] Though the formal analogue does not lead to a logical contradiction, it does prove certain impossibility results.

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 numbers). 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.

Relationship with Kolmogorov complexity edit

Main article: 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 languages, 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 edit

Notes edit

  1. ^ Nicholas Griffin (2003-06-23). The Cambridge Companion to Bertrand Russell. Cambridge University Press. p. 63. ISBN 978-0-521-63634-6.
  2. ^ Moore, Gregory H. (2014). The Collected Papers of Bertrand Russell, vol. 5. Routledge. pp. Appendix IV. ISBN 9780415820981.
  3. ^ Girard, 'The Blind Spot' (2011, p.16)
  4. ^ Menken, Alan; Ashman, Howard; Rice, Tim (1 Dec 1992). Aladdin (Piano/Vocal/Guitar Songbook). Hal Leonard. ISBN 978-0793517824.
  5. ^ Russell and Whitehead (1927).
  6. ^ Quine, Willard (1976). Ways of Paradox. Harvard University Press.
  7. ^ Kripke, Saul (1975-11-06). Outline of a theory of truth. Seventy-Second Annual Meeting American Philosophical Association, Eastern Division. Vol. 72. Journal of Philosophy. pp. 690–716. doi:10.2307/2024634. JSTOR 2024634.
  8. ^ a b c Beall, Jc; Glanzberg, Michael; Ripley, David (2016-12-12) [January 20, 2011]. "Liar Paradox: Section 4.3.1 Tarski's hierarchy of languages". from the original on 2021-01-12. Retrieved 2021-01-16.
  9. ^ Glanzberg, Michael (2015-06-17). "Complexity and hierarchy in truth predicates". Unifying the Philosophy of Truth. Logic, Epistemology, and the Unity of Science. Logic, Epistemology, and the Unity of Science. Springer, Dordrecht. 36: 211–243. doi:10.1007/978-94-017-9673-6_10. ISBN 978-94-017-9672-9.

References edit

External links edit

December 15, 2023
berry, paradox, self, referential, paradox, arising, from, expression, like, smallest, positive, integer, definable, under, sixty, letters, phrase, with, fifty, seven, letters, bertrand, russell, first, discuss, paradox, print, attributed, berry, 1867, 1928, j. 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 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 Contents 1 Overview 2 Resolution 3 Formal analogues 4 Relationship with Kolmogorov complexity 5 See also 6 Notes 7 References 8 External linksOverview editConsider the expression The smallest 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 Perhaps another helpful analogy to Berry s Paradox would be the phrase indescribable feeling 4 If the feeling is indeed indescribable then no description of the feeling would be true But if the word indescribable communicates something about the feeling then it may be considered a description this is self contradictory 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 editThe 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 5 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 6 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 a of the hierarchy there is a statement at level a 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 7 8 Saul Kripke is credited with identifying this incompleteness in Tarski s hierarchy in his highly cited paper Outline of a theory of truth 8 and it is recognized as a general problem in hierarchical languages 9 8 Formal analogues editUsing 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 citation needed Though the formal analogue does not lead to a logical contradiction it does prove certain impossibility results Boolos 1989 built on a formalized version of Berry s paradox to prove Godel 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 Godel numbers 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 Relationship with Kolmogorov complexity editMain article 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 languages 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 editBhartrhari s paradox Hindu philosopher and linguistPages displaying short descriptions of redirect targets 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 complexityPages displaying short descriptions of redirect targets Definable real number Hilbert Bernays paradox limit of classical logicPages displaying wikidata descriptions as a fallback Interesting number paradox On the smallest non interesting number Paradoxes of set theory Richard s paradox Apparent contradiction in metamathematicsNotes edit Nicholas Griffin 2003 06 23 The Cambridge Companion to Bertrand Russell Cambridge University Press p 63 ISBN 978 0 521 63634 6 Moore Gregory H 2014 The Collected Papers of Bertrand Russell vol 5 Routledge pp Appendix IV ISBN 9780415820981 Girard The Blind Spot 2011 p 16 Menken Alan Ashman Howard Rice Tim 1 Dec 1992 Aladdin Piano Vocal Guitar Songbook Hal Leonard ISBN 978 0793517824 Russell and Whitehead 1927 Quine Willard 1976 Ways of Paradox Harvard University Press Kripke Saul 1975 11 06 Outline of a theory of truth Seventy Second Annual Meeting American Philosophical Association Eastern Division Vol 72 Journal of Philosophy pp 690 716 doi 10 2307 2024634 JSTOR 2024634 a b c Beall Jc Glanzberg Michael Ripley David 2016 12 12 January 20 2011 Liar Paradox Section 4 3 1 Tarski s hierarchy of languages Archived from the original on 2021 01 12 Retrieved 2021 01 16 Glanzberg Michael 2015 06 17 Complexity and hierarchy in truth predicates Unifying the Philosophy of Truth Logic Epistemology and the Unity of Science Logic Epistemology and the Unity of Science Springer Dordrecht 36 211 243 doi 10 1007 978 94 017 9673 6 10 ISBN 978 94 017 9672 9 References editBennett 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 Godel Incompleteness Theorem Notices of the American Mathematical Society 36 388 390 676 Reprinted in Boolos 1998 pp 383 388 Boolos George 1998 Logic logic and logic Harvard University Press p 443 ISBN 0 674 53766 1 Chaitin Gregory 1993 Transcript of lecture given 27 October 1993 at the University of New Mexico Chaitin Gregory 1995 The Berry Paradox Complexity 1 26 30 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 metaphysique et de morale 14 627 650 Russell Bertrand Whitehead Alfred N 1927 Principia Mathematica Cambridge University Press 1962 partial paperback reissue goes up to 56 External links editRoosen Runge Peter H 1997 Berry s Paradox Weisstein Eric W Berry Paradox MathWorld Retrieved from https en wikipedia org w index php title Berry paradox amp oldid 1189114318, wikipedia, wiki, book, books, library,

article

, read, download, free, free download, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, picture, music, song, movie, book, game, games.