자연수와 실수

[유토피아]

     1. 두 집합의 원소의 개수(기수)가 같다는 것은 두 집합 사이에 ‘일대일 대응’이 존재할 때를 말한다.
          2. 집합 A가 B에 포함된다고 해서, A의 원소 개수가 B의 원소 개수보다 작다는 결론을 내릴 수 없다.

             무한집합에서는 ‘부분과 전체의 개수가 같을 수 있다’.
          3. 짝수의 집합, 자연수의 집합, 정수의 집합, 유리수의 집합은 갈수록 집합이 커지지만, 모두 기수는 같다.

참고로 개수 혹은 기수로서의 무한은 극한에서 나오는 무한과는 아무 상관이 없는 개념이라는 걸 이 자리에서 밝혀둔다.

기수가 다른 무한집합은 있는가?

지난 글까지 짝수의 집합, 자연수의 집합, 정수의 집합, 유리수의 집합이 모두 기수가 같다는 것을 보였다. 무한은 다 똑같은 무한인 것처럼 보였다. 그러나 모든 무한집합은 결국 일대일 대응 두 집합이 기수가 같다는 것은, 최선을 다해서 일대일 대응을 찾을 수 있을 때를 말한다고 했다. 그러므로 수단 방법 가리지 않고 일대일 대응을 찾아내면 두 집합이 기수가 같다는 것을 보일 수 있다. 모르긴 해도 칸토어 그렇다면 두 집합이 기수가 다르다는 것은 어떻게 보여야 할까? 어떤 수단을 쓰더라도, 결코, 절대, never, 일대일 대응을 만들 수 없다는 걸 보여야 한다. 여러 차례 경험한 바 있지만, 어떤 게 불가능하다는 걸 보이는 건 상당한 통찰력이 필요하다. 칸토어는 자연수의 집합 N과, 실수의 집합 사이에 절대 일대일 대응이 없다는 것을 증명했다. 흔히 ‘칸토어의 대각선 논법

수학자 칸토어(Georg Cantor 1845-1918)대각선 논법으로 실수의 기수가 자연수의 기수보다 크다는 것을 증명하여 무한의 개념에 혁명을 일으켰다.

실수는 자연수보다 많다 : 칸토어의 대각선 논법

어떤 게 불가능하다는 걸 증명하는 대표적 수학 전략은 귀류법

(단, 0.3999999…= 0.400000…이므로 둘 다 쓰면 중복이다. 그러니, 이런 수는 둘 중 하나의 표현만 골라 쓰기로 약속해야 한다.)

이제 왼쪽과 오른쪽이 서로 중복하지도, 남지도 않게 대응할 수는 없음을 보여야 한다. 그런데 눈을 씻고 봐도 왼쪽 자연수 중에서 남는 게 있을 것 같지는 않다. 그렇다면 오른쪽 R의 원소 중에서 남는 것이 있어야 하지 않을까? 즉, 오른쪽에 등장하지 않는 수를 찾아내라는 얘기다. 0.d₁d₂d₃d₄d₅…라는 숫자를 만드는데, d_k는 k에 대응하는 수에서 파란색으로 쓴 자릿수(소수점 이하 k번째 수)가 1일 경우에는 2로, 1이 아닐 때는 1로 정하자.

위에서 파란색으로 쓴 숫자가 대각선을 따라 분포하므로 대각선 논법이라 부르는데, 위의 예에서는 첫 번째 파란 숫자는 1이므로 d₁은 2다. 두 번째 줄의 파란 숫자는 0이므로 d₂는 1이다. 세 번째 파란 숫자 4는 1과 다르므로 d₃은 1이다. 마찬가지로 d₄는 1, d₅는 2, …이다. 이렇게 만든 0.d₁d₂d₃d₄d₅…=0.21112…는 R의 원소임이 분명하면서도 3947.134887…, 0.303066…, -72331.234567…, 3.141592…, -2.111113…, …의 어떤 것과도  같을 수가 없다! 즉, 위의 대응이 결코 일대일 대응일 수 없다. 다른 예를 가져오더라도, 똑같은 방법을 쓰면 오른쪽에 등장하지 않는 수 0.d₁d₂d₃d₄d₅…를 항상 찾아낼 수 있다. 즉, 어떤 대응을 가져오더라도 항상 오른쪽에서 대응하지 않는 원소를 찾을 수 있다는 얘기다. 따라서 실수의 기수는 자연수의 기수보다 크다. 실수는 자연수보다 확실히 많다!

실수보다 기수가 큰 집합도 얼마든지 있다 : 멱집합의 기수

자연수보다 기수가 더 큰 집합으로 실수 집합을 찾아냈다. 그럼 실수보다 기수가 더 큰 집합은 있을까? 무한집합 중에서 가장 기수가 큰 집합은 있을까라는 의문이 자연스럽게 제기된다. 실수보다 기수가 더 큰 집합도 있다! 더구나 어떤 집합을 가져오든 그것보다 더 기수가 큰 집합이 반드시 있다는 사실을 아래에서처럼 보일 수 있으므로, 가장 기수가 큰 집합이란 있을 수 없다.

