칸토어-번슈타인 정리

집합론에서, 칸토어-번슈타인 정리(영어: Cantor-Bernstein theorem)는 두 집합 사이에 두 방향으로 단사 함수가 존재하면 그 사이에 일대일 대응이 존재한다는 정리이다. 이는 선택 공리에 의존하지 않고 증명할 수 있다.

정의

다음 두 명제가 서로 동치이며, 이를 칸토어-번슈타인 정리라고 한다.

• 만약 두 집합 $A$와 $B$ 사이에 단사 함수 $f\colon A\to B$와 $g\colon B\to A$가 존재하면, 전단사 함수 $h\colon A\to B$가 존재한다.
• 만약 두 집합 $A$와 $B$의 기수가 $|A|\leq |B|$이며 $|A|\geq |B|$라면, $|A|=|B|$이다.

증명

두 단사 함수 $f\colon A\to B$와 $g\colon B\to A$가 주어졌다고 하자.

집합족 $\{C_{n}\}_{n=0}^{\infty }$ 및 집합 $C$ 및 함수 $h\colon A\to B$를 다음과 같이 정의하자.

$C_{0}=A\setminus g(B)$

$C_{n+1}=g(f(C_{n}))$

$C=\bigcup _{n=0}^{\infty }C_{n}$

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

우선 $h$는 단사 함수이다. $x,y\in A$이며 $x\neq y$라고 하자. $x,y\in C$인 경우, $f$가 단사 함수이므로 $h(x)\neq h(y)$이다. $x,y\in A\setminus C$인 경우, $g^{-1}$가 $A\setminus C$에서 단사 함수이므로 역시 $h(x)\neq h(y)$이다. $x\in C_{n}\subseteq C$이며 $y\in A\setminus C$인 경우, $h(x)\in f(C_{n})=g^{-1}(C_{n+1})$이며 $h(y)\in g^{-1}(A\setminus C)$이므로 $h(x)\neq h(y)$이다.

또한 $h$는 전사 함수이다. $b\in B$라고 하자. $b\in f(C)$인 경우, 당연히 $b=h(a)$인 $a\in A$가 존재한다. $b\notin f(C)$인 경우, $a=g(b)$로 놓으면, $a\in g(B\setminus f(C))$ 즉 $a\in A\setminus C$이므로 $b=h(a)$이다.

이에 따라 전단사 함수 $h\colon A\to B$가 존재한다.

같이 보기

• 알레프수