대각선 논법

이진법에서 비가산 집합의 존재성을 증명하는 칸토어의 대각선 논법을 나타낸 것이다. 아래에 있는 수는 위의 어느 수와도 같을 수 없다. 집합론에서 **대각선 논법**(對角線論法, diagonal argument)은 게오르크 칸토어가 실수가 자연수보다 많음을 증명하는 데 사용한 방법이다. 즉, 대각선 논법은 실수의 집합이 비가산 집합임을 보이는 데 사용된다.
# 자연수와 실수의 집합의 크기
자연수(음이 아닌 정수)의 집합 \mathbb N과 실수 구간 (0,1) 사이에는 전단사 함수가 존재하지 않으며, 이는 대각선 논법으로 증명할 수 있다. 이는 실수의 집합 \mathbb R이 비가산 집합이라는 명제와 동치이다. 이 명제가 참인지를 묻는 문제는 게오르크 칸토어가 1873년에 리하르트 데데킨트에게 보내는 서신에서 처음 제기하였다. 칸토어는 이 정리를 1874년에 구간 축소법을 이용하여 증명하였으며, 1891년에 대각선 논법을 사용하여 재증명하였다.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.- https://www.digizeitschriften.de/dms/img/?PID=GDZPPN002113910&physid;=phys84#navi 대각선 논법을 이용한 증명은 이전의 증명보다 더 간단하며 오늘날 더 널리 알려져 있다.
## 증명
임의의 함수 f\colon\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 :\vdots 다음과 같은 실수 r\in(0,1)를 생각하자. :r=0.b_1b_2b_3\cdots 여기서 b_i는 다음과 같다. :b_i=\begin{cases}1&a;_{ii}\ne 1\\\2&a;_{ii}=1\end{cases} 그렇다면 임의의 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 R는 자명하게 존재하므로, 전단사 함수 \mathbb N\to\mathbb R 역시 존재하지 않는다.
## 다른 방법의 증명
다음 증명은 대각선 논법을 사용하지 않는다. 구간 (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}^\infty는 수렴하며, \textstyle\lim_{n\to\infty}x_n\in(0,1)이다. 만약 \textstyle\lim_{n\to\infty}x_n\in S라면 갑이 승리하며, 만약 \textstyle\lim_{n\to\infty}x_n\not\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\not\in(x_n,y_{n-1})라면, 을은 n번째 실수로 임의의 y_n\in(x_n,y_{n-1})을 취한다. 그러나 S=(0,1)일 경우 항상 갑이 승리하므로, 을은 필승 전략을 가지지 않는다. 따라서 (0,1)은 비가산 집합이다.
# 멱집합의 크기
칸토어의 정리 칸토어의 정리(1890년)에 따르면, 임의의 집합 X 과 그 멱집합 \mathcal P(X) 사이에는 전단사 함수가 존재하지 않는다. 이 역시 대각선 논법을 이용해 증명할 수 있다. 이 증명에서는 각각의 집합 \psi(x)에 대해서 x를 포함할지로 항상 다른 집합 A를 만들어 내는 점이 대각선을 이용하고 있다. 이 정리에 의해, 멱집합의 크기가 원래의 집합보다 커지는 것은 알 수 있지만, 그럼 그 사이에 다른 크기는 존재하는가 하는 문제를 생각할 수도 있고 이것은 연속체 가설로 불리고 있다. 만약 모든 집합의 집합 V가 존재한다면, \mathcal P(V)는 V의 부분 집합이면서도 V보다 크기가 커져 모순을 일으킨다. 이를 **칸토어 역설**이라고 한다. 따라서, 공리적 집합론에서는 모든 집합을 포함한 집합이 존재하지 않는다. 대신 모든 집합의 고유 모임은 존재하며, 폰 노이만 전체라고 불린다.
## 증명
임의의 집합 X에 대하여, 함수 :f\colon X \to\mathcal P(X) 가 주어졌다고 하자. 그렇다면 :A=\\{x\in X\colon x\not\in f(x)\\}\subset X 를 정의하자. 그렇다면 다음 두 명제를 쉽게 보일 수 있다. * 임의의 a\in A에 대하여, A\ne f(a)이다. ** 정의에 따라서 a\not\in f(a)이다. 그러나 a\in A이므로, A\ne f(a)이다. * 임의의 b\in X\setminus A에 대하여, A\ne f(b)이다. ** 정의에 따라서 b\in f(b)이다. 그러나 이 경우 b\not\in A이므로, A\ne f(b)이다. 따라서 A는 f의 상에 포함되지 않는다. 즉, f는 전사 함수가 아니다. 따라서, X와 \mathcal P(X) 사이에 전사 함수가 존재하지 않으며, 모든 전단사 함수는 전사 함수이므로 역시 존재하지 않는다. 위의 구성은 러셀의 역설에서 이용되는 자기 자신을 포함하지 않는 집합 \\{S\colon S\not\in S\\}과 유사하다.