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

 

앞선 글에서 우리는 $|A|\le |B|\wedge |B|\le |A|\iff |A|=|B|$ 라는 수식을 보았다.

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

 

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

 

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

 

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

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

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

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

 

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

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

 

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

 

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

 

$a_1\in C$이고 $a_2\in A-C$ 이면, $\mathrm{\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)\ne h(a_2)$ 이다.

 

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

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

 

$b\in f(C)$ 이면 정의에 의해 $\mathrm{\exists }as.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 \mathrm{\forall }b\in B,\mathrm{\exists }a\in As.t.h(a)=b$$

 

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