러셀의 역설(Russell's paradox)

대부분의 집합은 자기 자신을 원소로 갖지 않습니다. {1, 2}의 원소는 1과 2뿐이고, 자연수⁠(natural number)⁠ 전체의 집합 ℕ은 자연수가 아니므로 $\mathbb{N} \notin \mathbb{N}$입니다. 그런데 '어떤 조건이든 그 조건을 만족하는 것을 모두 모으면 집합이 된다'는 소박한 생각을 따르면, 자기 자신을 원소로 갖는 집합도 생깁니다. 모든 집합을 모은 집합 V는 그 자체가 집합이니 $V \in V$입니다. 원소가 셋 이상인 집합들을 모은 집합 T도 원소가 셋보다 훨씬 많으니 $T \in T$입니다.

1901년 버트런드 러셀은 자기 자신을 원소로 갖지 않는 집합을 모두 모은 집합 $R = \{x : x \notin x\}$을 생각하고 물었습니다. R은 R의 원소일까요? 그림에서 R을 누르거나 여기서 R의 자리를 바꿔 보세요: . 어느 쪽에 두어도 규칙이 반대쪽으로 보냅니다. $R \in R$이면 $R \notin R$이고, 그 반대도 마찬가지입니다.

같은 구조를 이야기로 바꿀 수 있습니다. "마을의 이발사는 스스로 면도하지 않는 사람을, 그리고 그런 사람만 면도해 준다." 이발사는 스스로 면도할까요? 이발사 이야기는 "그런 이발사는 있을 수 없다"로 끝나면 그만입니다. 하지만 집합론은 그렇게 넘어갈 수 없었습니다. R을 정하는 조건 $x \notin x$는 흠잡을 데 없어 보였고, 그런 조건으로 집합을 만드는 것이 당시 논리학의 기본 원리였기 때문입니다.

이 논증은 칸토어의 대각선 논법⁠(Cantor's diagonal argument)⁠과 같은 모양입니다. 칸토어는 집합 A에서 멱집합⁠(power set)⁠으로 가는 어떤 함수⁠(function)⁠ f도 모든 부분집합⁠(subset)⁠에 닿지 못함을, 부분집합 $\{x \in A : x \notin f(x)\}$으로 보였습니다. 그래서 멱집합은 언제나 원래 집합보다 크기가 큽니다. 러셀 자신의 회고에 따르면, 그는 가장 큰 무한이 없다는 칸토어의 이 증명을 '모든 것의 집합'에 적용해 보다가 역설에 이르렀습니다. 1902년 6월 러셀이 편지로 이 역설을 알렸을 때, 독일의 논리학자 고틀로프 프레게는 산술을 논리 위에 세우려던 『산술의 기본 법칙』 2권을 인쇄하던 중이었고, 부록에서 자기 체계에 이 결함이 있음을 인정했습니다.

수학자들은 집합을 만드는 규칙을 좁혀서 역설을 피했습니다. 1908년 에른스트 체르멜로는 집합에 대해 무엇을 허락하는지를 몇 개의 공리⁠(axiom)⁠로 못 박은 공리적 집합론⁠(axiomatic set theory)⁠을 내놓았습니다. 1920년대 아브라함 프렝켈과 토랄프 스콜렘 등이 여기에 치환 공리⁠(axiom of replacement)⁠를 보탠 체계가 ZF(체르멜로–프렝켈)입니다. ZF에 선택공리(Choice)를 넣은 ZFC가 오늘날 수학의 표준 바탕입니다. 선택공리는 체르멜로의 1908년 공리에 이미 들어 있었지만, 쓰임을 따로 따지려고 이름에 C를 붙여 구별합니다. 이 체계에서는 조건만으로 집합을 만들 수 없고, 이미 있는 집합 A 안에서 $\{x \in A : \text{조건}\}$을 골라낼 수만 있습니다(분리 공리⁠, axiom schema of separation⁠). 그러면 $\{x \in A : x \notin x\}$는 집합이지만, 같은 논증이 이 집합은 A의 원소일 수 없음을 보여 줍니다. 결국 무엇이든 담는 '모든 집합의 집합'은 없다는 결론이 됩니다. 러셀 자신은 영국 수학자·철학자 앨프리드 노스 화이트헤드와 함께 쓴 『수학 원리』(1910–1913)에서 타입 이론⁠(type theory)⁠으로 답했습니다. 대상을 개체, 개체의 집합, 집합의 집합, … 하는 식으로 층을 나누고, 집합은 바로 아래층의 것만 원소로 가질 수 있게 하는 것입니다. 그러면 '$x \in x$'는 참도 거짓도 아닌, 애초에 적을 수 없는 식이 됩니다.

이어지는 곳. 자기 자신에 대해 말하는 구조는 20세기 논리학의 큰 결과마다 다시 나타납니다. 괴델의 불완전성 정리⁠(Gödel's incompleteness theorems)⁠에서는 '나는 증명할 수 없다'는 문장이, 정지 문제⁠(halting problem)⁠에서는 자기 코드를 입력받으면 반대로 행동하는 프로그램이 같은 역할을 합니다. 미국 논리학자 알론조 처치가 람다 계산⁠(lambda calculus)⁠을 담으려던 초기 논리 체계도 비슷한 역설로 모순임이 드러났습니다. 1969년 로베어는 칸토어, 러셀, 괴델, 튜링의 대각선 논법⁠(diagonal argument)⁠을 데카르트 닫힌 범주⁠(cartesian closed category)⁠의 고정점 정리⁠(fixed-point theorem)⁠ 하나로 묶어, 이 논증들이 같은 구조임을 보였습니다. 러셀의 역설 같은 모순이 드러나자 수학을 무엇 위에 어떻게 세워야 하는지를 두고 논쟁이 벌어졌는데, 이것이 수학 기초론 논쟁⁠(debate on the foundations of mathematics)⁠입니다. 로베어는 1964년 원소와 ∈ 대신 함수와 합성만으로 집합론을 적는 다른 기초⁠(basics)⁠를 내놓았고, 그 공리 가운데 일부만 남긴 세계가 토포스⁠(topos)⁠입니다. ZFC는 알려진 역설을 막았지만, ZFC에 모순이 없다면 그 안에서 증명도 반증도 할 수 없는 문장이 남아 있습니다. 자연수보다 크고 실수⁠(real number)⁠보다 작은 크기의 무한집합이 있느냐를 묻는 연속체 가설⁠(continuum hypothesis)⁠이 대표적입니다.