A에 대해 ‘A의 모든 부분집합’을 원소로 갖는 집합을 ‘A의 멱집합

일반적으로 유한집합 A의 원소 개수가 n개일 때, P(A)의 원소 개수는 2ⁿ이다. A가 무한집합일 때는 어떨까? P(A)가 무한집합임은 당연한데, 칸토어는 이 집합이 항상 A보다 기수가 클 수밖에 없음을 귀류법을 써서 증명했다.

A와 P(A) 사이에 대응이 있다고 하자. A의 원소 a에 대응하는 P(A)의 원소를 X_a라 쓰기로 하자. 이 때, 모든 X_a와 다른 집합 X를 하나 찾아내는 것이 목표다. X를 어떻게 구성하면 좋을까? 어떤 a를 가져와도 X가 X_a와 다르도록 만들려면, 다음과 같이 하면 된다. X_a가 a를 포함하면 X에는 a를 넣지 말고, X_a가 a를 포함하지 않으면 X에는 a를 넣으면 된다! 즉, 다음과 같이 하자는 것이다.

X는 당연히 A의 부분집합인데 (즉, P(A)의 원소인데) 어떤 a에 대해서도 X와 Xa는 같을 수가 없다. a라는 원소는 반드시 둘 중 어느 한 쪽에만 들어가기 때문이다.  따라서 이 대응은 절대 일대일 대응일 수 없다. X라는 집합을 어떻게 생각해낸 건지 신기한 사람도 있을 것 같다. 사실 2진법의 원리를 이용하면 위의 증명은 본질적으로 대각선 논법과 같지만, 더는 설명하지 않기로 한다.

자연수보다 크고 실수보다 기수가 작은 집합은 있을까?

자연수의 집합을 N이라 할 때, 다음을 생각해 보자, 자연수의 집합, 자연수 집합의 멱집합, 그 집합의 멱집합… 등이다.

각 집합은 먼저 나온 집합의 멱집합이므로, 기수가 커진다. 이쯤에서 질문이 생긴다. N의 기수가 P(N)의 기수보다 작은데, N보다 기수가 크고, P(N)보다 기수가 작은 것은 있을까? P(N)보다 기수가 크고 P(P(N))보다 기수가 작은 것은 있을까? 등등은 자연스러운 질문이다. 그 중 첫 번째 질문에만 집중해 보자. 그런데 자연수의 집합 N에 대해, N의 멱집합 P(N)의 기수는 실수 집합의 기수와 같다는 것을 보일 수 있다. (증명은 생략한다.) 따라서 이 질문은 자연수보다 기수가 크고, 실수보다 기수가 작은 집합이 있느냐는 문제로 귀결된다.

즉, 유리수보다 기수가 크고 실수보다 기수가 작은 집합을 찾는 문제가 된다. 유리수를 포함하고, 실수에 포함되는 집합 중에 ‘대수적 수

대수적 수는 유리수는 물론, 거듭제곱근 등을 포함하는 수 체계로, 어지간한 실수는 다 여기 들어 있는 것 같아 보인다. 하지만, 칸토어는 ‘대수적 수’의 개수 역시 자연수와 개수가 같다는 것을 보였다. 따라서 대수적 수가 아닌 수, 즉, 초월수

20세기 수학의 제 1문제 ‘연속체 가설’

이렇게 자연수보다 기수가 크고 실수보다 기수가 작은 집합을 찾으려는 첫 번째 시도는 실패했다. 칸토어는 그런 집합이 없다는 것을 증명해 보려고 노력해 보기도 하고, 혹은 그런 집합을 구성해보려고 애써 보기도 했지만, 결국 모르겠다고 고백하고 만다. 이후 이 질문을 ‘연속체 가설’(continuum hypothesis)이라 부르는데, 힐베르트

1940년 논리학의 황제 쿠르트 괴델폴 코헨

네 줄 요약?

무한집합의 기수에 대해 알게 되면, 어쩐지 자랑하고 싶은 마음이 든다. 상식을 벗어나는 일의 연속이니 말이다.

                        1. 짝수, 자연수, 정수의 개수가 같다
                        2. 자연수와 유리수도 개수가 같다
                        3. 자연수나 유리수보다는 실수가 개수가 더 많다

                        4. 유리수보다 개수가 많고 실수보다 개수가 더 적은 것은 있어도 좋고, 없어도 좋다

등등 어찌 보면 신기한 일이 계속되기 때문이다. (그래도 어지간하면 소개팅 자리에서 파트너에게 신기한 얘기라며 이런 얘기는 하지 않길 바란다. 필자가 몸소 경험한 일인지도 묻지 말아줬으면 좋겠다.)

사실 무한집합 및 수학의 기초에 대해서는 지금까지 한 얘기와는 비교조차 할 수 없는 주제가 산더미처럼 많다. 기수와는 다른 서수의 개념, 러셀의 역설 등을 비롯한 각종 역설, 선택의 공리, 공간 채우기 곡선, 논리 및 수학의 기반에 대한 불완전성 정리 등등이 그런 예다. 언젠가는 이 중에서 몇 가지는 다루고 싶지만, 당분간은 무한 세상을 떠나 다른 수학의 세계도 살펴보기로 하자.