|
The Berry paradox is the apparent contradiction that arises from expressions such as the following: - The smallest positive integer not nameable in under eleven words.
We can argue that this phrase specifies a unique integer as follows: there are finitely many phrases of fewer than eleven words. Some of these phrases denote a unique integer: For example, "one hundred thirty six", "the smallest prime number greater than five hundred million" or "ninety raised to the centillionth power". On the other hand, some of these phrases denote things which are not integers: For example "Tony Blair" or "Miguel de Cervantes." In particular, the set A of integers that can be uniquely specified in under eleven words is finite. Since A is finite, not every positive integer can be in A. Thus by well-ordering of the integers, there is a smallest positive integer that is not in A. The integers consist of the positive natural numbers (1, 2, 3, …), their negatives (−1, −2, −3, ...) and the number zero. ...
In mathematics, a set is called finite if and only if there is a bijection between the set and some set of the form {1, 2, ..., n} where is a natural number. ...
The number centillion refers to different quantities based on locality of usage: North American system In Canadian and U.S. usage, one centillion is 10303. ...
The Right Honourable Anthony Charles Lynton Blair (born 6 May 1953 in Edinburgh, Scotland) is the current Prime Minister of the United Kingdom, First Lord of the Treasury and Minister for the Civil Service. ...
Miguel de Cervantes Saavedra (September 29, 1547 – April 23, 1616), was a Spanish novelist, poet and playwright. ...
In mathematics, a well-order (or well-ordering) on a set S is a total order on S with the property that every non-empty subset of S has a least element in this ordering. ...
But the Berry expression itself is a specification for that number in only ten words!
This is clearly paradoxical, and would seem to suggest that "nameable in under eleven words" may not be well-defined. However, using programs or proofs of bounded lengths, it is possible 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, including an incompleteness theorem similar in spirit to Gödel's incompleteness theorem; see Kolmogorov complexity for details. Listen to this article · (info) This audio file was created from the revision dated 2005-07-07, and does not reflect subsequent edits to the article. ...
Gregory J. Chaitin (born 1947) is an American contemporary mathematician and computer scientist. ...
In mathematical logic, Gödels incompleteness theorems are two celebrated theorems proven by Kurt Gödel in 1931. ...
Algorithmic information theory is a field of study which attempts to capture the concept of complexity by using tools from theoretical computer science. ...
The Berry paradox was actually created by Bertrand Russell, who named it after G. G. Berry. Berry had provided the original idea in a letter to Russell about the less specific "the first ordinal that cannot be named in a finite number of words". The Right Honourable Bertrand Arthur William Russell, 3rd Earl Russell, OM, FRS (18 May 1872 – 2 February 1970), was an influential British logician, philosopher, and mathematician, working mostly in the 20th century. ...
Commonly, ordinal numbers, or ordinals for short, are numbers used to denote the position in an ordered sequence: first, second, third, fourth, etc. ...
Solutions It is generally accepted that the Berry paradox and its ilk hang on underdetermined language. That is, "not nameable in fewer than n words" is not well-defined, for several reasons. First, the number of words in which a thing is nameable is surely relative to the language in which it is named. So we might attempt to prop up the paradox as follows: "The smallest number not nameable in English in fewer than thirteen words" (adjusting word counts as the length of the expression requires). But this is not really enough either, because we can name any number in as few words as we want, just by stipulation. Pick out whatever number you want using as long an expression as you need, and declare, "I shall henceforth call that number Jones." Now you can ask whether Jones is odd, or even, or prime, and name it using only one word.
We can invent new words in this way whenever we please. Yet it is a well known fact that there are more numbers than there are possible names (of reasonable syllabic length) in any language, so given any vocabulary there must be some number it cannot name in less than n words, for any n.
The real problem, then, is that the paradox must be formulated relative to a fixed vocabulary. So we might say, "The smallest number that cannot be named, by the totality of English that existed by the end of December 31, 1999, in fewer than twenty-eight words." (counting 31, 1999, twenty, and eight each as a single word.)
However, it was shown by Tarski that certain predicates, such as the truth-predicate for a language, can be formulated coherently only in a richer language than the one they apply to, a metalanguage. That is, the above predicate can only exist without contradiction in a language other than "the totality of English that existed by December 31, 1999." So the "paradox" expression is not in fact a counterexample to the condition it states. Alfred Tarski (January 14, 1901 in Warsaw–October 26, 1983 in Berkeley, USA) was a Polish logician considered to be one of the greatest logicians of all time in a manner after Aristotle, Gottlob Frege, and Kurt Gödel. ...
Metalanguage in linguistics is a language used to make statements about language (the object language). ...
(A minor quibble is that "the smallest number not nameable in fewer than eleven words" is not a name at all but a description. The paradox easily accommodates this with, "the smallest number not denotable by any expression of fewer than fourteen words." The solution is similar.)
However, Berry's paradox can be forced into a formal language, specifically that of mathematical logic, provided that enough axioms are assumed that their model is sufficiently strong to carry out ordinary arithmetic. Boolos used a specific formalization to provide an alternate proof of Godel's Incompleteness Theorem. The basic idea of the proof is that a proposition that holds of x iff x=n for some natural number n can be called a "name" for x, and that the set {(n,k): the natural number n has a name that is k symbols long} can be shown to be representable (using Gödel numbers). Then the proposition "m is the first number not nameable in under k symbols" can be formalized and shown to be a name. In mathematical logic, Gödels incompleteness theorems are two celebrated theorems proved by Kurt Gödel in 1931. ...
Proposition is a term used in logic to describe the content of assertions, content which may be taken as being true or false, and which are a non-linguistic abstraction from the linguistic sentence that constitutes an assertion. ...
References - George Boolos, "A new proof of the Gödel Incompleteness Theorem." Notices of the American Mathematical Society, 36(4), pp. 388-390.
See also A definable number is a real number which can be unambiguously defined by some mathematical statement. ...
In computability theory, a Busy Beaver (from the colloquial expression for industrious person) is a Turing machine that, when given an empty tape (a string of only 0s), does a lot of work, then halts. ...
External links |
Feeds |
Contact