Berry paradox
The Berry paradox (also: Berry- paradox ) is a selbstreferenzierendes paradox that from the expression " the smallest integer that is not definable by a given number of words " results. Bertrand Russell, who in 1908 grappled the first writing with the paradox, it arranged to GG Berry ( 1867-1928 ), a librarian of the Bodleian Library Oxford.
The paradox
Consider the expression:
Since a finite number of words, there are finitely many sets of 14 words, and thus after the pigeonhole principle 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 can not be defined with a set of less than 14 words - namely those that have the property "can not be defined with less than 14 words to be able to ." Since the natural numbers are well-ordered, there must be a smallest in the set of satisfying this property numbers; Accordingly, there is a smallest positive integer with the property " can not be defined in less than 14 words ." This is the integer referred to by the above expression; That is, this integer is defined by the above expression. The given expression is only 13 words long; this integer is thus defined as less than 14 words. Thus they can be defined with fewer than 14 words and therefore is not the smallest positive integer that can not be defined with fewer than 14 words, and is therefore ultimately not defined by this expression. This is a paradox: there must be an integer that is defined by this expression, but since the term is contradictory ( any integer that defines it, is obviously definable with under 14 words ), there can be no integer, which he defines.
Resolution
The above described Berry paradox is due to the systematic ambiguity of the word " definable ". In other formulations of the Berry paradox, for example, " ... not nameable with less than ... ", accept other words this systematic ambiguity. Formulations of this type lay the foundation for Vicious Circle errors. Other terms of this property are satisfiable, true, false, function, class, property, relation, cardinal and ordinal. To resolve such a paradox, is first to determine exactly at which point a mistake has been made in the use of language, and then set up rules to avoid this error.
The above- mentioned argument "Because there are infinitely many positive integers, there must be positive integers that can not be defined with a set of less than 14 words, " requires that " there must be an integer that defines this expression will, " which is absurd, because most sentences " with less than 14 words " are ambiguous in terms of their definition of an integer, for which the above 13 - word sentence is an example. The assumption that one can put sentences in a relationship with numbers, is a misconception.
More rigorous this family can be resolved by paradoxes by introducing classifications of word meaning. Expressions with systematic ambiguity may be provided with subscripts that indicate the preferred meaning interpretation: The number that is not benennbar0 with less than fourteen words may be less than fourteen words benennbar1.
Formal analogies
With programs or evidence of a certain length, it is possible to formulate an analogue 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 proves impossible but some results.
George Boolos constructed in 1989 a formalized version of Berry's paradox, in order to prove the Gödel's incompleteness theorem on new and simpler way. The basic idea of this proof is that a measure taken for x acceptance as a definition of n can be used if x = n for a natural number, and that the set { (n, k): n has a definition of length k symbols } can be represented by Gödel numbers. Then, the adoption of "m is the first number which can not be defined with less than k symbols " are formalized and accepted as a definition at the abovementioned sense.
Related to the Kolmogorov complexity
→ Main article: Kolmogorov complexity
It is possible to clearly define what is the minimum number of symbols required to describe a given string. In this context, the terms chain and number can be used interchangeably, since a number is actually a string of symbols, so a German word ( like the word " fourteen " in the paradox), while it is otherwise possible to each word with a number represent, for example, with the number of its position in a given dictionary or by appropriate encoding. Some long strings can be accurately described by fewer symbols than for the complete representation would be needed, as often happens in data compression. The complexity of a given character string is then defined as the minimum length required by a specification to (uniquely ) represent the full representation of the string.
The Kolmogorov complexity is defined using formal languages or Turing machines that allow the avoidance of ambiguity, which results from a given string description. Once this function is defined, it can be proved that it is not predictable. The proof by contradiction shows that if it were possible to compute the Kolmogorov complexity, it would also be possible to systematically generate paradoxes such as this, that is implied descriptions that are shorter than the complexity of the character described. This means that the definition of the Berry number is paradoxical because it is not actually calculated how many words are needed to define a number, and we know that such a calculation because of the paradox is not feasible.