Berry paradox
Encyclopedia
The Berry paradox is a self-referential paradox
arising from the expression "the smallest possible integer
not definable by a given number of word
s". Bertrand Russell
, the first to discuss the paradox in print, attributed it to G. G. Berry (1867–1928), a junior librarian
at Oxford
's Bodleian library
, who had suggested the more limited paradox arising from the expression "the first undefinable
ordinal
".
Since there are finitely many words, there are finitely many phrases of under eleven words, and hence finitely many positive integers that are defined by phrases of under eleven words. Since there are infinitely many positive integers, this means that there are positive integers that cannot be defined by phrases of under eleven words. By the well ordering principle, 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 eleven words". This is the integer to which the above expression refers. The above expression is only ten words long, so this integer is defined by an expression that is under eleven words long; it is definable in under eleven words, and is not the smallest positive integer not definable in under eleven words, 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 eleven words), there cannot be any integer defined by it.
in the word "definable". In other formulations of the Berry paradox, such as one that instead reads: "...not name
able 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. 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.
. Though the formal analogue does not lead to a logical contradiction, it does prove certain impossibility results.
George 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 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 number
s). 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.
. 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 language
s, or Turing machines, that allow to avoid ambiguities about what string results from a given description. After defining that function, it can be proved that it cannot be computed. 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 feasible because of the paradox.
Paradox
Similar to Circular reasoning, A paradox is a seemingly true statement or group of statements that lead to a contradiction or a situation which seems to defy logic or intuition...
arising from the expression "the smallest possible integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
not definable by a given number of word
Word
In language, a word is the smallest free form that may be uttered in isolation with semantic or pragmatic content . This contrasts with a morpheme, which is the smallest unit of meaning but will not necessarily stand on its own...
s". Bertrand Russell
Bertrand Russell
Bertrand Arthur William Russell, 3rd Earl Russell, OM, FRS was a British philosopher, logician, mathematician, historian, and social critic. At various points in his life he considered himself a liberal, a socialist, and a pacifist, but he also admitted that he had never been any of these things...
, the first to discuss the paradox in print, attributed it to G. G. Berry (1867–1928), a junior librarian
Librarian
A librarian is an information professional trained in library and information science, which is the organization and management of information services or materials for those with information needs...
at Oxford
Oxford
The city of Oxford is the county town of Oxfordshire, England. The city, made prominent by its medieval university, has a population of just under 165,000, with 153,900 living within the district boundary. It lies about 50 miles north-west of London. The rivers Cherwell and Thames run through...
's Bodleian library
Bodleian Library
The Bodleian Library , the main research library of the University of Oxford, is one of the oldest libraries in Europe, and in Britain is second in size only to the British Library...
, who had suggested the more limited paradox arising from the expression "the first undefinable
Definable number
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 φ holds in the standard model of set theory .For the purposes of this article,...
ordinal
Ordinal number
In set theory, an ordinal number, or just ordinal, is the order type of a well-ordered set. They are usually identified with hereditarily transitive sets. Ordinals are an extension of the natural numbers different from integers and from cardinals...
".
The paradox
Consider the expression:- "The smallest positive integerIntegerThe integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
not definable in under eleven words."
Since there are finitely many words, there are finitely many phrases of under eleven words, and hence finitely many positive integers that are defined by phrases of under eleven words. Since there are infinitely many positive integers, this means that there are positive integers that cannot be defined by phrases of under eleven words. By the well ordering principle, 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 eleven words". This is the integer to which the above expression refers. The above expression is only ten words long, so this integer is defined by an expression that is under eleven words long; it is definable in under eleven words, and is not the smallest positive integer not definable in under eleven words, 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 eleven words), there cannot be any integer defined by it.
Resolution
The Berry paradox as formulated above arises because of systematic ambiguityAmbiguity
Ambiguity of words or phrases is the ability to express more than one interpretation. It is distinct from vagueness, which is a statement about the lack of precision contained or available in the information.Context may play a role in resolving ambiguity...
in the word "definable". In other formulations of the Berry paradox, such as one that instead reads: "...not name
Name
A name is a word or term used for identification. Names can identify a class or category of things, or a single thing, either uniquely, or within a given context. A personal name identifies a specific unique and identifiable individual person, and may or may not include a middle name...
able in less..." the term "nameable" is also one that has this systematic ambiguity. Terms of this kind give rise to vicious circle
Vicious circle principle
The vicious circle principle is a principle that was endorsed by many predicativist mathematicians in the early 20th century to prevent contradictions. The principle states that no object or property may be introduced by a definition that depends on that object or property itself...
fallacies. Other terms with this type of ambiguity are: satisfiable, true, false, function, property, class, relation, cardinal, and ordinal. 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.
Formal analogues
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 ChaitinGregory Chaitin
Gregory John Chaitin is an Argentine-American mathematician and computer scientist.-Mathematics and computer science:Beginning in 2009 Chaitin has worked on metabiology, a field parallel to biology dealing with the random evolution of artificial software instead of natural software .Beginning in...
. Though the formal analogue does not lead to a logical contradiction, it does prove certain impossibility results.
George Boolos
George Boolos
George Stephen Boolos was a philosopher and a mathematical logician who taught at the Massachusetts Institute of Technology.- Life :...
(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
Proposition
In logic and philosophy, the term proposition refers to either the "content" or "meaning" of a meaningful declarative sentence or the pattern of symbols, marks, or sounds that make up a meaningful declarative sentence...
that holds of x 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 number
Gödel number
In mathematical logic, a Gödel numbering is a function that assigns to each symbol and well-formed formula of some formal language a unique natural number, called its Gödel number. The concept was famously used by Kurt Gödel for the proof of his incompleteness theorems...
s). 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
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, i.e. 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 experienced using data compressionData compression
In computer science and information theory, data compression, source coding or bit-rate reduction is the process of encoding information using fewer bits than the original representation would use....
. 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 language
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
s, or Turing machines, that allow to avoid ambiguities about what string results from a given description. After defining that function, it can be proved that it cannot be computed. 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 feasible because of the paradox.
See also
- Definable numberDefinable numberA 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 φ holds in the standard model of set theory .For the purposes of this article,...
- Busy beaverBusy beaverIn computability theory, a busy beaver is a Turing machine that attains the maximum "operational busyness" among all the Turing machines in a certain class...
- Richard's paradoxRichard's paradoxIn logic, Richard's paradox is a semantical antinomy in set theory and natural language first described by the French mathematician Jules Richard in 1905. Today, the paradox is ordinarily used in order to motivate the importance of carefully distinguishing between mathematics and metamathematics...
- Interesting number paradoxInteresting number paradoxThe interesting number paradox is a semi-humorous paradox that arises from attempting to classify natural numbers as "interesting" or "dull". The paradox states that all natural numbers are interesting...
- List of paradoxes
External links
- Roosen-Runge, Peter H. (1997) "Berry's Paradox."