The Berry paradox is a self-referential paradox arising from the expression "the smallest possible integer not definable by a given number of words." Bertrand Russell, the first to discuss the paradox in print, attributed it to G. G. Berry, a librarian at Oxford's Bodleian library, who had suggested the more limited paradox arising from the expression "the first undefinable ordinal".
Contents:
1. The paradox
2. Resolution
3. Relationship with Kolmogorov complexity
4. Notes
5. See also
6. References
7. External links
1. The paradox
Consider the expression:
"The smallest positive integer 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 by the pigeonhole principle. Since there are infinitely many positive integers, this means that there are positive integers that cannot be defined by phrases of under eleven words — that is, positive integers satisfying the property "not definable in 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; that is, this integer is defined by the above expression. Note that the above expression is only ten words long; so, this integer is defined by an expression that is under eleven words long; so 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, clearly, definable in under eleven words), there cannot be any integer defined by it.
2. Resolution
The Berry paradox as formulated above arises because of systematic ambiguity in the word "definable." In other formulations of the Berry paradox, such as one that instead reads: "...not nameable 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. [1]
One of the ways it is proposed that this family of paradoxes be resolved is 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 syllables may be nameable1 in less than eleven syllables under this scheme. [2]
The argument presented above that "Since there are infinitely many positive integers, this means that there are positive integers that cannot be defined by phrases of under eleven words" assumes that "there must be an integer defined by this expression" which is counterfactual as most phrases "under eleven words" are ambiguous to their defining of an integer, with this ten word paradox being an example. Assuming one can match word phrases to numbers is a mistaken assumption. [3]
It is generally accepted that the Berry paradox results from interpreting sets of possibly self-referential expressions: it and similar paradoxes embody so-called "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.
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.
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 numbers). 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.
3. Relationship with Kolmogorov complexity
Main article: Kolmogorov complexity
It is possible to unambiguously define what is the minimal number of symbols required to describe a given string. 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 compression. 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 languages, 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.
4. Notes
1. Russell and Whitehead (1927).
2. Willard Quine (1976) Ways of Paradox. Harvard Univ. Press
3. French (1988) demonstrated that an infinite number of numbers could be uniquely described in the exact same words.
5. See also
* Definable number
* Busy beaver
* Richard's paradox
* Interesting number paradox
6. References
* Charles H. Bennett (1979) "On Random and Hard-to-Describe Numbers." IBM Report RC7483.
* George Boolos (1989) "A new proof of the Gödel Incompleteness Theorem," Notices of the American Mathematical Society 36: 388-90; 676. Reprinted in his (1998) Logic, Logic, and Logic. Harvard Univ. Press: 383-88.
* Gregory Chaitin (1995) "The Berry Paradox,." Complexity 1: 26-30.
* French, James D. (1988) "The False Assumption Underlying Berry's Paradox," Journal of Symbolic Logic 53: 1220-1223.
* Bertrand Russell (19nn) "Les paradoxes de la logique," Revue de métaphysique et de morale 14: 627-650
* ------ and Alfred N. Whitehead (1927) Principia Mathematica. Cambridge University Press. 1962 partial paperback reissue goes up to *56.
7. External links
* Roosen-Runge, Peter H. (1997) "Berry's Paradox."
Eric W. Weisstein, Berry Paradox at MathWorld.
* Weisstein, Eric W. "Berry paradox," Wolfram Research's MathWorld
Showing posts with label _B. Show all posts
Showing posts with label _B. Show all posts
Friday, December 26, 2008
Berry paradox
The Berry paradox is a self-referential paradox arising from the expression "the smallest possible integer not definable by a given number of words." Bertrand Russell, the first to discuss the paradox in print, attributed it to G. G. Berry, a librarian at Oxford's Bodleian library, who had suggested the more limited paradox arising from the expression "the first undefinable ordinal".
Contents:
1. The paradox
2. Resolution
3. Relationship with Kolmogorov complexity
4. Notes
5. See also
6. References
7. External links
1. The paradox
Consider the expression:
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 by the pigeonhole principle. Since there are infinitely many positive integers, this means that there are positive integers that cannot be defined by phrases of under eleven words — that is, positive integers satisfying the property "not definable in 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; that is, this integer is defined by the above expression. Note that the above expression is only ten words long; so, this integer is defined by an expression that is under eleven words long; so 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, clearly, definable in under eleven words), there cannot be any integer defined by it.
2. Resolution
The Berry paradox as formulated above arises because of systematic ambiguity in the word "definable." In other formulations of the Berry paradox, such as one that instead reads: "...not nameable 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. [1]
One of the ways it is proposed that this family of paradoxes be resolved is 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 syllables may be nameable1 in less than eleven syllables under this scheme. [2]
The argument presented above that "Since there are infinitely many positive integers, this means that there are positive integers that cannot be defined by phrases of under eleven words" assumes that "there must be an integer defined by this expression" which is counterfactual as most phrases "under eleven words" are ambiguous to their defining of an integer, with this ten word paradox being an example. Assuming one can match word phrases to numbers is a mistaken assumption. [3]
It is generally accepted that the Berry paradox results from interpreting sets of possibly self-referential expressions: it and similar paradoxes embody so-called "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.
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.
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 numbers). 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.
3. Relationship with Kolmogorov complexity
- Main article: Kolmogorov complexity
It is possible to unambiguously define what is the minimal number of symbols required to describe a given string. 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 compression. 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 languages, 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.
4. Notes
- Russell and Whitehead (1927).
- Willard Quine (1976) Ways of Paradox. Harvard Univ. Press
- French (1988) demonstrated that an infinite number of numbers could be uniquely described in the exact same words.
5. See also
6. References
- Charles H. Bennett (1979) "On Random and Hard-to-Describe Numbers." IBM Report RC7483.
- George Boolos (1989) "A new proof of the Gödel Incompleteness Theorem," Notices of the American Mathematical Society 36: 388-90; 676. Reprinted in his (1998) Logic, Logic, and Logic. Harvard Univ. Press: 383-88.
- Gregory Chaitin (1995) "The Berry Paradox,." Complexity 1: 26-30.
- French, James D. (1988) "The False Assumption Underlying Berry's Paradox," Journal of Symbolic Logic 53: 1220-1223.
- Bertrand Russell (19nn) "Les paradoxes de la logique," Revue de métaphysique et de morale 14: 627-650
- ------ and Alfred N. Whitehead (1927) Principia Mathematica. Cambridge University Press. 1962 partial paperback reissue goes up to *56.
7. External links
- Roosen-Runge, Peter H. (1997) "Berry's Paradox."
Eric W. Weisstein, Berry Paradox at MathWorld.
- Weisstein, Eric W. "Berry paradox," Wolfram Research's MathWorld
Monday, August 25, 2008
Black-or-White
The black-or-white fallacy is a false dilemma fallacy that unfairly limits you to only two choices.
Example:
Well, it's time for a decision. Will you contribute $10 to our environmental fund, or are you on the side of environmental destruction?A proper challenge to this fallacy could be to say, "I do want to prevent the destruction of our environment, but I don't want to give $10 to your fund. You are placing me between a rock and a hard place." The key to diagnosing the black-or-white fallacy is to determine whether the limited menu is fair or unfair. Simply saying, "Will you contribute $10 or won't you?" is not unfair.
Begging the Question
A form of circular reasoning in which a conclusion is derived from premises that presuppose the conclusion. Normally, the point of good reasoning is to start out at one place and end up somewhere new, namely having reached the goal of increasing the degree of reasonable belief in the conclusion. The point is to make progress, but in cases of begging the question there is no progress.
Example:
"Women have rights," said the Bullfighters Association president. "But women shouldn't fight bulls because a bullfighter is and should be a man."The president is saying basically that women shouldn't fight bulls because women shouldn't fight bulls. This reasoning isn't making an progress toward determining whether women should fight bulls. Insofar as the conclusion of a deductively valid argument is "contained" in the premises from which it is deduced, this containing might seem to be a case of presupposing, and thus any deductively valid argument might seem to be begging the question. It is still an open question among logicians as to why some deductively valid arguments are considered to be begging the question and others are not. Some logicians suggest that, in informal reasoning with a deductively valid argument, if the conclusion is psychologically new insofar as the premises are concerned, then the argument isn't an example of the fallacy. Other logicians suggest that we need to look instead to surrounding circumstances, not to the psychology of the reasoner, in order to assess the quality of the argument. For example, we need to look to the reasons that the reasoner used to accept the premises. Was the premise justified on the basis of accepting the conclusion? A third group of logicians say that, in deciding whether the fallacy is committed, we need more. We must determine whether any premise that is key to deducing the conclusion is adopted rather blindly or instead is a reasonable assumption made by someone accepting their burden of proof. The premise would here be termed reasonable if the arguer could defend it independently of accepting the conclusion that is at issue.
Bandwagon
If you suggest that someone's claim is correct simply because it's what most everyone is coming to believe, then you're committing the bandwagon fallacy. Get up here with us on the wagon where the band is playing, and go where we go, and don't think too much about the reasons. The Latin term for this fallacy of appeal to novelty is Argumentum ad Novitatem.
Example:
[Advertisement] More and more people are buying sports utility vehicles. Isn't it time you bought one, too? [You commit the fallacy if you buy the vehicle solely because of this advertisement.]Like its close cousin, the fallacy of appeal to the people, the bandwagon fallacy needs to be carefully distinguished from properly defending a claim by pointing out that many people have studied the claim and have come to a reasoned conclusion that it is correct. What most everyone believes is likely to be true, all things considered, and if one defends a claim on those grounds, this is not a fallacious inference. What is fallacious is to be swept up by the excitement of a new idea or new fad and to unquestionably give it too high a degree of your belief solely on the grounds of its new popularity, perhaps thinking simply that 'new is better.'
Subscribe to:
Comments (Atom)
