칸토어의 무한수
무한집합을 수로 나타낼 수 있는가
칸토어는 흄의 원리를 이용해서 무한수들을 측정할 수 있다고 합니다.
예전에 포스트했듯이 흄의 원리는 다음과 같습니다.
#F=#G ↔ F≈G ↔ ∃R[∀x(Fx→∃1y(Rxy ∧ Gy) ∧∀y(Gy→∃1x(Ryx ∧ Fx))]
수가 같다는 말의 동치는 개념들 사이에 일대일 대응이 성립한다는 것입니다.
유한집합뿐만 아니라 무한집합의 경우에도 이 원리를 적용하여 수를 판단할 수 있습니다.
먼저 여러 무한수들을 언급하기 전에 수학적인 개념 몇개를 언급해야 할 것 같습니다.
denumerable : 자연수 집합과 일대일 대응가능하다
(한글로 가산可算이라고 번역하던데 엄밀한 의미에서 틀린 말입니다. 자연수 집합 자체가 무한집합인데, 무한을 셀 수는 없죠)
countable : finite or denumerable. 유한하거나 denumerable함을 뜻합니다.
uncountable : 무한하면서도 자연수 집합과 일대일 대응할 수 없음을 뜻합니다.
Denumerable set
denumerable set에는 자연수, 정수, 유리수 집합이 있습니다.
즉, '자연수의 수=정수의 수=유리수의 수'입니다.
물론 자연수의 수가 정말로 존재하는가에 대한 논쟁은 있겠지만(더 나아가 무한수가 과연 실재하는가에 대한 논쟁), 여기서는 그런 논쟁들은 나두고 자연수의 수가 있다는 일반적인 견해를 따르기로 합니다.
집합론에서는 무한수를 $\aleph$로 표기합니다. aleph(알레프)라고 읽습니다. 최초의 무한수는 $\aleph_0$로 자연수 집합의 수와 동일합니다.
자연수 집합은 '0과 그 다음수 관계'를 만족하는 대상들의 집합입니다.1
$\mathbb{N}=\{0,1,2,3,4...\}$입니다.
집합들 사이에 수가 같기 위해서는 흄의 원리에 의해서 집합들 사이에 일대일 대응이 성립해야 합니다.
먼저 정수와 자연수의 수를 비교해봅시다.
모든 자연수는 0 1 2 3 4 등으로 이어지는 모든 수이고, 모든 정수는 … -3 -2 -1 0 1 2 3 … 등으로 이어지는 수입니다.
이 수들을 이렇게 대응시킬 수 있겠습니다.
|
자연수 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
… |
|
정수 |
0 |
-1 |
1 |
-2 |
2 |
-3 |
3 |
-4 |
… |
이렇게 대응시킨다면, 자연수와 정수는 일대일 대응가능합니다.
모든 자연수를 나열하더라도 반드시 정수 하나가 대응될 수 있고, 모든 정수를 나열하더라도 반드시 자연수 하나와 대응될 수 있습니다. 두 집합은 완벽한 일대일 대응이라는 겁니다.
이런 관계는 양의 정수, 음의 정수에도 똑같이 나타나며, 홀수 짝수도 똑같이 나타납니다.
모두 $\aleph_0$로 같은 수입니다.
유리수는 어떨까요?
|
분모/분자 |
0 |
1 |
-1 |
2 |
-2 |
|
1 |
0 |
1 |
-1 |
2 |
-2 |
|
2 |
0 |
1/2 |
-1/2 |
1 |
-1 |
|
3 |
0 |
1/3 |
-1/3 |
2/3 |
-2/3 |
|
4 |
0 |
1/4 |
-1/4 |
1/2 |
-1/2 |
|
5 |
0 |
1/5 |
-1/5 |
2/5 |
-2/5 |
이런 식으로 나열한다면 유리수를 모두 나열할 수 있습니다.
위같은 표를 일정한 규칙으로 순서를 매긴다면, 위같은 표는 모두 자연수와 대응되게 됩니다.
여기서 반복되는 수를 하나만 남겨놓고 모두 제외한다면 유리수 집합 $\mathbb{Q}$가 되겠죠.
저 표에서 반복되는 것들을 지우고, 순서를 매긴다면 자연수 집합과 유리수 집합 또한 일대일 대응하게 됩니다.
흄의 원리에 의해서 역시, 자연수 집합의 수와 유리수 집합의 수도 $\aleph_0$로 같게 됩니다.
결론적으로, 수로 보면 짝수=홀수=자연수=정수=유리수=$\aleph_0$입니다.
(더 나아가 무한집합 중에서 자연수, 정수, 유리수의 부분집합인 것이 있다면, 그 무한집합은 $\aleph_0$값을 가지게 됩니다.)
Uncountable set
위에 나열된 집합들과는 다르게 실수의 집합은 non-denumerable합니다. 자연수와 일대일 대응이 성립하지 않는다는 것이죠.
대표적으로 칸토어의 대각선 논법(Cantor's diagonal argument)으로 이를 증명합니다.
모든 실수를 나열한다고 합시다.
이런 식으로 계속 진행하다보면 모든 실수를 나열할 수 있게 됩니다.
어떤 실수를 제시하더라도 그 실수는 반드시 
라는 수를 정의합시다. 소수점 이하 $i+1$번째 자리에서 실수$\Large r_i$의 자리수인 $\Large d_i^i$와 다른 수를 $\Large e_i$로 정의하자는 겁니다.
가령 $r_0$의 첫번째 소수자리수가 $1$이라면 $e_0$은 $1$이 아닙니다. $r_2$의 세번째 소수자리수가 $3$이라면 $e_2$는 $3$이 아니죠.
이런 식으로 해서$0.e_0 e_1 e_2 e_3 ....$를 만들 수 있습니다.
$e_0$는 $d_0^0$이 아니고, $e_1$은 $d_1^1$이 아니고 $e_n$은 $d_n^n$이 아니기 때문에 $r_i$의 $i+1$번째 소수자리수 $d_i^i$에 대해서 $d_i^i \ne e_n$입니다.
따라서 임의의 $i$에 대해서 $0.e_0 e_1 e_2 e_3 ....$는 실수 $r_i$의 배열에 나타나지 않습니다. 즉, 실수의 나열에 위 수는 들어가 있지 않다는 말이죠.
이는 실수를 나열할 수 있다는 것에 모순이고, '나열'이라는 것에 자연수의 나열과 대응될 수 있다는 의미가 있으므로, 실수와 자연수는 일대일 대응하지 않는다는 결론입니다.
물론 이 자체가 '자연수의 수 < 실수의 수' 라는 건 아닙니다. 여기에 다른 theorem이 필요합니다.
자연수는 실수의 부분집합이고, 실수의 집합과 자연수의 집합은 같지 않습니다.
따라서, 자연수의 수보다 실수의 수가 더 크다고 결론짓는 것이 타당합니다.
그러므로 자연수의 수보다 실수의 기수가 더 크고, 이는 실수집합 $\mathbb{R}$이 uncountable(non-denumerable)하다는 걸 의미합니다.
이 실수의 기수(cardinality of the continuum)를 $2^{\aleph_0}$라고 합니다. 자세한 증명은 칸토어가 제시했습니다.
이와 관련해서 연속체 가설(continuum hypothesis)이란 게 있습니다.
수식으로 $\not\exists{\mathbb{A}}:\aleph_{0}<|\mathbb{A}|<2^{\aleph_0}$ 혹은 $|\mathbb{R}|=\aleph_1$으로 표기됩니다.
즉, 최초의 무한수인 $\aleph_0$의 다음수 $\aleph_1$가 실수집합의 크기인 $2^{\aleph_0}$라는 가설이죠.
쿠르트 괴델과 폴 코헨이 ZF(C) 공리체계에서 연속체 가설이 결정불가능함을 증명함으로써 연속체 가설은 현재까지는 미지수로 남아있습니다.
- 통상적으로 자연수를 1부터 정의하기도 하지만, 제 모든 포스팅은 자연수를 0부터 시작하는 수학자들의 논리를 따릅니다 [본문으로]