|
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.
For the sake of simplicity, we assume here that hyphenated words like "self-evident" do not count as a single word but as several words ("self" and "evident"). The integers consist of the positive natural numbers (1, 2, 3, …), their negatives (−1, −2, −3, ...) and the number zero. ...
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 "Miguel de Cervantes" or "Mount Kilimanjaro."In any case, 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. In mathematics, a set is called finite 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. ...
To meet Wikipedias quality standards, this article or section may require cleanup. ...
Kilimanjaro (formerly Kaiser-Wilhelm-Spitze) is a mountain in northeastern Tanzania. ...
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 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, including an incompleteness theorem similar in spirit to Gödel's incompleteness theorem; see Kolmogorov complexity for details. Robert Boyles self-flowing flask fills itself in this diagram, but perpetual motion machines cannot exist (according to our present understanding of physics). ...
Gregory J. Chaitin (born 1947) is an Argentine-American mathematician and computer scientist. ...
In mathematical logic, Gödels incompleteness theorems are two celebrated theorems proven by Kurt Gödel in 1931. ...
In computer science, the Kolmogorov complexity (also known as descriptive complexity, Kolmogorov-Chaitin complexity, stochastic complexity, algorithmic entropy, or program-size complexity) of an object such as a piece of text is a measure of the computational resources needed to specify the object. ...
The Berry paradox was proposed by Bertrand Russell (Russell, 1906). He attributed it to G. G. Berry of the Bodleian library (c.f. Russell and Whitehead 1910), who had suggested the idea of considering the paradox associated to the expression "the first undefinable ordinal". Bertrand Arthur William Russell, 3rd Earl Russell, OM, FRS (18 May 1872 – 2 February 1970), was a British philosopher, logician, and mathematician, working mostly in the 20th century. ...
Entrance to the Library, with the coats-of-arms of several Oxford colleges The Bodleian Library, the main research library of the University of Oxford, is one of the oldest libraries in Europe, and in England is second in size only to the British Library. ...
Commonly, ordinal numbers, or ordinals for short, are numbers used to denote the position in an ordered sequence: first, second, third, fourth, etc. ...
Resolution of the paradox
It is generally accepted that the Berry paradox and other similar paradoxes (such as Richard's paradox) result from interpreting sets of possibly self-referential expressions. According to (Russell and Whitehead, 1910) these paradoxes "embody vicious circle fallacies". 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. Richards paradox is a fallacious paradox of mathematical mapping first described by the French mathematician Jules Richard in 1905. ...
Note that some Berry type expressions present only minor problems of interpretation:
- The smallest positive integer not nameable in under two words.
under reasonable definitions of English denotes 21, since "twenty one" (or "twenty-one") is two words and any indirect definition of the number (such as "the number of dots on a six-sided die", or indeed "the smallest positive integer not nameable in under two words") is necessarily two or more words long.
However, Berry's paradox can be forced into a formal system. George Boolos used a specific formalization to provide an alternate proof of Gödel's Incompleteness Theorem. The basic idea of the proof is that a proposition that holds of x if x = n for some natural number n can be called a "name" for n, 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. George Stephen Boolos (September 4, 1940, New York City - May 27, 1996) was a philosopher and a mathematical logician. ...
Proposition is a term used in logic to describe the content of assertions. ...
References - Charles H. Bennett, On Random and Hard-to-Describe Numbers, IBM Report RC7483 (1979)
http://www.research.ibm.com/people/b/bennetc/Onrandom.pdf - George Boolos, A new proof of the Gödel Incompleteness Theorem. Notices of the American Mathematical Society, 36(4), pp. 388-390.
- Bertrand Russell, Les paradoxes de la logique, Revue de métaphysique et de morale, vol 14, pp 627-650
- Bertrand Russell and Alfred N. Whitehead, Principia Mathematica, Cambridge University Press/ A paperback reissue up to *56 was published in 1962.
See also A real number a is first-order definable in the language of set theory, without parameters, if there is a formula φ in the language of set theory, with one free variable, such that a is the unique real number such that φ(a) holds (in the von Neumann universe V). ...
In computability theory, a Busy Beaver (from the colloquial expression for industrious person) is a Turing machine that, when given an empty tape, does a lot of work, then halts. ...
Richards paradox is a fallacious paradox of mathematical mapping first described by the French mathematician Jules Richard in 1905. ...
External links |
Feeds |
Contact