칸토어-슈뢰더-베른슈타인 정리

정리. 두 집합 $A, B$에 대해 $|A| \leq |B|$, $|A| \geq |B|$라면 $|A| = |B|$이다.

매우 당연해 보이지만 $\leq$가 단사함수의 존재성으로, $=$가 전단사함수의 존재성으로 정의된다는 점에서 트리키한 함수 핸들링을 요구한다.

여담으로 “칸토어-베른슈타인 정리(위키피디아)” 또는 “슈뢰더-베른슈타인 정리(나무위키)”라고도 부르는데 “칸토어-슈뢰더 정리”라고 부르는 경우는 못 봤다. 홍대병에 취해 있다면 “칸토어-슈뢰더 정리”라고 불러보자.

첫 번째 증명

실선이 $f: A → B$, 점선이 $g: B → A$이다. 조건에 의해 $f, g$는 단사이다. $C := \mathrm{Im} f$가 $B$와 같다면 증명이 끝나므로, $C \subsetneq B$라고 하자.

임의의 $y \in B \setminus C$에 대해,

• $x_1^y = g(y)$
• $x_{n+1}^y = g(f(x_n))$

• $h_y(x_1^y) = y$
• $h_y(x_{n+1}^y) = f(x_n)$

로 정의한다(보라색). 다음이 성립함을 확인하라.

따라서 다음의 함수 $h: X → Y$는 well-defined이다.

$h$가 전단사임을 확인하라. ◾

두 번째 증명

보조정리. $A_1 \subset B \subset A$에 대해 $|A_1| \leq |B| \leq |A|$이고 $|A_1| = |A|$라면 $|A_1| = |B| = |A|$이다.

증명. $f: A → A_1$가 전사라고 하자. 다음과 같이 $\{A_n\}, \{B_n\}, \{C_n\}$을 정의한다.

$C = \bigcup C_n, D = A \setminus C$라고 하자. $f[C] \subset C, f[D] \subset D$임을 확인하라. 따라서 다음의 $g: A → B$는 전사이다.

본 정리의 증명. $f: A → B, g: B → A$가 전사일 때 $|gf[A]| \leq |g[B]| \leq |A|$이므로 보조정리에 의해 $|g[B]| = |B| = |A|$이다. ◾

잘 생각해 보면 두 증명은 사실 같다.