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

19 Nov 2024

정리. 두 집합 $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^{-1}(y)$

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

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

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

\[x^y_n = x^z_m \iff y = z, n = m\]

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

\[h(x) = \begin{cases} h_y(x) &x = x^y_n \text{ for some } y, n \\\\ f(x) &\text{otherwise} \end{cases}\]

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

두 번째 증명

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

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

\[\begin{gather} A_0 = A, \; A_{n+1} = f[A_n] \\ B_0 = B, \; B_{n+1} = f[B_n] \\ C_n = A_n \setminus B_n \end{gather}\]

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

\[g(x) = \begin{cases} f(x) & x \in C\\ x & x \in D \end{cases}\]

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

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