Cantor - Bernstein Theorem (칸토어-베른슈타인 정리)

Lemma.  Let   f: A → B⊂A   be an injection,    then   ∃ a bijection h: A → B.

이 레머(lemma)가 말하는 바는, 자신의 부분집합으로 가는 인젝션이 있다면, 바이젝션도 존재한다는 뜻이다. 엄밀한 증명은 좀 까다로운데, 직관적으로 그럴싸 하므로, 생략한다.

암튼, 위의 레머를 이용해, 다음의 정리를 증명한다.

Cantor-Bernstein Theorem. If A is equipotent to a subset of B, and B is equipotent to a subset of A, then, A and B are equipotent.

여기서 equipotent 는 ∃ a bijection 의 의미이다.

증명.
B와 equipotent 인 A의 서브셋을 C , A와 equipotent 인 B의 서브셋을 D 라고 하자.
그리고 주어진 바이젝션을 다음과 같이 f 와 g 라고 하자.

f:A→D⊂B    ,     g:B→C⊂A

그러면, D가 B의 부분집합 이므로, 컴포지션 (g ο f ) : A → C⊂A 는 잘 정의되며, 인젝션이다.
따라서, 앞의 레머에 의해 A 에서 C 로의 바이젝션 h: A → C⊂A   가 존재한다.

g는 바이젝션이므로, 인버스 g^-1 : C⊂A  → B 도 바이젝션이다.
이제, 두 바이젝션 g^-1 과 h 의 합성 ( g^-1 ο h )  :  A → B  은 바이젝션이므로 증명이 완료된다.


Cantor-Bernstein 정리로 부터 곧바로 다음을 얻는다.
If  |A| ≤ |B|  and  |A| ≥ |B|,  then  |A| = |B|