(+)분류 : 가져온 문서/오메가

Cantor's theorem
집합론과 관련된 기초적 정리 중 하나로, 어떤 집합과 그 멱집합은 대등할 수 없다는 내용의 정리이다.
1. 진술 ✎ ⊖
가 집합이고 가 그 멱집합이라 하자. 이 때 전단사 함수 는 존재하지 않는다.
2. 증명 ✎ ⊖
전단사 가 존재한다고 가정하자. 이 때 집합 를
으로 정의하자. 가 전사이므로, 어떤 가 존재해 이여야 한다. 만약 이면 의 정의에 의해 이므로 모순이다. 만약 이면 가 되므로 의 정의에 의해 이다. 따라서 이 경우에도 모순이다. 하지만 혹은 둘 중 하나는 참이여야 한다. 따라서 전사함수 가 존재한다는 전제가 거짓이여야 한다.
으로 정의하자. 가 전사이므로, 어떤 가 존재해 이여야 한다. 만약 이면 의 정의에 의해 이므로 모순이다. 만약 이면 가 되므로 의 정의에 의해 이다. 따라서 이 경우에도 모순이다. 하지만 혹은 둘 중 하나는 참이여야 한다. 따라서 전사함수 가 존재한다는 전제가 거짓이여야 한다.