대각선 논법

이진법에서 비가산 집합의 존재성을 증명하는 칸토어의 대각선 논법을 나타낸 것이다. 아래에 있는 수는 위의 어느 수와도 같을 수 없다.

집합론에서 대각선 논법(對角線論法, 틀:Llang)은 게오르크 칸토어가 실수가 자연수보다 많음을 증명하는 데 사용한 방법이다. 즉, 대각선 논법은 실수의 집합이 비가산 집합임을 보이는 데 사용된다.

자연수와 실수의 집합의 크기

자연수(음이 아닌 정수)의 집합 $\mathbb{N}$과 실수 구간 $(0,1)$ 사이에는 전단사 함수가 존재하지 않으며, 이는 대각선 논법으로 증명할 수 있다. 이는 실수의 집합 $ℝ$이 비가산 집합이라는 명제와 동치이다. 이 명제가 참인지를 묻는 문제는 게오르크 칸토어가 1873년에 리하르트 데데킨트에게 보내는 서신에서 처음 제기하였다. 칸토어는 이 정리를 1874년에 구간 축소법을 이용하여 증명하였으며, 1891년에 대각선 논법을 사용하여 재증명하였다. 대각선 논법을 이용한 증명은 이전의 증명보다 더 간단하며 오늘날 더 널리 알려져 있다.

증명

임의의 함수 $f:\mathbb{N}\to (0,1)$가 주어졌다고 하자. 구간 $(0,1)$에 포함되는 실수는 소수로 표기할 수 있다. 다만, 0.1과 같은 유한 소수는 0.0000…, 0.9999…로 쓰도록 해서 실수 하나에는 하나의 소수 표현만이 대응하도록 한다. 이렇게 표기하였을 때, $f$의 값들이 다음과 같다고 하자.

$f(0)=0.a_{11}{a}_{12}{a}_{13}\cdots$

$f(1)=0.a_{21}{a}_{22}{a}_{23}\cdots$

$f(2)=0.a_{31}{a}_{32}{a}_{33}\cdots$

$⋮$

다음과 같은 실수 $r\in (0,1)$를 생각하자.

$r=0.b_1{b}_2{b}_3\cdots$

여기서 $b_i$는 다음과 같다.

