📂집합론

칸토어의 대각선 논법

정리 ¹

열린 구간 $(0,1)$ 은 비가산집합이다.

증명

실수 집합 $\mathbb{R}$ 은 가산 집합이 아닌데, 이것은 실수 집합과 어떤 가산 집합 사이에 ‘일대일 대응’이 존재하지 않음을 통해서 보인다. 이는 자연수 집합과 열린 구간 $(0,1)$ 사이에 일대일 대응이 존재하지 않는 것을 보이고, 그 따름정리로써 얻을 수 있다.

칸토어는 이것을 놀라운 방법으로 증명해냈고, 이 방법은 ‘대각선 논법’이라는 이름과 함께 칸토어의 업적으로 남았다. 결과를 떠나 그 자체로 아름다움을 느낄 수 있는 증명이니 몇 번 읽어서 이해가 안가더라도 이해가 될 때까지 읽어보도록 하자.

증명

일대일 대응 $f : \mathbb{N} \to (0,1)$ 이 존재한다고 가정하면 ${ a } _{ ij }$ 를 소수점 아래 $j$번째 숫자로 썼을 때 다음과 같이 나타낼 수 있다. $$f(i)=0. { a } _{ i1 } { a } _{ i2 } { a } _{ i3 } { a } _{ i4 } \cdots$$ 그러면 자연수 $i \in \mathbb{N}$ 에 대해서 $$f(1)=0. { a } _{ 11 } { a } _{ 12 } { a } _{ 13 } { a } _{ 14 } \cdots \\ f(2)=0. { a } _{ 21 } { a } _{ 22 } { a } _{ 23 } { a } _{ 24 } \cdots \\ f(3)=0. { a } _{ 31 } { a } _{ 32 } { a } _{ 33 } { a } _{ 34 } \cdots \\ \vdots \\ f(k)=0. { a } _{ k1 } { a } _{ k2 } { a } _{ k3 } { a } _{ k4 } \cdots \\ \vdots$$ 와 같은 배열로 나타낼 수 있을 것이다. 여기서 $z \in (0,1)$ 을 다음과 같이 정의하자. $$z=0. { z } _{ 1 } { z } _{ 2 } { z } _{ 3 } { z } _{ 4 } \cdots, \left( { z } _{ j } = \begin{cases} 2 & { a } _{ jj } \text{가 홀수일 때} \\ 1 & { a } _{ jj } \text{가 짝수일 때} \end{cases} \right)$$ 이는 위의 배열에서 대각선에 위치한 수인 $a_{11} , a_{22} , \cdots$ 들과 홀짝이 반대가 되는 수를 뽑는 것이다. $z$ 와 $f(i)$ 소수점 아래 $i$번째 자리 숫자가 홀수인지 짝수인지만 살펴 보자. ${ z }_{ i }$ 가 짝수면 ${ a } _{ ii }$ 가 홀수고, $\ { z } _{ i }$가 홀수면 ${ a } _{ ii }$ 가 짝수기 때문에 $$z\neq f(1) \\ z\neq f(2) \\ z\neq f(3) \\ \vdots \\ z\neq f(k) \\ \vdots$$ 이다. 모든 자연수 $i$ 에 대해 $z \neq f(i)$ 이므로 $z \notin f(\mathbb{N})$ 인데, $f$ 는 일대일 대응이므로 $f(\mathbb{N})=(0,1)$ 이고 $z \in (0,1)$ 이므로 $z\in f(\mathbb{N})$ 이어야한다. 이는 가정에 모순이므로, 일대일 대응 $f : \mathbb{N} \to (0,1)$ 은 존재하지 않는다.

■