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

 

 

여태까지 비가산집합의 예시를 몇 개 다루었는데, 실수보다 큰 기수를 갖는 무한집합을 보지는 못했습니다. 기수에 대한 기본적인 개념을 습득하면 이제 칸토어의 정리로 넘어갈 수 있고, 나중에 이를 활용해서 실수보다 더 큰 기수를 가지는 집합이 있는지를 확인해볼 수 있습니다.

---

1.  칸토어의 정리

 

정리($S.T$) 4.18) 칸토어의 정리(Cantor's Theorem)
다음 두 명제를 모두 칸토어의 정리라고 한다. 둘은 동치이다.^[각주:1]
① 임의의 집합 $X$ 에 대해서, $X$ 의 기수는 $X$ 의 멱집합(=$X$ 의 모든 부분집합들을 원소로 같는 집합)의 기수보다 항상 작다. 즉,
$$\left| X \right| < \left| \mathcal{P}(X) \right|=2^{\left| X \right|}$$ ② 임의의 집합 $X$ 에 대하여 전사함수 $f:X\rightarrow \mathcal{P}(X)$ 는 존재하지 않는다. ^[각주:2]

증명) $X=\phi$ 이면 $\left| X \right|=0 < 1 = \left| \mathcal{P}(X) \right|$ 이므로 주어진 명제가 성립한다. 그러니 $X\neq \phi$ 라 하자.

$\left| X \right| \leq \left| \mathcal{P}(X) \right|$ 인 경우를 생각해보자. 추후 여기서 등호가 절대 성립하지 않음을 보여서, 부등호를 증명할 것이다. 우선 $\leq$ 가 성립함을 보이려면 $X$ 가 $\mathcal{P}(X)$ 의 부분집합과 대등하다는 것을 보이면 된다.

함수 $g:X\rightarrow \mathcal{P}(X)$ 를 모든 $x\in\mathbb{R}$ 에 대해 $x\mapsto \left\{ x \right\}$ 와 같이 정의하면, 이는 단사함수가 되고,^[각주:3] 따라서 $X\sim g(X)\subseteq \mathcal{P}(X)$ 가 성립하여 $\left| X \right| \leq \left| \mathcal{P}(X) \right|$ 임은 분명하다.

이제 $\left| X \right| \neq \left| \mathcal{P}(X) \right|$ 임을 보이면 된다. 귀류법을 사용하기 위해 $\left| X \right| = \left| \mathcal{P}(X) \right|$ 인 상황, 즉 전단사함수 $f:X\sim \mathcal{P}(X)$ 가 존재한다고 가정하자. 그리고 $f:X\sim \mathcal{P}(X)$ 가 $x\mapsto f(x)$ 로 정의되는 전단사함수라 생각하자. 이때

$$S=\left\{ x\in X \mid x\notin f(x) \right\}$$
라는 집합을 생각해보자.^[각주:4]
(예를 들어 $X=\left\{ a,b,c \right\}$ 인 경우에 $\mathcal{P}(X)=\left\{ \phi,\left\{ a \right\},\left\{ b \right\},\left\{ c \right\},\left\{ a,b \right\},\left\{ b,c \right\},\left\{ c,a \right\},\left\{ a,b,c \right\} \right\}$ 가 되고, $a\in X$ 는 $\left\{ b,c \right\}$ 로, $b\in X$ 는 $\left\{ c,a \right\}$ 로, $c\in X$ 는 $\left\{ a,b \right\}$ 로 보내 이때는 $S=X$ 가 됩니다. 만일 여기서 $c\in X$ 만 $\left\{ a,b,c \right\}$ 로 보냈다면, $S=\left\{ a,b \right\}\subset X$ 가 되는 것입니다. 물론 이 증명 과정에서 $X$ 는 무한집합입니다.)
어찌되었든 $S$ 는 $X$ 의 부분집합인 셈이므로, $S\in \mathcal{P}(X)$ 이다. 이때 $f$ 는 전단사함수이므로, $f(e)=S$ 를 만족하는 $e\in X$ 가 존재해야 한다.

i) $e\in S$ : $S$ 의 정의에 의하여 $e\notin f(e)$ 가 되어야 한다. 그런데 $f(e)=S$ 이므로 이는 모순이다.
ii) $e\notin S$ : $e\notin S=f(e)$ 가 되는데 다시 $S$ 의 정의에 의하여 $e\in S$ 가 되어야 하므로 이는 모순이다.

따라서 언제나 모순이므로, $\left| X \right| \neq \left| \mathcal{P}(X) \right|\;_\blacksquare$

 

 

 

 

[참고문헌]

You-Feng Lin, Shwu-Yeng T,Lin - Set thoery

 

 

 

 

 

 

 

 

1. 동치인 이유는 대등(equipotent)의 정의를 떠올려 보면 간단하다. [본문으로]
2. 여기서 마지막에 $2^{\left| X \right|}$ 라는 식이 멱집합의 기수와 같다는 것은 뒤쪽의 기수의 거듭제곱을 다룰 때 증명합니다. [본문으로]
3. 언제나 단사임을 보이기 위해서는 정의를 사용하면 된다. [본문으로]
4. 이 집합이 공집합이 아닌 이유를 납득하는 것이 좋습니다. 가볍게 $X$ 의 원소가 2개일 때, 3개일 때로 나누어서 예시를 떠올려 보시기 바랍니다. [본문으로]