$b_i=\{\begin{array}{cc}1& a_{ii}\ne 1\\ 2& a_{ii}=1\end{array}$

그렇다면 임의의 $n\in \mathbb{N}$에 대하여, $r$는 $f(n)$과 소수점 뒤 $n+1$번째 자리에서 다르므로, $r\ne f(n)$이다. 즉, $r$는 $f$의 치역에 포함되지 않으며, $f$는 전사 함수가 아니다. 즉, 전사 함수 $\mathbb{N}\to (0,1)$는 존재하지 않으며, 모든 전단사 함수는 전사 함수이므로 이 역시 존재하지 않는다. 전단사 함수 $(0,1)\to ℝ$는 자명하게 존재하므로, 전단사 함수 $\mathbb{N}\to ℝ$ 역시 존재하지 않는다.

다른 방법의 증명

틀:참고 다음 증명은 대각선 논법을 사용하지 않는다. 구간 $(0,1)$의 임의의 부분 집합 $S\subseteq (0,1)$에 대하여, 갑과 을이 다음과 같은 규칙의 게임을 한다고 가정하자.

• 갑과 을은 번갈아 가며 실수를 취한다.
• 우선 갑이 $x_0=0$을 취하고, 그 뒤 을이 $y_0=1$을 취한다.
• $x_{n-1},y_{n-1}$이 선택되었을 때, 먼저 갑이 임의의 $x_n\in (x_{n-1},y_{n-1})$을 취하고, 을은 임의의 $y_n\in (x_n,y_{n-1})$를 취한다.
• 이 경우, $(x_n{)}_{n=0}^{\mathrm{\infty }}$는 수렴하며, $\underset{n\to \mathrm{\infty }}{\lim }{x}_n\in (0,1)$이다. 만약 $\underset{n\to \mathrm{\infty }}{\lim }{x}_n\in S$라면 갑이 승리하며, 만약 $\underset{n\to \mathrm{\infty }}{\lim }{x}_n\in ̸S$라면 을이 승리한다.

만약 $S=\{s_1,s_2,\dots \}$가 가산 집합일 경우, 다음과 같은 을의 필승 전략이 존재한다. 임의의 $n\in {\mathbb{Z}}^{+}$에 대하여,

• 만약 $n\le |S|$이며 $s_n\in (x_n,y_{n-1})$라면, 을은 $n$번째 실수로 $y_n=s_n$을 취한다.
• 만약 $n>|S|$이거나 $s_n\in ̸(x_n,y_{n-1})$라면, 을은 $n$번째 실수로 임의의 $y_n\in (x_n,y_{n-1})$을 취한다.

그러나 $S=(0,1)$일 경우 항상 갑이 승리하므로, 을은 필승 전략을 가지지 않는다. 따라서 $(0,1)$은 비가산 집합이다.

멱집합의 크기

틀:본문 칸토어의 정리(1890년)에 따르면, 임의의 집합 $X$ 과 그 멱집합 $𝒫(X)$ 사이에는 전단사 함수가 존재하지 않는다. 이 역시 대각선 논법을 이용해 증명할 수 있다. 이 증명에서는 각각의 집합 $\psi (x)$에 대해서 $x$를 포함할지로 항상 다른 집합 $A$를 만들어 내는 점이 대각선을 이용하고 있다. 이 정리에 의해, 멱집합의 크기가 원래의 집합보다 커지는 것은 알 수 있지만, 그럼 그 사이에 다른 크기는 존재하는가 하는 문제를 생각할 수도 있고 이것은 연속체 가설로 불리고 있다.

만약 모든 집합의 집합 $V$가 존재한다면, $𝒫(V)$는 $V$의 부분 집합이면서도 $V$보다 크기가 커져 모순을 일으킨다. 이를 칸토어 역설이라고 한다. 따라서, 공리적 집합론에서는 모든 집합을 포함한 집합이 존재하지 않는다. 대신 모든 집합의 고유 모임은 존재하며, 폰 노이만 전체라고 불린다.

증명

임의의 집합 $X$에 대하여, 함수

$f:X\to 𝒫(X)$

가 주어졌다고 하자. 그렇다면

$A=\{x\in X:x\in ̸f(x)\}\subset X$

를 정의하자. 그렇다면 다음 두 명제를 쉽게 보일 수 있다.

• 임의의 $a\in A$에 대하여, $A\ne f(a)$이다.
  • 정의에 따라서 $a\in ̸f(a)$이다. 그러나 $a\in A$이므로, $A\ne f(a)$이다.
• 임의의 $b\in X\setminus A$에 대하여, $A\ne f(b)$이다.
  • 정의에 따라서 $b\in f(b)$이다. 그러나 이 경우 $b\in ̸A$이므로, $A\ne f(b)$이다.

따라서 $A$는 $f$의 상에 포함되지 않는다. 즉, $f$는 전사 함수가 아니다. 따라서, $X$와 $𝒫(X)$ 사이에 전사 함수가 존재하지 않으며, 모든 전단사 함수는 전사 함수이므로 역시 존재하지 않는다.

위의 구성은 러셀의 역설에서 이용되는 자기 자신을 포함하지 않는 집합 $\{S:S\in ̸S\}$과 유사하다.

같이 보기

• 집합의 크기

참고 문헌

• (흥미있는 수학 이야기 -이만근,오은영 2007)http://shop.mathlove.kr/shop/goods/goods_view.php?&goodsno=472&category=004001
• (Georg Cantor (1891). "Ueber eine elementare Frage der Mannigfaltigkeitslehre". Jahresbericht der Deutschen Mathematiker-Vereinigung. 1: 75–78. English translation: Ewald, William B. (ed.) (1996). From Immanuel Kant to David Hilbert: A Source Book in the Foundations of Mathematics, Volume 2. Oxford University Press. pp. 920–922. ISBN 0-19-850536-1.-Ueber eine elementare Frage der Mannigfaltigketislehre.
• Jahresbericht der Deutschen Mathematiker-Vereinigung / Zeitschriftenband (1890/91) / Artikel / 75 - 78