📂집합론

칸토어의 정리 증명

정리 ¹

임의의 집합 $X$ 와 그 멱집합 $\mathscr{P} (X)$ 에 대해 $$\operatorname{card}(X)<\operatorname{card}(\mathscr{P} (X))$$

설명

어떤 집합이든 그 기수는 그 멱집합의 기수보다 작다는 말이다. 이미 집합론에서 말하는 무한이라는 개념에 익숙해졌다면 이것은 조금 의외일지도 모르겠다. 자연수의 집합 $\mathbb{N}$ 이 유리수의 집합 $\mathbb{Q}$ 과 일대일 대응이 존재했고, 안타깝게도 $\mathbb{R}$ 과의 일대일 대응은 존재하지 않았다. 이러한 논의들을 생각해볼 때 집합의 포함관계는 직관과 달리 집합의 대등을 말할 때 큰 도움이 되지 않음을 짐작할 수 있었다.

물론 멱집합 $2^{X}$ 는 원래의 집합 $X$ 에 비해 엄청나게 크다. 적어도 모든 $x \in X$ 는 $\left\{ x \right\} \in 2^{X}$ 에 대응된다. 그러나 여기서 생각을 멈추고 $|X| < \left| 2^{X} \right|$ 를 주장한다면 그것은 수학으로 얻은 연역이 아니라 직관에 의존한 추측에 지나지 않는다. 엄밀하게 칸토어의 증명을 따라가보자.

증명

$X=\emptyset$ 이면 $$\operatorname{card}(X)=0 \\ \operatorname{card}(\mathscr{P} (X))=1$$ 이므로 $\operatorname{card}(X)<\operatorname{card}(\mathscr{P} (X))$ 이다. 한편 $X \ne \emptyset$ 이면 $X$ 와 그 멱집합 사이에는 함수가 존재할 것이다. 집합 $X$ 의 원소 $x$ 에 대해 $g(x):={x}$ 와 같이 정의된 $g : X \to \mathscr{P} (X)$ 는 단사다. 그리고 $$X \sim g(X)={{x} ,|, x\in X} \\ {{x} ,|, x\in X}\subset \mathscr{P} (X)$$ 이므로 $\operatorname{card}(X)\le \operatorname{card}(\mathscr{P} (X))$ 이다. 여기서 $\operatorname{card}(X) \ne \operatorname{card}(\mathscr{P} (X))$ 임을 보이면 원하는 결과를 얻는다. 귀류법을 사용하기 위해 일대일 대응 $f : X \sim \mathscr{P} (X)$ 이 존재한다고 가정해보자.

집합 $S={x\in X ,|, x\notin f(x)}$ 에 대해 생각해보면 $S$ 는 $X$ 의 부분집합 $f(x)$ 가 $x$ 를 포함하지 않는 경우의 $x$ 를 모두 모은 집합이다. 확실한 것은 $S\subset X$, 즉 $S\in \mathscr{P} (X)$ 다. $f$ 의 정의에 따라 $f : X \sim \mathscr{P} (X)$ 이고 $S$ 의 정의에 따라 $S\in \mathscr{P} (X)$ 이므로 $f(e)=S$ 를 만족하는 어떤 원소 $e \in X$ 가 존재해야한다. 이 때 $e \in S, e\notin S$ 두 가지 경우를 살펴보자.

• Case 1. $e\in S$
  • 집합 $S$ 의 정의에 따라 $e\notin f(e)$ 인데 $f(e)=S$ 이므로 $e\notin f(e)=S$, 즉 $e\notin S$
• Case 2. $e\notin S$
  • $S=f(e)$ 이므로 $e\notin S=f(e)$, 즉 $e\notin f(e)$ 인데 집합 $S$ 의 정의에 따라 $e\in S$ 이는 모순이므로 일대일 대응 $f$ 는 존재하지 않는다. 따라서 $\operatorname{card}(X) \neq \operatorname{card}(\mathscr{P} (X))$ 이고, 결과적으로 $$\operatorname{card}(X)<\operatorname{card}(\mathscr{P} (X))$$

■