Cantor's theorem
집합론과 관련된 기초적 정리 중 하나로, 어떤 집합과 그
멱집합은 대등할 수 없다는 내용의 정리이다.
A가 집합이고 \\mathcal{P}(A)가 그 멱집합이라 하자. 이 때 전단사 함수 f:A\\to \\mathcal{P}(A)는 존재하지 않는다.
전단사
f:A\\to \\mathcal{P}(A)가 존재한다고 가정하자. 이 때 집합
R\\in\\mathcal{P}(A)를
R=\\{x\\in X \\mid x\\notin f(x)\\}
으로 정의하자.
f가 전사이므로, 어떤
y\\in X가 존재해
f(y)=R이여야 한다. 만약
y\\in R이면
R의 정의에 의해
y\\notin f(y)=R이므로 모순이다. 만약
y\\notin R이면
y\\notin f(y)가 되므로
R의 정의에 의해
y\\in R이다. 따라서 이 경우에도 모순이다. 하지만
y\\in R 혹은
y\\notin R 둘 중 하나는 참이여야 한다. 따라서 전사함수
f가 존재한다는 전제가 거짓이여야 한다.
