칸토어의 정리

칸토어의 정리(Cantor's theorem)는 게오르크 칸토어가 증명한 집합론의 정리로, 임의의 집합 $X$과 그 멱집합 $2^X$ 사이에 전단사가 존재할 수 없다는 정리이다. 이 정리로부터 집합 $X$의 기수는 그 멱집합 $2^X$의 기수보다 클 수 없다는 사실을 알 수 있다. 이 정리로부터 제기된 의문은 연속체 가설의 토대를 제공하였다.

증명

임의의 집합 $X$에 대하여

$X=\varnothing$이면 $|X|=0$이고 $|2^X| = 1$이므로 성립한다.

$X \neq \varnothing$일 때, 집합 $X$과 그 멱집합 $2^X$ 사이에 전단사 $f$가 존재한다고 가정하고, $A=\left\{x \in X | x \not\in f(x)\right\}$로 정의하자. 이 때, $f$는 전단사이므로, 적당한 $a \in X$가 존재하여 $f(a)=A$라 하였을 때, 다음과 같은 모순이 발생한다.

1. $a \in A$인 경우, 집합 $A$의 정의에 의해 $a \not\in f(a) = A$
2. $a \not\in A$인 경우, $a \not\in f(a)$이고 집합 $A$의 정의에 의해 $a \in A$

Q.E.D.

같이 보기

• 대각선 논법
• 게오르크 칸토어