러셀의 역설
위키백과 ― 우리 모두의 백과사전.
러셀의 역설(Russell's paradox)은 수학자 버트런드 러셀이 1901년 발견한 논리적 역설로 프레게의 논리체계와 칸토어의 소박한 집합론(naive set theory)이 모순을 지닌다는 것을 보여준 예이다.
그 대략적인 내용은 다음과 같다.
- M이라는 집합을 "자신을 원소로 포함하지 않는 모든 집합들의 집합"으로 정의하자. 다시 말해, A가 M의 원소가 되기 위한 필요충분조건은 A가 A의 원소가 아닌 것으로 한다.
- 칸토어의 공리체계에서 위와 같은 정의로 집합 M은 문제없이 잘 정의된다. 여기서 M이 자기 자신을 원소로 포함하는가?란 질문을 던져본다. 만약 포함한다고 가정하면 그 정의에 의해 M은 자신을 원소로 포함하지 않는다. 반대로 M이 자신을 원소로 포함하지 않는다고 가정했을 때에도 역시 그 정의에 의해 M은 자신에 포함되어야 한다. 즉 "M은 M의 원소이다"라는 명제와 "M은 M의 원소가 아니다"라는 명제는 둘 다 모순을 도출하여 맞다 혹은 그르다 중에 어떤 답으로 답할 수 없다.
프레게의 공리체계에서 M은 "자신을 정의하는 개념에 포함되지 않는다(not fall under its defining concept)"라는 개념(concept)에 해당한다. 따라서, 프레게의 체계 역시 모순을 낳는다.
목차 |
[편집] 역사
러셀이 정확히 언제 이 역설을 발견했는지는 확실하지 않지만, 아마도 1901년 5월이나 6월경 특정 영역의 개체의 수는 그 개체의 하등계급 수보다 작다는 칸토어의 법칙에 대한 연구를 하다가 발견한 것으로 보인다.
In Russell's Principles of Mathematics (not to be confused with the later Principia Mathematica) Chapter X, section 100, where he calls it "The Contradiction" he says that he was led to it by analyzing Cantor's proof that there can be no greatest cardinal. He also mentions it in a 1901 paper in the International Monthly, entitled "Recent work in the philosophy of mathematics" Russell mentioned Cantor's proof that there is no largest cardinal and stated that "the master" had been guilty of a subtle fallacy that he would discuss later.
Famously, Russell wrote to Frege about the paradox in June 1902, just as Frege was preparing the second volume of his Grundgesetze. Frege was forced to prepare an appendix in response to the paradox, but this later proved unsatisfactory. It is commonly supposed that this led Frege completely to abandon his work on the logic of classes.
While Zermelo was working on his version of set theory, he also noticed the paradox, but thought it too obvious and never published anything about it! Zermelo's system avoids the difficulty through the famous Axiom of separation (Aussonderung).
Russell, with Alfred North Whitehead, undertook to accomplish Frege's task, this time using a more restricted version of set theory that, they thought, would not admit Russell's Paradox, but would still produce arithmetic. Kurt Gödel later showed that, even if it was consistent, it did not succeed in reducing all mathematics to logic -indeed this could not be done: arithmetic is "incomplete."
[편집] 역설의 이해하기 쉬운 해석
논리학을 전문적으로 공부하지 않은 일반인들도 이해하기 쉽게 러셀 자신이 그의 역설을 예로 설명한 것이 이발사이야기이다.
만약 어떤 마을에 스스로 이발을 하지 않는 모든 이의 이발를 해주는 이발사가 있다고 하자. 이 이발사는 이발을 스스로 해야 할까? 만약 스스로 이발을 하지 않는다면, 그 전제에 의해 자신이 자신을 이발시켜야 하고, 역으로 스스로 이발을 한다면, 자신이 자신을 이발시켜서는 안된다. 이는 바로 러셀의 역설과 동일한 문제에 걸리는 것이다.
위키백과에 "자기 자신을 포함하지 않는 모든 목록만의 목록"이란 항목이 있을 수 있을까? 러셀의 역설에 의해 이는 모순이다. 만약 자기 자신을 포함하지 않는다면 미완성이며 포함한다면 틀린 제목이 된다.
[편집] Set-theoretic responses to the Russell Paradox
After this paradox was described, set theory had to be reformulated axiomatically as axiomatic set theory in a way that avoided this and other related problems. Russell himself, together with Alfred North Whitehead, developed a comprehensive system of types in his work Principia Mathematica. This system does indeed avoid the known paradoxes and allows for the formulation of all of mathematics, but it has not been widely accepted. The most common version of axiomatic set theory in use today is Zermelo-Fraenkel set theory, which avoids the notion of types and restricts the universe of sets to those which can be constructed from given sets using certain axioms. The object M discussed above cannot be constructed like that and is therefore not a set in this theory; it is a proper class.
[편집] Easy-to-understand version of responses to the Paradox
Some of the various set-theoretic approaches to address and circumvent Russell's paradox can be illustrated in the context of Wikipedia, respecting the requirement that the content of each entry must be correct according to its entry name, and allowing the possiility of its entire contents to be correctly linked in turn:
- either by self links of entry content to the same entry being discouraged; together with noting that the entity through which all Wikipedia entries are necessarily linked, namely Wikipedia as a whole, is itself not just an entry, but an entire web site. Accordingly, no entry would contain and link to itself; and the entity containing all entries (which don't link to themselves) is identified as the whole Wikipedia;
- or instead by requiring that the name of any entry which concerns listing, inclusion or linking must be explicit and decisive about the inclusion of the entry itself. Names such as list of all lists which do not contain themselves, but including this one itself, and list of all lists which do not contain themselves, except this one could be correctly and legitimately articulated as Wikipedia entries (although doing so is nevertheless not advisable, if their contents may be obtained in Wikipedia more efficiently otherwise).
- In context of the Barber example, the latter requirement would ensure the consideration instead, for instance, of a barber who shaves everyone who does not shave himself, as well as the barber himself; perhaps along with a town sheriff who may arrest all those who cannot arrest themselves, with exception of the sheriff.
[편집] 응용 방면과 관련 주제
The Barber paradox, in addition to leading to a tidier set theory, has been used twice more with great success: Kurt Gödel proved his incompleteness theorem by formalizing the paradox, and Turing proved the undecidability of the Halting problem (and with that the Entscheidungsproblem) by using the same trick.
러셀의 역설은 거짓말쟁이의 역설과 깊은 관련이 있다.
