칸토어-번슈타인 정리

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

정의 
다음 두 명제가 서로 동치이며, 이를 칸토어-번슈타인 정리라고 한다.
 만약 두 집합 와  사이에 단사 함수 와 가 존재하면, 전단사 함수 가 존재한다.
 만약 두 집합 와 의 기수가 이며 라면, 이다.

증명 
두 단사 함수 와 가 주어졌다고 하자.

집합족  및 집합  및 함수 를 다음과 같이 정의하자.

우선 는 단사 함수이다. 이며 라고 하자. 인 경우, 가 단사 함수이므로 이다. 인 경우, 가 에서 단사 함수이므로 역시 이다. 이며 인 경우, 이며 이므로 이다.

또한 는 전사 함수이다. 라고 하자. 인 경우, 당연히 인 가 존재한다. 인 경우, 로 놓으면,  즉 이므로 이다.

이에 따라 전단사 함수 가 존재한다.

같이 보기 
 알레프수

수학기초론 정리
기수