베리 역설

Berry paradox

베리 패러독스는 '60자 미만으로 정의할 수 없는 가장 작은 양의 정수'(57자의 구절)와 같은 표현에서 비롯되는 자기주장적 역설이다.

인쇄된 역설을 최초로 논한 베르트랑 러셀옥스퍼드 보들리언 도서관의 후배 [1]사서인 G. G. 베리(1867–1928) 덕분이라고 했다. 러셀은 베리를 "옥스퍼드에서 수학 논리를 이해한 유일한 사람"[2]이라고 불렀다.

개요

다음 식을 고려하십시오.

"60자 미만으로 정의할 수 없는 가장 작은 의 정수."

영어 알파벳에는 26자밖에 없기 때문에, 60자 미만의 구절들이 매우 많으며, 따라서 60자 미만의 구절들로 정의되는 양수들도 상당히 많다. 무한히 많은 양의 정수가 있기 때문에, 60자 이하의 문구로 정의할 수 없는 양의 정수가 있다는 것을 의미한다. 주어진 속성을 만족시키는 양의 정수가 있는 경우, 그 속성을 만족시키는 최소 양의 정수가 있으므로, "60자 미만으로 정의할 수 없다"는 특성을 만족하는 최소 양의 정수가 있다. 이것은 위의 표현이 가리키는 정수다. 그러나 위의 표현은 단지 57자 길이에 불과하므로 60자 이하로 정의할 수 있으며, 60자 이하로 정의할 수 없는 가장 작은 양의 정수가 아니며, 이 표현으로 정의되지 않는다. 이것은 역설이다:이 표현에 의해 정의되는 정수가 있어야 하지만, 그 표현은 자기 모순적이므로(그 표현은 정의한 정수가 60자 이내로 정의될 수 있음), 그것에 의해 정의되는 정수는 있을 수 없다.

아마도 베리의 패러독스에 대한 또 다른 유용한 비유는 "설명할 수 없는 감정"[3]이라는 문구일 것이다. 만약 그 감정이 정말로 말로 표현할 수 없다면, 그 감정에 대한 어떠한 설명도 진실되지 않을 것이다. 그러나 "설명할 수 없는"이라는 단어가 느낌에 대해 뭔가를 전달한다면, 그것은 설명으로 간주될 수 있다: 이것은 자기 모순이다.

Mathematician and computer scientist Gregory J. Chaitin in The Unknowable (1999) adds this comment: "Well, the Mexican mathematical historian Alejandro Garcidiego has taken the trouble to find that letter [of Berry's from which Russell penned his remarks], and it is rather a different paradox. Berry’s letter actually talks about the first ordinal that can’t be named in a finite number of words. According to Cantor’s theory such an ordinal must exist, but we’ve just named it in a finite number of words, which is a contradiction."

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.[4] 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.[5]

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 Chaitin. 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 and only 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.

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, e.g. 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 achieved 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 which avoids ambiguities about which string results from a given description. It can be proven that the Kolmogorov complexity is not computable. 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 possible because of the paradox.

See also

Notes

  1. ^ Nicholas Griffin (2003-06-23). The Cambridge Companion to Bertrand Russell. Cambridge University Press. p. 63. ISBN 978-0-521-63634-6.
  2. ^ Moore, Gregory H. (2014). The Collected Papers of Bertrand Russell, vol. 5. Routledge. pp. Appendix IV. ISBN 9780415820981.
  3. ^ Menken, Alan; Ashman, Howard; Rice, Tim (1 Dec 1992). Aladdin (Piano/Vocal/Guitar Songbook). Hal Leonard. ISBN 978-0793517824.
  4. ^ Russell and Whitehead (1927).
  5. ^ 키네, 윌라드(1976년). 패러독스의 방법. 하버드 대학 출판부.

참조

외부 링크