| 수학기초론 Foundations of Mathematics | |||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | 다루는 대상과 주요 토픽 | ||
| 수리논리학 | 논리 · 논증{귀납논증 · 연역논증 · 귀추 · 유추} · 공리 및 공준 · 증명{증명보조기 · 자동정리증명 · 귀류법 · 수학적 귀납법 · 반증 · 더블 카운팅 · PWW} · 논리함수 · 논리 연산 · 잘 정의됨 · 조건문(조각적 정의) · 명제 논리(명제 · 아이버슨 괄호 · 역 · 이 · 대우) · 양상논리 · 술어 논리(존재성과 유일성) · 형식문법 · 유형 이론 · 모형 이론 | ||
| 집합론 | 집합(원소 · 공집합 · 집합족 · 곱집합 · 멱집합) · 관계(동치관계 · 순서 관계) · 순서쌍(튜플) · 서수(하세 다이어그램 · 큰 가산서수) · 수 체계 · ZFC(선택공리) · 기수(초한기수) · 절대적 무한 · 모임 | ||
| 범주론 | 범주 · 함자 · 수반 · 자연 변환 · 모나드 · 쌍대성 | ||
| 계산가능성 이론 | 계산 · 오토마타 · 튜링 기계 · 바쁜 비버 · 정지 문제 · 재귀함수 | ||
| 정리 | |||
| 드모르간 법칙 · 대각선 논법 · 러셀의 역설 · 거짓말쟁이의 역설 · 뢰벤하임-스콜렘 정리 · 슈뢰더-베른슈타인 정리 · 집합-부분합 정리 · 퍼스의 항진명제 · 굿스타인 정리 · 완전성 정리 · 불완전성 정리(괴델 부호화) · 힐베르트의 호텔 · 연속체 가설 · 퍼지 논리 | |||
| 기타 | |||
| 예비사항(약어 및 기호) · 추상화 · 벤 다이어그램 · 수학철학 | |||
| 틀:논리학 · 틀:이산수학 · 틀:이론 컴퓨터 과학 · 철학 관련 정보 · 논리학 관련 정보 · 수학 관련 정보 | }}}}}}}}} | ||
1. 개요
[math(\{x|x\not\in x\}\in\{x|x\not\in x\})]
Russell's paradox 영국 철학자이자 수학자인 버트런드 러셀이 1901년 제시한 집합론에 대한 역설.
2. 내용
집합 [math(X)]를 다음과 같이 정의한다.[math(X=\{\,X\mid X\notin X\,\})]
이때 [math(X\notin X)] 라면, 조건을 만족하므로 [math(X\in X)]가 된다.
반대로 [math(X\in X)] 라면, 조건을 만족하지 않으므로 [math(X\notin X)]가 된다.
[math(X\in X\iff X\notin X)] 따라서 집합 [math(X)]의 존재는 모순이다.
모순이 발견되었으므로 힐베르트의 소박한 집합론(naive set theory)은 불완전(inconsistent)하다.
2.1. 해설
위의 설명이 이해가 안되면 집합 A의 정의에서 적색으로 강조한 "만", 녹색으로 강조한 "모두", 논증 과정에서 강조한 "그 자신의 정의에 의해"를 주시하자."자기 자신을 포함하지 않는 집합들만 모두 원소로 포함하는 집합 A"를 정의한다. 칸토어의 소박한 집합론에 위배되지 않으므로 이 정의는 성립할 수 있다. 이때 집합 A는 자기 자신을 원소로 포함하는가?
- 만약 집합 A가 자기 자신을 원소로 포함하면, 집합 A는 그 자신의 정의에 의해 자기 자신을 원소로 포함하지 않는다.
- 만약 집합 A가 자기 자신을 원소로 포함하지 않으면, 집합 A는 그 자신의 정의에 의해 자기 자신을 원소로 포함한다.
결론적으로 "집합 A는 자기 자신을 원소로 포함하면서 원소로 포함하지 않는다."는 이 문장은 집합 A가 칸토어의 집합론에 의해 정의될 수 있으므로 정의상 참이지만, 동시에 우리의 직관에 의하면 거짓이다. 즉, 저 결론은 참인 동시에 거짓이므로 이는 모순이다.
다만 위의 설명을 다르게 생각해보면 A라는 집합 안에 a와 ~a가 같이 있게 되는데, a&~a는 집합의 정의상 공집합이 되고, 모든 집합은 공집합을 포함하기 때문에 이발사를 지칭하는 a를 제외한 원소에 대해서는 논리상의 문제가 없다. 즉 말로 표현하자면, 위의 논리는 '이발사 본인에겐 적용되지 않지만 나머지 사람들에겐 적용할 수 있는 것'이 된다.
2.2. 비전공자를 위한 설명
2.2.1. 도서관 사서의 역설
이는 이 역설을 설명하는 비유 중 가장 널리 알려진 것이 원소를 책으로, 집합을 카탈로그로 비유한 도서관 사서가 겪는 역설로 비유하기 때문이다. 도서관 사서의 역설로 위의 내용을 비유하자면 아래와 같다.어떤 도서관 사서가 자신이 근무하는 도서관의 책을 분류하기 위해 카탈로그를 제작하기 시작했다. 그렇게 도서관에 있는 모든 책을 대상으로 카탈로그를 만들고, 카탈로그를 내용으로 하는 카탈로그도 만들면서 도서관의 책과 카탈로그를 이용해서 만든 카탈로그들의 모음을 만들었다.
카탈로그를 전부 만든 도서관 사서는 마지막으로 두 개의 카탈로그를 만들었는데, 이 두 개의 카탈로그는 지금까지 만든 모든 카탈로그를 대상(원소)으로 하는 카탈로그이며, 카탈로그 A는 '자기 자신을 포함하지 않는 카탈로그들의 카탈로그', 카탈로그 B는 '자기 자신을 포함하는 카탈로그들의 카탈로그'로 정의하여 지금까지 만든 카탈로그를 전부 카탈로그로 묶었고 추후 새로 만들어지는 카탈로그도 두 카탈로그 중 하나에 속하도록 만들었다. (당연히 A와 B의 정의는 상반되므로 모든 카탈로그는 A와 B 둘 중 하나에는 반드시 들어가야 한다.)
그렇다면 이 경우 카탈로그 A와 카탈로그 B도 (도서관에 있는 카탈로그이므로) 카탈로그 A와 카탈로그 B 중 하나에 포함시켜야 하는 상황이 발생한다. 이 경우 카탈로그 B는 카탈로그 B에 속해도 문제가 없다. 왜냐하면 카탈로그 B는 카탈로그 B를 원소로 함으로써 '자기 자신을 포함하는 카탈로그'가 되었으며 그렇기 때문에 카탈로그 B에 속해도 아무 문제가 없기 때문이다.
문제는 카탈로그 A는 카탈로그 A에도 B에도 들어갈 수 없다. 만약 카탈로그 A가 카탈로그 A에 속하게 되면 카탈로그 A는 '자기 자신을 포함하는 카탈로그'가 되므로 카탈로그 A에 속할 수 없다. 그러나 카탈로그 A가 카탈로그 B에 속하게 되면 카탈로그 A는 '자기 자신을 포함하지 않는 카탈로그'가 되므로 카탈로그 B에 속할 수 없다. 따라서 이 경우 카탈로그 A는 A에도 B에도 속할 수 없는 카탈로그가 되고, 도서관의 모든 카탈로그는 카탈로그 A와 B 중 하나에 속해야 한다라는 점과 모순이 발생한다.
2.2.2. 이발사의 역설
세비야의 한 (남자) 이발사는 다음과 같이 선언했다.
"앞으로 나는 자기 수염을 '스스로 깎지 않는' 모든 사람들의 수염을 전부 깎아줄 것이오. 다만 '스스로 깎는' 사람은 깎아주지 않겠소."
이때 이 이발사의 수염은 누가 깎아줘야 하는가?
다른 사람이 이 이발사의 수염을 깎아주는 경우 이 이발사는 수염을 '스스로 깎지 않는' 사람에 속하므로, 선언한 바에 따라 자신의 수염을 깎아야 한다.
그러나 스스로 수염을 깎는다면 이 이발사는 수염을 '스스로 깎는' 사람에 속하므로, 선언한 바에 따라 자신의 수염을 깎을 수 없다.
이 이발사는 어찌하면 되는가?
"앞으로 나는 자기 수염을 '스스로 깎지 않는' 모든 사람들의 수염을 전부 깎아줄 것이오. 다만 '스스로 깎는' 사람은 깎아주지 않겠소."
이때 이 이발사의 수염은 누가 깎아줘야 하는가?
다른 사람이 이 이발사의 수염을 깎아주는 경우 이 이발사는 수염을 '스스로 깎지 않는' 사람에 속하므로, 선언한 바에 따라 자신의 수염을 깎아야 한다.
그러나 스스로 수염을 깎는다면 이 이발사는 수염을 '스스로 깎는' 사람에 속하므로, 선언한 바에 따라 자신의 수염을 깎을 수 없다.
이 이발사는 어찌하면 되는가?
이 말을 집합론적으로 옮긴 것이 러셀의 역설이라고 보면 된다.
이 경우 이발사의 역설이 풀리게 되는 재밌는 경우의 수가 있는데, 바로 '이발사가 사람이 아닌 경우'이다.
2.2.3. 거짓말쟁이의 역설
보다 직접적인 자기지시 역설 사례이다.3. 파급력
프레게는 독일의 수리논리학자로 힐베르트의 라이벌이자 동반자였다. 힐베르트와 마찬가지로 "완전한 수학체계"를 만들기 위해 공리계를 처음부터 다듬기 시작했다. 사칙연산으로 이뤄진 공리계를 더욱 엄밀하게 만들기 위해 기수를 '집합의 원소의 개수'로 정의하고[1] 공리계를 집합론을 통해 정리했다.즉, 러셀의 역설을 통해 수학 전체의 기초 공리와 추론의 체계가 뒤집어진 것이다. 때문에 1901년에 이 역설이 영국 학회에 발표되자마자 수학계에서는 말 그대로 헬게이트가 열렸다. 수학의 근간 자체를 흔들어버린 러셀의 역설을 해결하기 위해서 많은 수학자들이 노력했고, 러셀 자신도 이 논리의 허점을 연구하기 시작했다.
다행히도 이 파란은 몇 달 만에 러셀 자신이 해결함으로써 끝을 맺었다. 러셀은 이러한 오류가 만들어진 이유가 "집합"의 정의에 의한 것임을 깨달았다. 지금과 달리 그 당시에는 집합이란 그냥 '원소를 모아놓은 것'이라고만 생각했기 때문에 현대인들은 생각하기 힘든 '자기 자신을 포함하는 집합'이라는 것이 가능했던 것이다.[2] 따라서 러셀은 당시의 집합의 정의와도 크게 모순되지 않으면서 이 역설에서의 문제점을 만들어내기 위해서 '집합'이라는 존재의 정의를 "계형이론"이라는 이론으로 체계적으로 재정비하여 이 모순을 해결했다.
계형이론이란 간단히 말하여 집합에 대해 방정식으로 따지면 "차수"와 같은 개념을 도입시키는 것이다. 즉 1, 2, 3... 및 a, b, c... 같은 단일 개체를 "0계"에 속한다고 하고, 이런 0계의 원소들을 포함하는 집합을 "1계"에 속한다고 하며, 0~1계의 원소들을 포함하는 집합을 "2계"...하는 식으로 집합의 계수를 정의해나갔다. 이렇게 집합마다 계수를 정의하면 "자기 자신을 포함하는 집합"이라는 존재 자체가 불가능하게 된다. 만일 n계의 집합 A가 자기 자신을 포함한다면 A는 계수의 정의에 따라 n-1계 이하의 집합만을 포함해야 하는데 A부터가 이미 n계이므로 A가 A를 포함할 수 없게 되는 것. 단순하면서도 직관적인 이 계형이론은 쉽게 많은 수학자들이 납득했는데, 다행히도 프레게의 논리체계에 흠집 하나 내지 않고 그대로 수용될 수 있었음은 물론이고 러셀의 역설의 근간 자체를 무효로 만들었다.
서술만 보면 러셀의 역설은 단순한 해프닝처럼 보일 수도 있으나 수학계에 미친 영향은 컸다. 러셀이 당시에 사용되던 집합론에 대한 허점을 제시함으로써 당시까지 무류하게 취급되어 사용되던 집합론 역시 무류하지 않다는 사실을 수학자들이 깨닫게 하는 계기가 되었고, 이는 집합을 통한 수학체계 재정비에 앞서 집합론에 대한 공리를 확실히 규정해야 한다는 파급으로 이어져 ZFC 공리계가 탄생하는 계기가 되었다. ZFC에서 러셀의 역설을 해결한 방법은 해당 항목의 분류 공리꼴 문단을 참조하면 된다. 20년 뒤에 ZFC 공리계도, 더 나아가 자연수를 쓰는 공리계는 모두 완전할 수 없다라는 사실이 나와 헬게이트가 좀 일찍 열리고 늦게 열리고의 차이가 되었다는 게 문제지만.
한편 러셀의 제자였던 철학자 비트겐슈타인도 생전 출간된 유일한 저작인 논리철학논고에서 함수는 자기 자신의 독립 변수가 될 수 없다는 점을 들어 이 문제를 해결했다. 정확히는 문제 자체가 무의미함을 보여준 것이다.
함수는 그 자신의 독립 변수가 될 수 없다. 그 이유는 함수 기호는 이미 자기의 독립 변수의 원형을 포함하면서 또 자기 자신을 포함할 수는 없기 때문이다.
요컨대, 함수 F(fx)가 자기 자신의 독립 변수가 될 수 있을 거라고 가정해 보자. 그렇다면 'F(F(fx))'라는 명제가 주어질 것이다. 그런데 이 명제에서 외부 함수 F와 내부 함수 F는 그 가리키는 바가 달라야 한다. 왜냐하면 그 내부 함수는 φ(fx)의 형식을 지니고, 외부 함수는 ψ(φ(fx))의 형식을 지니기 때문이다. 그 두 함수에는 단지 "F"라는 문자만이 공통적인데, 그러나 그 문자는 그 자체로는 아무 것도 가리키지 않는다.
이 점은 만일 우리가 'F(F(u))' 대신에 '(∃φ) : F(φu).φu = Fu'라고 쓴다면 곧 분명해진다.
이로써 러셀의 역설은 풀린다.
러셀의 역설은 자기 자신의 원소가 아닌 집합들의 모든 집합을 R이라 할 때, R = {x │ x ∉ x}에서 "R은 R의 원소인가?"에 대해 묻고 있다. 그러나, x ∉ x를 간단히 fx로 나타내고 'fx에서 x에 어떤 것을 대입시켰을 때 참 문장이 산출된다' (간단히, 'fx는 만족된다')를 F(fx)로 나타내보자. 그렇게 되면, F(fx)와 R이 서로 대응된다. 그리하여 'R은 R의 원소인가?'라는 질문을 'F(F(fx))는 참인가?'로 바꿀 수 있다. 그런데 함수는 자기 자신의 독립변수가 될 수 없으므로 결국 'R은 R의 원소인가?'라는 물음이나 'R은 R의 원소이다'와 같은 표현은 무의미하다.
요컨대, 함수 F(fx)가 자기 자신의 독립 변수가 될 수 있을 거라고 가정해 보자. 그렇다면 'F(F(fx))'라는 명제가 주어질 것이다. 그런데 이 명제에서 외부 함수 F와 내부 함수 F는 그 가리키는 바가 달라야 한다. 왜냐하면 그 내부 함수는 φ(fx)의 형식을 지니고, 외부 함수는 ψ(φ(fx))의 형식을 지니기 때문이다. 그 두 함수에는 단지 "F"라는 문자만이 공통적인데, 그러나 그 문자는 그 자체로는 아무 것도 가리키지 않는다.
이 점은 만일 우리가 'F(F(u))' 대신에 '(∃φ) : F(φu).φu = Fu'라고 쓴다면 곧 분명해진다.
이로써 러셀의 역설은 풀린다.
러셀의 역설은 자기 자신의 원소가 아닌 집합들의 모든 집합을 R이라 할 때, R = {x │ x ∉ x}에서 "R은 R의 원소인가?"에 대해 묻고 있다. 그러나, x ∉ x를 간단히 fx로 나타내고 'fx에서 x에 어떤 것을 대입시켰을 때 참 문장이 산출된다' (간단히, 'fx는 만족된다')를 F(fx)로 나타내보자. 그렇게 되면, F(fx)와 R이 서로 대응된다. 그리하여 'R은 R의 원소인가?'라는 질문을 'F(F(fx))는 참인가?'로 바꿀 수 있다. 그런데 함수는 자기 자신의 독립변수가 될 수 없으므로 결국 'R은 R의 원소인가?'라는 물음이나 'R은 R의 원소이다'와 같은 표현은 무의미하다.