영국 철학자이자 수학자인 버트런드 러셀이 제시한 집합론에 대한 역설. "도서관 사서의 역설"이라고도 한다. 역설의 전체적인 흐름은 흔히 알려진 이발사의 역설과 같다.
세빌리아의 한 (남자) 이발사는 다음과 같이 선언했다."앞으로 나는 자기 수염을 스스로 깎지 않는 사람들의 수염을 전부 깎아줄 것이오. 다만 스스로 깎는 사람은 잘라주지 않겠소."
이 때 이 이발사의 수염은 누가 잘라줘야 하는가?
다른 사람이 이 이발사의 수염을 깎아준다면 이 이발사는 수염을 스스로 깎지 않았으니 이 이발사는 자신이 자신의 수염을 깎아줘야 할 것이다.
그러나 자신이 수염을 깎는다면 자신은 수염을 스스로 깎는 사람이 되므로 자신이 수염을 자를 수 없다.
이 이발사는 어찌하면 되는가?
수염을 기르면 된다고 생각해...
아니 딴 이발사에게서 깎으면 되잖아
이 이발사의 이야기를 집합론적으로 옮긴 것이 러셀의 역설이라고 보면 된다. 본격적인 러셀의 역설은 아래와 같다.
어떠한 집합으로 이뤄진 한 집합군 S에서 두가지 새로운 집합을 새로 추가하자. "자기 자신을 포함하는 집합들을 포함하는 집합 A"와 "자기 자신을 포함하지 않는 집합들을 포함하는 집합 B"의 두 가지이다.[1]
이 때 집합 B는 자기 자신인 B를 원소로 가지고 있는가?
결론을 먼저 서술하자면, 이 명제는 참이든 거짓이든 모순이다. 따라서 귀류법에 따라 가정에서 내세운 A나 B의 집합은 존재할 수 없다.
해당 명제가 어느 경우에도 모순이란 것을 각각 확인해보자. 만약 명제가 참이라면 (즉 B가 B를 원소로 갖는다면) B의 정의에 (자기 자신을 원소로 갖지 않는 집합) 모순된다.
그러나 만약 해당 명제가 거짓이면 (즉 B가 B를 원소로 갖지 않는다면) B의 정의에 (자기 자신을 원소로 갖지 않는 집합) 따라 B는 B의 원소이다. 이는 "B가 B를 원소로 갖지않는다"는 가정에 모순이다.
결국 "어떠한 종류의 집합을 모두 포함하는 하나의 집합"을 가정해서 생긴 문제이며 귀류법에 따라 그러한 집합이 존재할 수 없음을 나타낸다. 곧, 러셀의 역설을 만족하는 이발사는 있을 수 없다.
이 결론은 집합을 통해 쌓아올려진 프레게의 논리체계의 모순을 의미한다.
프레게는 독일의 수리논리학자로 힐베르트의 라이벌이자 동반자였다. 힐베르트와 마찬가지로 "완전한 수학체계"를 만들기 위해 공리계를 처음부터 다듬기 시작했다. 사칙연산으로 이뤄진 공리계를 더욱 엄밀하게 만들기 위해 기수를 '집합의 원소의 개수'로 정의하고[2] 공리계를 집합론을 통해 정리했다.
즉, 러셀의 역설을 통해 수학 전체의 기초 공리와 추론의 체계가 뒤집어진 것이다. 때문에 1901년에 이 역설이 영국 학회에 발표되자마자 수학계에서는 말 그대로 헬게이트가 열렸다. 수학의 근간 자체를 흔들어버린 러셀의 역설을 해결하기 위해서 많은 수학자들이 노력했고, 러셀 자신도 이 논리의 허점을 연구하기 시작했다.
다행히도 이 파란은 몇 달 만에 러셀 자신이 해결함으로서 끝을 맺었다. 러셀은 이러한 오류가 만들어진 이유가 "집합"의 정의에 의한 것임을 깨달았다. 지금과 달리 그 당시에는 집합이란 그냥 '원소를 모아놓은 것'이라고만 생각했기 때문에 현대인들은 생각하기 힘든 '자기 자신을 포함하는 집합'이라는 것이 가능했던 것이다.[3] 따라서 러셀은 당시의 집합의 정의와도 크게 모순되지 않으면서 이 역설에서의 문제점을 만들어내기 위해서 '집합'이라는 존재의 정의를 "계형이론"이라는 이론으로 체계적으로 재정비하여 이 모순을 해결했다.
계형이론이란 간단히 말하여 집합에 대해 방정식으로 따지면 "차수"와 같은 개념을 도입시키는 것이다. 즉 1, 2, 3... 및 a, b, c같은 단일 개체를 "0계"에 속한다고 하고, 이런 0계의 원소들을 포함하는 집합을 "1계"에 속한다고 하며, 0~1계의 원소들을 포함하는 집합을 "2계"...하는 식으로 집합의 계수를 정의해나갔다. 이렇게 집합마다 계수를 정의하면 "자기 자신을 포함하는 집합"이라는 존재 자체가 불가능하게 된다. 만일 n계의 집합 A가 자기 자신을 포함한다면 A는 계수의 정의에 따라 n-1계 이하의 집합만을 포함해야하는데 A부터가 이미 n계이므로 A가 A를 포함할 수 없게 되는 것.
단순하면서도 직관적인 이 계형이론은 쉽게 많은 수학자들이 납득했는데, 다행히도 프레게의 논리체계에 흠집 하나 내지 않고 그대로 수용될 수 있었음은 물론이고 러셀의 역설의 근간 자체를 뿌리뽑아버렸기 때문이다. 프레게와 힐베르트는 안도했고, 수학체계의 연구는 다시 차근차근 진행되기 시작했다.
...20년 뒤에 불완전성 정리라는 폭풍이 불어닥칠 것을 예상하지 못한 채로 말이다.
한편 러셀의 제자였던 철학자 비트겐슈타인 도 생전 출간된 유일한 저작인 논리철학논고에서 함수는 자기 자신의 독립 변수[논항]가 될 수 없다는 점을 들어 이 문제를 해결하였다.[4]
3.333 함수는 그 자신의 독립 변수[논항]가 될 수 없다. 그 이유는 함수 기호는 이미 자기의 독립 변수[논항]의 원형을 포함하면서 또 자기 자신을 포함할 수는 없기 때문이다.
요컨대, 함수 F(fx)가 자기 자신의 독립 변수가 될 수 있을 거라고 가정해 보자. 그렇다면 "F(F(fx))"라는 명제가 주어질 것이다. 그런데 이 명제에서 외부 함수 F와 내부 함수 F는 그 가리키는 바가 달라야 한다. 왜냐하면 그 내부 함수는 φ(fx)의 형식을 지니고, 외부 함수는 ψ(φ(fx))의 형식을 지니기 때문이다. 그 두 함수에는 단지 "F"라는 문자만이 공통적인데, 그러나 그 문자는 그 자체로는 아무 것도 가리키지 않는다.
이 점은 만일 우리가 "F(F(u))" 대신에 "(∃φ) : F(φu).φu = Fu"라고 쓴다면 곧 분명해진다.
이로써 러셀의 역설은 풀린다.