대각선 논법

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

칸토어의 대각선 논법(對角線 論法, 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^XX의 부분 집합이면서도 X보다 농도가 커져 모순을 일으킨다. 따라서, 공리적 집합론의 입장에서는 「모든 집합을 포함한 집합」은 집합이 아니다(클래스가 된다). 위의 구성은 러셀의 역설에서 이용되는 「자기 자신을 포함하지 않는 집합」과 비슷하는 것도 상기하라.

같이 보기[편집]