집합론, 그 스물일곱 번째 이야기 | 칸토어 정리 ( 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{array}{ll}0& \text{if }x\notin A\\ 1& \text{if }x\in A\end{array}$$

 

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

 

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)$를 생각하자.

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

그러면 둘의 합성 $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|}$임을 알 수 있다.

$◼$

 

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

 

이 명제는 집합론에서 가장 유명한 명제 중 하나라고 해도 과언이 아닐 정도로 유명한 명제이며, 이 명제를 칸토어 정리라고 부르기도 한다. 일단, $X$가 공집합인 경우에는 $|\mathcal{P}(X)|=|\{\mathrm{\varnothing }\}|=1>0=|X|$이므로 위 명제가 성립한다. 이제 $X$가 공집합이 아닌 경우에 대해 생각해보자. 일단, 함수 $a:X\to \mathcal{P}(X)$를 $a:x\mapsto \{x\}$로 정의하자. 그러면 함수 $a$가 단사함수임은 매우 자명하다. 따라서 $|X|\le |\mathcal{P}(X)|$가 성립한다. 이제 $|X|\ne |\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|\ne |\mathcal{P}(X)|$이다. 즉, $|\mathcal{P}(X)|>|X|$이다.
$◼$

 

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

 

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

$◼$