집합론, 그 열 번째 이야기 | 칸토어 베른슈타인 정리의 증명 ( The Proof of The Cantor-Bernstein Theorem )

 

앞선 글에서 우리는 $|A|\leq|B|\land|B|\leq|A|\Leftrightarrow|A|=|B|$ 라는 수식을 보았다.

이 글에서는, 위 수식을 증명하려고 한다.

 

두 집합 $A, B$에 대해 $|A| \leq |B| \wedge |A| \geq |B|$ 가 우리의 가정이고, 얻고싶은 결론은 $|A|=|B|$ 이다.

 

즉, 단사함수 $f : A \rightarrow B, g : B \rightarrow A$ 가 존재할 때, 전단사함수 $h : A \rightarrow B$ 가 존재함을 보여야 한다.

 

이 때, 집합 $C_n$ 과 $C$ 를 다음과 같이 정의하자. (단, $n$ 은 임의의 자연수)

$$C_0 = A - g(B)$$ $$C_{n+1} = g(f(C_n))$$ $$C = \displaystyle\bigcup_{n=0}^{\infty}C_n$$

이 때, 우리는 다음과 같은 함수가 $A, B$ 사이의 전단사함수가 됨을 보일 것이다.

$$h(x)=\begin{cases} f(x) & x \in C\\ g^{-1}(x) & x \in A - C \end{cases}$$

 

Part 1. $h : A \rightarrow B$가 단사함수

$a_1, a_2 \in A, a_1 \neq a_2$ 인 $a_1, a_2$를 생각하자.

 

$a_1, a_2 \in C$ 이면 $f(a_1)\neq f(a_2)$ 이므로 $h(a_1)\neq h(a_2)$ 가 되어 단사함수이다.

 

$a_2, a_2 \in A-C$ 이면 $g^{-1}(a_1) \neq g^{-1}(a_2)$ 이므로 이 때도 $h(x)$는 단사함수이다.

 

$a_1 \in C$이고 $a_2 \in A - C$ 이면, $\exists n \in \mathbb{N}\;s.t.\; a_1 \in C_n$ 이고, 이 때

$$h(a_1) \in f(C_n) = g^{-1}(C_{n+1})$$ $$h(a_2) \in g^{-1}(A-C)$$ 이므로, $h(a_1) \neq h(a_2)$ 이다.

 

Part 2. $h : A \rightarrow B$가 전사함수

$b \in B$인 임의의 $b$를 선택하자.

 

$b \in f(C)$ 이면 정의에 의해 $\exists a\;s.t.\;h(a) = b$

$b \notin f(C)$ 인 경우, $a = g(b)$라 할 때 $a \in g(B - f(C)) \Rightarrow a \in A - C$ 이므로 정의에 의해 $h(a) = b$

$$\therefore \forall b \in B, \exists a \in A\;s.t.\;h(a) = b$$

 

따라서 $h : A \rightarrow B$는 전단사함수이고, $|A| = |B|$가 성립한다.