Berry Paradox

The Berry Paradox (also: Berry Paradox) is a self-referencing paradox that results from the expression “the smallest whole number that cannot be defined by a given number of words ”. Bertrand Russell , who in 1908 was the first to deal with the paradox in writing, assigned it to GG Berry (1867–1928), a librarian at Oxford's Bodleian Library .

The paradox

The expression is given:

"The smallest positive whole number that cannot be defined in less than fourteen words."

Since there are finitely many words, there are also finitely many sentences of 14 words, and thus only finitely many positive integers that can be defined by sentences of less than 14 words. Because there are infinitely many positive integers, there must be positive integers that cannot be defined with a set of less than 14 words - namely, those that have the property of "cannot be defined with less than 14 words". Since the natural numbers are well ordered , there must be a smallest number in the set of numbers satisfying this property ; consequently there is a smallest positive integer with the property “not definable in less than 14 words”. This is the integer to which the above expression applies; that is, this integer is defined by the above expression. The given expression is only 13 words long; this integer is defined with less than 14 words. So it is definable with less than 14 words and consequently not the smallest positive integer that cannot be defined with less than 14 words and is therefore ultimately not defined by this expression. This is a paradox: there has to be an integer defined by this expression, but since the expression is contradicting (any integer it defines is obviously definable by under 14 words) there cannot be an integer it defines .

resolution

The Berry paradox described above arises from the systematic ambiguity of the word “definable”. In other formulations of the Berry Paradox, for example "... not nameable with less than ...", other words take over this systematic ambiguity. Formulations of this kind lay the foundation for vicious circle errors. Further terms of this property are satisfiable , true , false , functioning , property , class , relationship , cardinal and ordinal . In order to resolve such a paradox, it is first necessary to determine exactly where a mistake was made in linguistic usage, in order to then establish rules to avoid this mistake.

The above argument, “Because there are infinitely many positive integers, there must be positive integers that cannot be defined with a set of less than 14 words” implies that “there must be an integer that defines with this expression becomes ” , which is absurd because most sentences “ with less than 14 words ”are ambiguous with regard to their definition of an integer, of which the 13-word sentence above is an example. The assumption that one can relate sentences to numbers is a misconception.

This family of paradoxes can be resolved even more rigorously by introducing classifications of word meaning. Expressions with systematic ambiguity can be provided with subscripts that signal the preferred interpretation of the meaning: The number that cannot be named ₀ in less than fourteen words can be named ₁ in less than fourteen words.

Formal analogies

With programs or proofs of a certain length it is possible to formulate an equivalent of the Berry expression in a formal mathematical language, as was done by Gregory Chaitin . Although the formal correspondence does not lead to a logical contradiction, it does prove certain impossible outcomes.

George Boolos constructed a formalized version of Berry's Paradox in 1989 in order to prove Gödel's incompleteness theorem in a new and simpler way. The basic idea of this proof is that an assumption made for can be used as a definition for if holds for a natural number, and that the set can be represented with Godel numbers . Then the assumption “ is the first number that cannot be defined with less than symbols” can be formalized and accepted as a definition in the sense mentioned above. ${\ displaystyle x}$ ${\ displaystyle n}$ ${\ displaystyle x = n}$ ${\ displaystyle \ left \ {(n, k): n {\ mbox {has a definition of length}} k \ right \}}$ ${\ displaystyle m}$ ${\ displaystyle k}$

Relation to Kolmogorow Complexity

see main article: Kolmogorov Complexity

It is possible to unambiguously define what is the minimum number of symbols required to describe a given character string. In this context, the terms chain and number can be used interchangeably, since a number is actually a chain of symbols, i.e. a German word (like the word "fourteen" in the paradox), while on the other hand it is possible to use each word with a number to represent, e.g. B. with the number of its position in a given dictionary or by appropriate coding. Some long strings can be described exactly by fewer symbols than would be necessary for the complete representation, as is often the case with data compression . The complexity of a given string is then defined as the minimum length a description needs to (uniquely) represent the full representation of this string.

The Kolmogorow complexity is defined with the help of formal languages or Turing machines , which avoid ambiguities about which character string results from a given description. Once this function is defined, it can be proven that it is not computable. Proof by contradiction shows that if it were possible to compute Kolmogorov complexity, it would also be possible to systematically generate paradoxes like this, that is, descriptions that are shorter than the complexity of the character string being described. This means that the definition of the Berry number is paradoxical because it is not actually computable how many words are needed to define a number, and we know that such a computation cannot be carried out because of the paradox.

literature

Charles H. Bennett: On Random and Hard-to-Describe Numbers . (PDF) IBM Report RC7483, 1979.
George Boolos : A new proof of the Gödel Incompleteness Theorem . In: Notices of the American Mathematical Society , 36, 1989, pp. 388-390, 676. Reprinted in 1998 in Logic, Logic, and Logic . Harvard Univ. Press, pp. 383-88.
Gregory Chaitin : The Berry Paradox . In: Complexity , 1, 1995, pp. 26-30, doi: 10.1002 / cplx.6130010107 .
James D. French: The False Assumption Underlying Berry's Paradox . In: Journal of Symbolic Logic , 53, 1988, pp. 1220-1223, jstor.org .
Bertrand Russell : Les paradoxes de la logique . In: Revue de métaphysique et de morale , 14, pp. 627–650
Bertrand Russell, Alfred N. Whitehead (1927) Principia Mathematica . Cambridge University Press. 1962 partly new paperback edition up to * 56.

Web links

Peter H. Roosen-Runge: Berry's Paradox. 1997
Eric W. Weisstein : Berry Paradox . In: MathWorld (English).

Individual evidence

^ ^A ^b Russell: Mathematical logic as based on the theory of types (PDF; 1.9 MB) In: American Journal of Mathematics , 30, 1908, p. 223 (4). In the English original there are nineteen syllables instead of fourteen words.
↑ Russell and Whitehead (1927)
↑ French demonstrated in 1988 that an infinite number of numbers can be uniquely described with the exact same words.
↑ Willard Quine : Ways of Paradox . Harvard Univ. Press 1976

[Russell-1] A ^b Russell: Mathematical logic as based on the theory of types (PDF; 1.9 MB) In: American Journal of Mathematics , 30, 1908, p. 223 (4). In the English original there are nineteen syllables instead of fourteen words.

[2] Russell and Whitehead (1927)

[3] French demonstrated in 1988 that an infinite number of numbers can be uniquely described with the exact same words.

[4] Willard Quine : Ways of Paradox . Harvard Univ. Press 1976