집합론, 그 스물일곱 번째 이야기 | 칸토어 정리 ( Cantor's Theorem )

이번 글에서는 칸토어 정리를 소개하고 그것을 증명할 것이다. 칸토어 정리(Cantor's Theorem)는 다음과 같다.

 

임의의 기수 $\kappa$에 대해 언제나 $2^\kappa>\kappa$가 성립한다.

 

일단 서술의 편의성을 위해 다음과 같은 간단한 개념을 정의하자.

 

집합 $X$와 그의 부분집합 $A$에 대해 다음과 같은 함수 $\mathbf{1}_A:X\to\{0,1\}$를 집합 $A$에 대한 Indicator Function이라고 한다. $$\mathbf{1}_A(x)=\begin{cases}0&\mbox{if }x\notin A\\1&\mbox{if }x\in A\end{cases}$$

 

위 명제를 증명하기에 앞서 다음 두 명제를 살펴보자.

 

Lemma 1. $|\mathcal{P}(X)|=2^{|X|}$

 

위 명제의 증명은 비교적 자명하다. 일단 기수가 $2^{|X|}$인 집합 $\{0,1\}^X$를 생각하고 다음과 같이 정의되는 함수 $f:\mathcal{P}(X)\to \{0,1\}^X$와 함수 $g:\{0,1\}^X\to\mathcal{P}(X)$를 생각하자.

$$f:A\mapsto \mathbf{1}_A\\g:h\mapsto\{x\in X\;|\;h(x)=1\}$$

그러면 둘의 합성 $f\circ g$와 $g\circ f$가 각각 항등함수 $I_{\{0,1\}^X}:\{0,1\}^X\to\{0,1\}^X$와 $I_{\mathcal{P}(X)}:\mathcal{P}(X)\to\mathcal{P}(X)$가 됨을 쉽게 알 수 있다. 따라서 $f$와 $g$는 전단사함수이며, 그로부터 $|\mathcal{P}(X)|=2^{|X|}$임을 알 수 있다.

$\blacksquare$

 

Lemma 2. $|\mathcal{P}(X)|>|X|$

 

이 명제는 집합론에서 가장 유명한 명제 중 하나라고 해도 과언이 아닐 정도로 유명한 명제이며, 이 명제를 칸토어 정리라고 부르기도 한다. 일단, $X$가 공집합인 경우에는 $|\mathcal{P}(X)|=|\{\emptyset\}|=1>0=|X|$이므로 위 명제가 성립한다. 이제 $X$가 공집합이 아닌 경우에 대해 생각해보자. 일단, 함수 $a:X\to\mathcal{P}(X)$를 $a:x\mapsto\{x\}$로 정의하자. 그러면 함수 $a$가 단사함수임은 매우 자명하다. 따라서 $|X|\leq|\mathcal{P}(X)|$가 성립한다. 이제 $|X|\neq|\mathcal{P}(X)|$임을 보이면 Lemma 2가 증명된다. 이는 귀류법으로 증명할 것이다. 전단사함수 $f:X\to\mathcal{P}(X)$가 존재한다고 가정하고 집합 $S=\{s\in X\;|\;s\in f(s)\}$를 생각하자. 그러면 $S\subseteq X$이므로 $S\in\mathcal{P}(X)$이다. 함수 $f$가 전단사함수이므로 $f(e)=S$를 만족하는 $e\in X$가 존재한다. 이제 이 $e$가 $S$의 원소인지 판단할 것이다. 일단, $e\in S$라고 가정하자. 그러면 $S$의 정의에 의해 $e\notin f(e)=S$가 성립한다. 따라서 $e$는 $S$의 원소이면서 동시에 $S$의 원소가 아니어야 한다. 이는 모순이므로 $e$는 $S$의 원소일 수 없다. 만약 $e$가 $S$의 원소가 아니라면, $S$의 정의에 의해 $e$는 $f(e)$의 원소이다. 그런데, $f(e)=S$이므로 이 경우 역시 $e$가 $S$의 원소이면서 동시에 $S$의 원소가 아니어야 하며 결국 모순이다. 따라서 전단사함수 $f:X\to\mathcal{P}(X)$가 존재한다는 처음의 가정이 모순을 이끌어냈으며, 귀류법에 의해 그러한 전단사함수는 존재할 수 없다. 따라서 $|X|\neq|\mathcal{P}(X)|$이다. 즉, $|\mathcal{P}(X)|>|X|$이다.
$\blacksquare$

 

Theorem 칸토어 정리 ( Cantor's Theorem )

 

임의의 기수 $\kappa$에 대해 $|K|=\kappa$를 만족하는 집합 $K$가 존재한다. 이때, Lemma 1에 의해 $|\mathcal{P}(K)|=2^\kappa$임을 알 수 있으며, Lemma 2에 의해 $|\mathcal{P}(K)|>\kappa$임을 알 수 있다. 따라서 $2^\kappa>\kappa$이다.

$\blacksquare$