칸토어의 정리

틀:위키데이터 속성 추적 집합론에서 칸토어의 정리(틀:Llang)는 멱집합의 크기가 항상 원래의 집합의 크기보다 크다는 정리이다. 즉, 집합과 멱집합의 원소는 일대일 대응할 수 없다.

정의

집합 $X$의 멱집합 $2^X$는 $X$의 모든 부분 집합의 집합이다.

칸토어의 정리에 따르면, 멱집합 $2^X$의 크기는 항상 원래의 집합 $X$의 크기보다 크다. 즉, 다음이 성립한다.

$|2^X|>|X|$

즉, 임의의 기수 $\kappa \in \mathrm{Card}$에 대하여, 다음이 성립한다.

$2^{\kappa }>\kappa$

증명

만약 $X=\varnothing$이라면,

$|\varnothing |=0<1=|\{\varnothing \}|=|2^{\varnothing }|$

이므로 성립한다.

만약 $X\ne \varnothing$이라면, 우선 단사 함수

$X\to 2^X$

$x\mapsto \{x\}$

가 존재하므로,

$|X|\le |2^X|$

이다. 또한, 만약

$|X|=|2^X|$

라고 가정하면, 전단사 함수

$f:X\to 2^X$

가 존재한다. 이 경우, 부분 집합

$f(a)=\{x\in X:x\in ̸f(x)\}\in 2^X(a\in X)$

를 구성할 수 있는데, $f(a)$의 정의에 따라

$a\in f(a)⟺a\in ̸f(a)$

이며, 이는 모순이다. 즉,

$|X|\ne |2^X|$

이며, 따라서

$|X|<|2^X|$

이다.

역사

게오르크 칸토어가 증명하였다. 이 정리로부터 제기된 의문은 연속체 가설의 토대를 제공하였다.

같이 보기

• 대각선 논법
• 칸토어 역설