칸토어(칸토르) 정리

<칸토르 정리>

집합 A의 원소 개수 보다 멱집합 P(A)의 원소 개수가 더 많다

(좀더 유식하게 집합 A의 기수 보다 멱집합P(A)의 기수가 더 크다, 기수=원소의 개수)

이 증명의 배경 지식이나 이야기는 여기를 클릭하시면 이야기를 읽으실 수 있습니다.

증명

a. 공집합인 경우에는 φ의 원소의 개수는 0개이고 P(φ)={φ}이므로 개수가 1이다.

따라서 성립합다.

b. A가 공집합이 아니라고 하자.

당연히 P(A)는 A보다 개수가 많거나 같다(무한일 때를 고려해서)

그럼 여기서 개수가 같지만 않음을 보이면 된다.

만약 둘의 개수가 같다고 가정하자.(나중에 모순을 보일 것임)

그럼

P(A)와 P가 일대일 대응이다.

이 대응을 함수 f라고 하자.

그럼 f(x)는 P(A)의 원소로 A의 부분집합이 된다.(주의 f(x)는 집합이다.)

집합 S={x∈A│x ∉ f(x)}라고 하자.

즉 x의 원소인데 일대일 대응으로 보내면

대응되는 결과(A의 어떤 부분집합)에 x가 들어가지 않는다.

그런데 S도 P(A)의 원소 이므로 어떤 원소 e가 존재해서

f(e)=S이다.

그런데 이 e가 문제이다.

e는 S의 원소이거나 아니거나 둘 중에 하나다

(case 1) e∈S

S의 정의에 따라서 e∉f(e)

한편 f(e)=S이고 e∈S이므로 e∈f(e)이다

이것은 모순이다

(case 2) e∉S

S의 정의에 따라서 e∈f(e)

한편 f(e)=S이므로 e∉f(e)이다.

이것은 모순이다.

case 1,2 모두 모순이므로

처음에 가정한 A와 P(A)의 개수가 같다는 가정은 틀렸다!

따라서 P(A)는 항상 A보다 개수가 많다.