칸토어-번슈타인 정리

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

정의[편집]

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

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

증명[편집]

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

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

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

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

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