1. 대각선 논법
시작하기에 앞서 칸토어 역설을 설명하는 과정에 필요한 대각선 논법(Diagonal argument)를 알고 넘어가자.
대각선 논법은 칸토어가 고안한 수학적 증명 방법으로 실수 집합의 크기가 무한하다 즉, 실수 집합은 비가산집합이라는 것을 증명했다. 실제로 실수 집합은 자연수 집합과 같은 크기인 $\left \vert \mathbb{R} \right \vert = \left \vert \mathbb{N} \right \vert = \aleph_{0}$이다.
1.1. 실수 집합의 비가산성 증명
대각선 논법을 이해하기 위해 실수 집합의 비가산성을 증명해 보자.
편의를 위해 실수 집합의 부분집합 $(0, 1)$을 잡자. 해당 집합이 가산집합이라면 자연수 집합 $\mathbb{N}$과의 전단사함수가 존재해야 한다. 이러한 함수를 $f: \mathbb{N} \rightarrow (0, 1)$라 하자.
실수는 무한 소수로 표현할 수 있으므로 $a_{nm} \in \left \{ n \in \mathbb{N} \vert 0 \le n \le 9 \right \}$이라 할 때 $f$를 다음과 같이 보일 수 있다.
$f(1) = 0.a_{11}a_{12}a_{13}a_{14}\dots$
$f(2) = 0.a_{21}a_{22}a_{23}a_{24}\dots$
$f(3) = 0.a_{31}a_{32}a_{33}a_{34}\dots$
$\dots$
이때, 다음과 같은 수 $b$를 생각해 보자.
\[b = 0.b_1b_2b_3b_4\dots\] \[b_i = \left\{\begin{matrix} 0 & a_{ii} = 1\\ 1 & a_{ii} \ne 1 \end{matrix}\right.\]따라서 $b$는 $b_n$의 값이 $f(n)$의 $n$번째 수와 다르기 때문에 $f(n)$과 다름이 보장된다. 이는 모든 $n$에 대해 성립하므로 $b$는 $f$의 치역에 속하지 않음을 알 수 있다. 따라서 $f$는 전사함수가 아니고 이는 $f$가 전사함수라는 전제에 모순된다. 고로 귀류법에 의해 실수의 부분집합 $(0, 1)$는 비가산 집합이다. 이에 따라 $(0, 1)$를 부분집합으로 가지는 $\mathbb{R}$또한 비가산집합이다.
결국 대각선 논법은 모든 원소들을 2차 텐서(각 row vector 또는 column vector가 각 원소를 나타낸다)로 표현한 후 대각선 방향으로 각 원소와의 특정 조건을 만족시키면서 새로운 원소를 만들어 내는 과정을 통해 원하는 바를 증명하는 방법이다.
2. 대각선 논법을 이용한 칸토어 정리 증명
칸토어의 정리는 다음과 같다.
집합 $X$의 멱집합(Power set) $\mathcal{P}(X)$에 대해 $\left \vert X \right \vert < \left \vert \mathcal{P}(X) \right \vert$를 만족한다.
여기서 어떤 집합의 멱집합이란, 어떤 집합의 모든 부분집합을 포함하는 집합을 말한다. 예를 들어, $X = \left \{ x, y, z \right \}$라고 하면 집합 $X$의 멱집합 $\mathcal{P}(X)$는 다음과 같다.
\[\mathcal{P}(X) = \left \{ \left \{ \right \}, \left \{ x \right \}, \left \{ y \right \} , \left \{ z \right \}, \left \{ x, y \right \}, \left \{ y, z \right \}, \left \{ x, z \right \}, \left \{ x, y, z \right \}\right \}\]이제 칸토어의 정리를 대각선 논법을 이용해 증명해 보자.
$X$에 속한 모든 원소들을 $x_i$로 표현한다. 그렇다면 $X$의 임의의 부분집합 $A$는 다음과 같은 벡터 $a$로 표현할 수 있다.
\[a_i = \left\{\begin{matrix} 0 & \text{if } x_i \in A \\ 1 & \text{if } x_i \notin A \end{matrix}\right.\]벡터 $a$는 집합 $A$를 유일하게 표현한다. 이러한 벡터를 ‘집합 표현 벡터’ 라고 하자.
칸토어 집합이 거짓이라면, $\left \vert X \right \vert \ge \left \vert \mathcal{P}(X) \right \vert$ 일 것이고 $f: X \rightarrow \mathcal{P}(X)$인 전사 함수 $f$가 존재한다. $\mathcal{P}(X)$에 속한 모든 원소 집합들은 집합 $X$의 부분집합이므로 위와 같이 집합 표현 벡터로 표현할 수 있다. 따라서 $f$를 $\mathcal{P}(X)$의 각 원소 집합의 집합 표현 벡터를 원소로 가지고 있는 집합 $V(\mathcal{P}(X))$에 대해 $f: X \rightarrow V(\mathcal{P}(X))$로 정의해도 $f$는 전사 함수를 만족해야 한다.
이때, 다음과 같은 벡터 $v$를 생각해 보자.
\[v_i = \left\{\begin{matrix} 0 & \text{if } f_i(i) = 1 \\ 1 & \text{if } f_i(i) = 0 \end{matrix}\right.\]그렇다면 이로부터 만들어지는 벡터 $v$는 $f$의 치역에 속하지 않는다. 이는 $f$가 전사 함수라 가정한 것에 모순되므로 $f$는 전사 함수가 아니다. 따라서 $\left \vert X \right \vert < \left \vert \mathcal{P}(X) \right \vert$이며 이는 칸토어의 정리가 참임을 보이는 결과이다.
3. 칸토어 역설
칸토어의 정리는 어떤 집합의 부분집합을 모두 포함하는 집합은 어떤 집합보다 크다는 것을 보인다.
그렇다면 모든 집합들의 집합에 대해서도 성립할까?
집합 $V$가 모든 집합들의 모임인 집합이라 하자. 그렇다면 집합 $V$의 멱집합 $\mathcal{P}(V)$는 칸토어의 정리에 의해 다음과 같다.
\[\left \vert V \right \vert < \left \vert \mathcal{P}(V) \right \vert\]그러나, $V$는 모든 집합들의 모임이므로, $\mathcal{P}(V) = V$를 만족하기 때문에 다음과 같다.
\[\left \vert V \right \vert < \left \vert \mathcal{P}(V) \right \vert = \left \vert V \right \vert\]이는 $\left \vert V \right \vert < \left \vert V \right \vert$임을 나타내고 이는 모순되는 결과이다.
해당 결과는 집합론 조차 비모순성을 증명할 수 없음을 보인다. 이러한 결과는 괴델의 불완전성 원리로 나아가고 튜링 머신을 탄생하게 하는 결과를 가져온다.
컴퓨터 과학의 탄생 이면에는 이러한 초수학적 내용이 숨어있다.
이와 비슷한 역설로는 부랄리포르티 역설(Burali-Forti paradox)을 들을 수 있다.