Cantor's Theorem (칸토어의 정리 : 멱집합의 카디널리티)
Math2008. 12. 5. 23:03 |어떠한 집합 A 에 대하여, P(A) 를 A 의 멱집합이라고 하자. 이 때 다음의 정리가 성립한다.
즉, 임의의 집합에 대해서 멱집합의 카디널리티는 원래의 집합보다 크다는 것이다. 이것은 유한의 경우에는 당연하다. 따라서 증명은 무한의 경우로 충분하다.
증명.
A의 원소에 대해 그것을 { } 으로 감싸는 함수를 생각하면, 그 함수는 A 에서 P(A) 로의 인젝션이다.
따라서, |A| ≤ |P(A)| 이므로, |A| ≠ |P(A)| 임을 보이면 충분하다. 즉, A 와 P(A) 사이에 바이젝션이 존재할 수 없음을 보인다.
A와 P(A) 사이에 1대1 대응이 존재한다고 가정하자.
그리고 그러한 바이젝션을 f 라고 하자. f : A → P(A) , 그러면 A의 임의의 원소 x 에 대해 f(x) 는 A의 부분집합으로 P(A) 의 원소이다.
가정에 의해, f 는 1대1 대응이므로, 따라서 onto 이다. 즉, f의 치역 f[A] 는 P(A) 와 같다.
이제, 집합 B를 다음과 같이 놓자.
B = { x ∈ A | x !∈ f(x) } ( !∈ 를 "속하지 않는다" 라는 의미로 사용하였다.)
집합 B는, A의 원소 x가 바이젝션 f 에의해 A의 어떤 부분집합 f(x) 로 갈 때, 그 집합 f(x) 가 x를 포함하지 않는 경우의 x들을 모두 모아놓은 집합이다.
그러면, B는 A의 부분집합이므로, B는 P(A)의 원소이다. 즉, B⊂A , B ∈ P(A)
f 는 onto 이고, B가 공역의 원소이므로, f 에 의해 B로 맵핑되는 원소가 A 에 존재해야한다.
그러한 원소를 s 라고 하자. 즉, ∃s ∈A such that f(s) = B ∈ P(A)
또한, B는 A의 부분집합이므로, s ∈A 는 s ∈ B⊂A 이거나 s ! ∈ B⊂A 이다.
만약 s ∈ B⊂A 라고 가정하면, B 의 정의 B = { x ∈ A | x !∈ f(x) } 에 의해서, s !∈ f(s) 가 된다.
그런데, s의 정의에서 f(s) = B 이므로, s !∈ B 라는 말이된다. 그런데 이것은 s ∈ B 라는 가정에 모순이다.
반대로, s !∈ B 라고 가정하면, f(s) 는 B 이므로, s !∈ f(s) 라는 말과 같다. 그런데 이것은 s 가 B에 속해야 함을 의미한다. 따라서 가정에 모순된다.
아무튼, 어떠한 경우에도 모순되므로, 바이젝션 f는 존재하지 않는다. 그러므로, |A| ≠ |P(A)| 이고, |A| < |P(A)| 의 증명을 완료한다.
-----------------------------------------------------------------------------------------------------------------------------
이 정리를 연쇄적으로 적용하면, 즉, 멱집합의 멱집합을 연쇄적으로 고려하면, 항상 이전의 카디널리티보다 큰 카디널리티를 생각할 수 있으므로, 카디널리티의 최대값은 존재하지 않게 된다.
또한, 칸토어의 정리를 자연수집합 N 에 적용하면, |P(N)| 이 알레프 널 보다 크다는 결론을 얻게 되는데, 알레프 널과 |P(N)| 사이에 카디널리티가 존재하는가 하는 문제를 연속체문제(continuum problem) 라고 한다.
| Cantor's Theorem. |A| < |P(A)| |
즉, 임의의 집합에 대해서 멱집합의 카디널리티는 원래의 집합보다 크다는 것이다. 이것은 유한의 경우에는 당연하다. 따라서 증명은 무한의 경우로 충분하다.
증명.
A의 원소에 대해 그것을 { } 으로 감싸는 함수를 생각하면, 그 함수는 A 에서 P(A) 로의 인젝션이다.
따라서, |A| ≤ |P(A)| 이므로, |A| ≠ |P(A)| 임을 보이면 충분하다. 즉, A 와 P(A) 사이에 바이젝션이 존재할 수 없음을 보인다.
A와 P(A) 사이에 1대1 대응이 존재한다고 가정하자.
그리고 그러한 바이젝션을 f 라고 하자. f : A → P(A) , 그러면 A의 임의의 원소 x 에 대해 f(x) 는 A의 부분집합으로 P(A) 의 원소이다.
가정에 의해, f 는 1대1 대응이므로, 따라서 onto 이다. 즉, f의 치역 f[A] 는 P(A) 와 같다.
이제, 집합 B를 다음과 같이 놓자.
B = { x ∈ A | x !∈ f(x) } ( !∈ 를 "속하지 않는다" 라는 의미로 사용하였다.)
집합 B는, A의 원소 x가 바이젝션 f 에의해 A의 어떤 부분집합 f(x) 로 갈 때, 그 집합 f(x) 가 x를 포함하지 않는 경우의 x들을 모두 모아놓은 집합이다.
그러면, B는 A의 부분집합이므로, B는 P(A)의 원소이다. 즉, B⊂A , B ∈ P(A)
f 는 onto 이고, B가 공역의 원소이므로, f 에 의해 B로 맵핑되는 원소가 A 에 존재해야한다.
그러한 원소를 s 라고 하자. 즉, ∃s ∈A such that f(s) = B ∈ P(A)
또한, B는 A의 부분집합이므로, s ∈A 는 s ∈ B⊂A 이거나 s ! ∈ B⊂A 이다.
만약 s ∈ B⊂A 라고 가정하면, B 의 정의 B = { x ∈ A | x !∈ f(x) } 에 의해서, s !∈ f(s) 가 된다.
그런데, s의 정의에서 f(s) = B 이므로, s !∈ B 라는 말이된다. 그런데 이것은 s ∈ B 라는 가정에 모순이다.
반대로, s !∈ B 라고 가정하면, f(s) 는 B 이므로, s !∈ f(s) 라는 말과 같다. 그런데 이것은 s 가 B에 속해야 함을 의미한다. 따라서 가정에 모순된다.
아무튼, 어떠한 경우에도 모순되므로, 바이젝션 f는 존재하지 않는다. 그러므로, |A| ≠ |P(A)| 이고, |A| < |P(A)| 의 증명을 완료한다.
-----------------------------------------------------------------------------------------------------------------------------
이 정리를 연쇄적으로 적용하면, 즉, 멱집합의 멱집합을 연쇄적으로 고려하면, 항상 이전의 카디널리티보다 큰 카디널리티를 생각할 수 있으므로, 카디널리티의 최대값은 존재하지 않게 된다.
또한, 칸토어의 정리를 자연수집합 N 에 적용하면, |P(N)| 이 알레프 널 보다 크다는 결론을 얻게 되는데, 알레프 널과 |P(N)| 사이에 카디널리티가 존재하는가 하는 문제를 연속체문제(continuum problem) 라고 한다.