주 메뉴 열기

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

정의편집

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

  • 만약 두 집합    사이에 단사 함수   가 존재하면, 전단사 함수  가 존재한다.
  • 만약 두 집합   기수 이며  라면,  이다.

증명편집

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

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

 
 
 
 

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

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

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

함께보기편집