무한집합을 수로 나타낼 수 있는가
칸토어는 흄의 원리를 이용해서 무한수들을 측정할 수 있다고 합니다.
예전에 포스트했듯이 흄의 원리는 다음과 같습니다.
#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(알레프)라고 읽습니다. 최초의 무한수는 ℵ0로 자연수 집합의 수와 동일합니다.
자연수 집합은 '0과 그 다음수 관계'를 만족하는 대상들의 집합입니다. 1
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 |
… |
이렇게 대응시킨다면, 자연수와 정수는 일대일 대응가능합니다.
모든 자연수를 나열하더라도 반드시 정수 하나가 대응될 수 있고, 모든 정수를 나열하더라도 반드시 자연수 하나와 대응될 수 있습니다. 두 집합은 완벽한 일대일 대응이라는 겁니다.
이런 관계는 양의 정수, 음의 정수에도 똑같이 나타나며, 홀수 짝수도 똑같이 나타납니다.
모두 ℵ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 |
이런 식으로 나열한다면 유리수를 모두 나열할 수 있습니다.
위같은 표를 일정한 규칙으로 순서를 매긴다면, 위같은 표는 모두 자연수와 대응되게 됩니다.
여기서 반복되는 수를 하나만 남겨놓고 모두 제외한다면 유리수 집합 Q가 되겠죠.
저 표에서 반복되는 것들을 지우고, 순서를 매긴다면 자연수 집합과 유리수 집합 또한 일대일 대응하게 됩니다.
흄의 원리에 의해서 역시, 자연수 집합의 수와 유리수 집합의 수도 ℵ0로 같게 됩니다.
결론적으로, 수로 보면 짝수=홀수=자연수=정수=유리수=ℵ0입니다.
(더 나아가 무한집합 중에서 자연수, 정수, 유리수의 부분집합인 것이 있다면, 그 무한집합은 ℵ0값을 가지게 됩니다.)
Uncountable set
위에 나열된 집합들과는 다르게 실수의 집합은 non-denumerable합니다. 자연수와 일대일 대응이 성립하지 않는다는 것이죠.
대표적으로 칸토어의 대각선 논법(Cantor's diagonal argument)으로 이를 증명합니다.
모든 실수를 나열한다고 합시다.
이런 식으로 계속 진행하다보면 모든 실수를 나열할 수 있게 됩니다.
어떤 실수를 제시하더라도 그 실수는 반드시 의 형태를 띄게 됩니다.
라는 수를 정의합시다. 소수점 이하 i+1번째 자리에서 실수ri의 자리수인 dii와 다른 수를 ei로 정의하자는 겁니다.
가령 r0의 첫번째 소수자리수가 1이라면 e0은 1이 아닙니다. r2의 세번째 소수자리수가 3이라면 e2는 3이 아니죠.
이런 식으로 해서0.e0e1e2e3....를 만들 수 있습니다.
e0는 d00이 아니고, e1은 d11이 아니고 en은 dnn이 아니기 때문에 ri의 i+1번째 소수자리수 dii에 대해서 dii≠en입니다.
따라서 임의의 i에 대해서 0.e0e1e2e3....는 실수 ri의 배열에 나타나지 않습니다. 즉, 실수의 나열에 위 수는 들어가 있지 않다는 말이죠.
이는 실수를 나열할 수 있다는 것에 모순이고, '나열'이라는 것에 자연수의 나열과 대응될 수 있다는 의미가 있으므로, 실수와 자연수는 일대일 대응하지 않는다는 결론입니다.
물론 이 자체가 '자연수의 수 < 실수의 수' 라는 건 아닙니다. 여기에 다른 theorem이 필요합니다.
자연수는 실수의 부분집합이고, 실수의 집합과 자연수의 집합은 같지 않습니다.
따라서, 자연수의 수보다 실수의 수가 더 크다고 결론짓는 것이 타당합니다.
그러므로 자연수의 수보다 실수의 기수가 더 크고, 이는 실수집합 R이 uncountable(non-denumerable)하다는 걸 의미합니다.
이 실수의 기수(cardinality of the continuum)를 2ℵ0라고 합니다. 자세한 증명은 칸토어가 제시했습니다.
이와 관련해서 연속체 가설(continuum hypothesis)이란 게 있습니다.
수식으로 ∄A:ℵ0<|A|<2ℵ0 혹은 |R|=ℵ1으로 표기됩니다.
즉, 최초의 무한수인 ℵ0의 다음수 ℵ1가 실수집합의 크기인 2ℵ0라는 가설이죠.
쿠르트 괴델과 폴 코헨이 ZF(C) 공리체계에서 연속체 가설이 결정불가능함을 증명함으로써 연속체 가설은 현재까지는 미지수로 남아있습니다.
- 통상적으로 자연수를 1부터 정의하기도 하지만, 제 모든 포스팅은 자연수를 0부터 시작하는 수학자들의 논리를 따릅니다 [본문으로]
'학문 > 수학' 카테고리의 다른 글
드모르간 법칙 증명(proof of De Morgan law) (0) | 2014.03.09 |
---|---|
ZF집합론에서의 자연수 정의 (0) | 2014.02.23 |
소박한 집합론(naive set theory) (2) | 2014.01.28 |
프레게의 논리주의적 기획(9)ㅡ프레게의 종말과 러셀의 역설 (1) | 2014.01.26 |
프레게의 논리주의적 기획(8)ㅡ자연수 정의 (0) | 2014.01.26 |