대각선 논법

칸토어의 대각선 논법(對角線 論法, Cantor's diagonal argument)은 실수가 셀 수 있는 무한이 아니라는 것을 보여주기 위해 게오르크 칸토어가 고안한 수학적 증명이다.

자연수와 실수의 농도

자연수 전체집합에서 실수 구간 (0, 1] 로의 전단사 사상(간단히 말해 일대일 대응)이 존재할 수 없다는 것, 다시 말하면 1 이하인 양의 실수 모두를 하나씩 번호를 매길 수 없다는 정리를 대각선 논법을 이용해 증명하면 다음과 같다. 이 증명은 칸토어가 1891년에 얻은 것이다. 칸토어는 이 정리를 이미 1874년 구간 축소법을 이용하여 증명하였고, 대각선 논법을 이용한 다음의 증명은 이전의 증명보다 간단하고, 직관적이다.

증명

귀류법으로 증명한다. 실수에서 구간 (0, 1] 로의 전단사 사상이 존재한다고 가정하자. 그 사상을 $\phi$로 하고, 구간 (0, 1] 에 포함되는 실수는 소수 형태로 쓴다. 다만,

0.1

과 같은 유한소수는

0.09999...

로 쓰도록 해서 실수 하나에는 하나의 소수 표현만이 대응하도록 한다.

가정으로부터 이러한 형태의 임의의 소수에 하나의 번호가 붙을 것이다. 과연 그럴까?

그 수를 순서대로 늘어 놓아 다음과 같이 되었다고 하자.

$\begin{matrix} \phi(0)&=&0.\mathbf{a}_{00}a_{01}a_{02}a_{03}\cdots\\ \phi(1)&=&0.a_{10}\mathbf{a}_{11}a_{12}a_{13}\cdots\\ \phi(2)&=&0.a_{20}a_{21}\mathbf{a}_{22}a_{23}\cdots\\ \vdots & & \vdots \end{matrix}$

여기서 다음과 같은 실수 $A$ 를 생각하자.

$0.b_0 b_1 b_2 b_3 \cdots$

단,

$b_{i} = \left\{ \begin{matrix} 1 & \mbox{if }a_{ii} \ne 1 \\ 2 & \mbox{if }a_{ii} = 1 \end{matrix} \right.$

이렇게 하면, 이것은 (0, 1] 에 들어가 있지만, 어느 $\phi(n)$과도 소수 $n+1$ 째 자리에서 다르다. 이것은 $\phi$가 전사라는 가정에 위배되므로 모순이다.

Q.E.D. 여기에서 대각선은 식에서 굵은 글씨로 처리된 $\mathbf{a_{00}, a_{11}, a_{22},} \cdots$ 등으로, $n$ 번째 소수의 소수 제$n+1$ 자리를 차례차례에 더듬고 간 부분에 해당한다. 실수 전체와 (0, 1] 과의 사이에 전단사 관계는 쉽게 증명할 수 있으며, 따라서 위의 정리는 실수가 가산(可算)이 아니다라는 증명이 된다.

집합과 그 멱집합의 농도

임의의 집합 $X$ 과 그 멱집합 $2^X$ 사이에 전단사가 존재하지 않는 것(칸토어의 정리, 1890년) 역시 대각선 논법을 이용해 증명한다. 이 증명에서는 각각의 집합 $\psi(x)$에 대해서 $x$ 를 포함할지로 항상 다른 집합 $A$를 만들어 내는 점이 대각선을 이용하고 있다.

증명

귀류법을 이용한다. 전단사 사상 $\psi:\, X \to 2^X$ 가 존재한다고 하자. $X$의 한 부분집합 $A$를

$A = \left\{ \begin{matrix} a \notin A & \mbox{if }a \in \psi(a) \\ a \in A & \mbox{if }a \notin \psi(a) \end{matrix} \right.$

로 정의하면, $A \in 2^X$ 이다. $\psi$는 전단사이므로 $X$의 원소 중 어떤 $x$ 에 대해서 $A = \psi(x)$여야 하지만, $x \in \psi(x)$라고 하여도 $x \not\in \psi(x)$ 라고 해도 모두 모순을 일으킨다.

Q.E.D.

실수의 집합은 자연수의 멱집합과 농도가 동일하기 때문에, 최초의 정리는 두 번째 정리의 특별한 경우가 된다.이 정리에 의해, 멱집합의 농도가 원래의 집합보다 커지는 것은 알 수 있지만, 그럼 그 사이에 다른 농도는 존재하는가 하는 문제를 생각할 수도 있고 이것은 연속체 가설로 불리고 있다.

$X$ 를 「모든 집합을 포함한 집합」으로 정의하면, $2^X$은 $X$의 부분 집합이면서도 $X$보다 농도가 커져 모순을 일으킨다. 따라서, 공리적 집합론의 입장에서는 「모든 집합을 포함한 집합」은 집합이 아니다(클래스가 된다). 위의 구성은 러셀의 역설에서 이용되는 「자기 자신을 포함하지 않는 집합」과 비슷하는 것도 상기하라.

같이 보기

• 집합의 크기
• 칸토어의 정리
• 게오르크 칸토어