어서오세요! 힐베르트 호텔에! ~무한의 세계로 떠나는 여행~

어서오세요! 힐베르트 호텔에! ~무한의 세계로 떠나는 여행~

자연수가 클까? 유리수가 클까?

 

 

0. 무한 호텔에 오신 것을 환영합니다!

안녕하세요! 어서오세요! 여기는 힐베르트 그랜드 호텔(Hilbert Grand Hotel)입니다!

이 호텔은 정말 말그대로 '그랜드(Grand)'해서 방이 정말 많아요!
진짜 말그대로 방이 무한히 많답니다.

게다가 엄청난 성업중!
오늘도 평화로운 힐베르트 호텔호텔호텔. 모든 방에 손님이 꽉 차 있습니다. 빈방이 하나도 없죠. 🏨

그런데 새로운 손님 한 명이 찾아옵니다.
"형님들 안녕하십니까?"
어라? 방이 꽉차있는데 어쩌죠? 입장 거절 확정인가요?

그런데 말입니다. 지배인 형님 등장하셨죠. 끝났습니다.
당황하지 않고 입을 여시죠.
"1번 방 손님은 2번 방으로, 2번 방 손님은 3번 방으로..."
마법처럼 모든 손님에게 자신의 방 번호에 +1을 더한 방으로 강제 이주 들어갑니다.
이제 1번방 비었죠? 새 손님 입장 확정입니다.
끝났습니다. 입장하시죠.

이처럼 '꽉 찼지만' 항상 공간을 더 만들 수 있는 것이 바로 무한의 신비입니다. 여기서 한 가지 궁금증이 생깁니다.

"아니, 한 명이 더 와도, 심지어 무한 명이 더 와도 수용이 가능한 이 무한에도 '크기'라는 게 있을까? 무한끼리 크기를 비교할 수 있다는 게 말이 될까?"

놀랍게도, 대답은 "네, 가능합니다." 입니다.

모든 무한이 다 같은 레벨의 무한은 아니라는 사실. 믿겨지시나요?

"무한대는 다 똑같은 거 아니야?" 라고 생각했다면 큰 오산! 오늘은 무한의 세계로 떠나 어떤 무한이 더 '큰지' 비교해보는 신기한 여행을 시작하겠습니다. 

미리 힌트를 좀 드리자면, 수학자 게오르그 칸토어가 발견한 '일대일 대응'이라는 마법 같은 방법만 알면 누구나 이 무한의 크기를 이해할 수 있답니다.

 

1. 자연수가 더 클까요, 짝수가 더 클까요?

자, 일단 자연수가 더 큰지, 짝수가 더 큰지 생각해 볼까요?

자연수는 짝수와 홀수로 이루어져 있고, 따라서 일견 짝수가 자연수보다 크기가 더 작을 것 같습니다.

"당연히 자연수가 더 많지! 짝수는 자연수에 포함되잖아?" 라고 자연스럽게 말하게 될 것입니다.

직관적으로는 그렇게 생각하기 쉽습니다.

하지만 무한의 세계에서는 우리의 직관이 항상 통하지는 않습니다.

두 집합의 크기를 비교하는 방법은 바로 일대일로 짝을 지어보는 것입니다.

하나도 남거나 모자라지 않게 짝을 지을 수 있다면 두 집합의 크기는 같다고 봅니다.

즉, 일대일대응을 시켜서 대응이 된다면 두 집합의 크기가 같은것이죠!


자, 자연수와 짝수를 한번 짝지어 볼까요?

자연수 1 에는 짝수 2를

자연수 2 에는 짝수 4를

자연수 3 에는 짝수 6을

...

자연수 n 에는 짝수 2n을

어떤가요? 모든 자연수는 자신만의 짝꿍 짝수를 가질 수 있고, 어떤 짝수도 짝꿍이 없는 경우가 없습니다.

이렇게 빈틈없이 일대일로 대응시킬 수 있으므로, 놀랍게도 자연수의 개수와 짝수의 개수는 같습니다.

결론: 자연수와 짝수의 '무한'은 같은 크기다!

 

 

2. 정수가 더 클까요, 자연수가 더 클까요?

이번엔 0과 음수까지 포함하는 정수와 자연수를 비교해 봅시다.

정수는 자연수(양의 정수)와 0, 그리고 음의 정수까지 있으니 당연히 더 많아 보이죠?

하지만 이번에도 일대일 대응의 마법을 사용해 보겠습니다.


이렇게 짝을 지어보면 어떨까요?

자연수 1 에는 정수 0을

자연수 2 에는 정수 -1을

자연수 3 에는 정수 1을

자연수 4 에는 정수 -2를

자연수 5 에는 정수 2를

...

즉, 홀수 자연수 n에 대해서는 (n-1)/2를 대응하고, 짝수 자연수 n에 대해서는 -n/2를 대응하면 나오는 규칙이죠!

이런 규칙으로 자연수를 양의 정수와 음의 정수에 번갈아 가며 대응시키면, 모든 정수는 자신만의 자연수 짝을 찾을 수 있습니다.(1:1 대응 성립) 따라서 정수와 자연수도 같은 크기의 무한입니다.

결론: 정수와 자연수의 '무한'도 같은 크기다!

 

 

3. 유리수가 더 클까요, 자연수가 더 클까요?

그럼 이제 집합의 크기를 좀 더 키워봅시다.
수의 체계에서 정수보다 큰 집합은? 네 유리수죠!
그럼 유리수는 자연수보다 커질까요? 아니면 지금처럼 같은 크기일까요?

유리수는 이제 분수가 들어가기 시작하면서 간단한 수식계산 같은 조작으로는 이제 조금 버겁기 시작합니다.

그러나 세상에는 똑똑한 사람이 참 많은 것 같습니다.

이 분수를 전부 기약분수(p/q)로 만든 뒤, 분자(p)의 값을 x값에, 분모(q)의 값을 y값에 대응시킵니다.

기약분수의 꼴이므로 본모도 정수(0이 아닌), 분자도 정수임을 이용한 것이죠.

이렇게 좌표위에 하나씩 찍어주면... 정수 격자점 위에 점이 하나씩 찍힐 것입니다.

다음 그림처럼 말이죠.

기약분수니까, 점 (p, q)에서 p, q가 공약수를 가지는 격자점은 공백이 됩니다.

또한, (0, q)는 q가 1일 때만 기약분수로 간주하기 때문에, q가 다른 값은 모두 공백이 됩니다.


자, 이렇게 그리고보니까 이 파란색으로 x표 쳐진 격자점 하나하나를 '셀 수 있게' 되었네요?

일단 0을 첫번째로 세고, (1,1)을 두번째로 세고, (-1,1)을 세번째로 세고, (2, 1)을 네번째로 세고.....

결국 자연수와 1:1 대응을 시킬 수 있습니다.

결론: 유리수와 자연수의 '무한'도 같은 크기다!


여기서 중간 정리 하자면, 무한의 크기는 자연수=정수=유리수 입니다.

 

 

4. 실수가 더 클까요, 자연수가 더 클까요?

이제 정말 흥미로운 질문입니다. 유리수와 무리수를 모두 포함하는 '빽빽한' 수의 집합인 실수와 자연수를 비교해 보겠습니다. 지금까지의 결과처럼 이번에도 두 집합의 크기가 같을까요?

결론부터 말하자면, 실수가 자연수보다 훨씬 더 큰 무한입니다.

어떻게 이럴수가 있죠!?

수학자 칸토어는 '대각선 논법'이라는 기발한 방법으로 이를 증명했습니다.

간단히 설명하자면, 모든 실수를 목록으로 만들어 자연수와 일대일로 짝을 지었다고 '가정'해 봅시다.

그리고 그 목록에 존재하지 않는 새로운 실수를 하나 만들어내는 것입니다.(그러면 가정이 무너지겠죠!?)


자세히 살펴볼까요?

1. 일단, 지금까지 모든 집합은 자연수와 크기가 같았으니 일단 실수도 자연수와 크기가 같다고 가정합니다.
2. 그렇다면 모든 실수는 자연수와 1:1 대응일 것입니다.(크기가 같다 = 1:1 대응이다)
3. 이는 (0, 1)사이에서도 무조건 성립해야겠죠?(모든 수를 셀 수 있으니까 0에서 1사이에 모든 수도 셀 수 있어야 할 것입니다)
   그렇다면 그 리스트는 다음과 같겠죠?
   $ \begin{vmatrix}
   1: && 0.\textcolor{blue}{a_{11}}a_{12}a_{13} \dots \\
   2: && 0.a_{21}\textcolor{blue}{a_{22}}a_{23} \dots \\
   3: && 0.a_{31}a_{32}\textcolor{blue}{a_{33}} \dots \\
   \vdots && \vdots
   \end{vmatrix} $
4. 이제 우리는 여기서 '네가 세지 못한 수가 존재한다!'는 것을 보여줄 것입니다. 그리고 이걸 보여주는 순간 원래 가정이 무너지면서 '셀 수 없음'이 반대로 증명되는거죠.(이걸 귀류법이라고 한답니다)
5. 일단 '이 안에 있는 수와 다르다(=리스트에 없는 수다)'는 것을 보여주기위해 각 순서의 소수점 이하 자리를 취하겠습니다.
   뭔 말인고 하니, 이제 우리는 새로운 수를 이렇게 만들 겁니다(이렇게 대각선으로 수를 모아서 만든다고 '대각선 논증'입니다.)
   $ 0.\textcolor{blue}{a_{11}a_{22}a_{33}} \dots $
   그리고 이 수를 변형하겠습니다.
   
   10진수체계로 보면, $ a $가 1이면 2로 바꾸고, 1이 아니면 1로 바꿉니다.
   2진수체계라면, $ a $를 그냥 바로 보수취해줍니다. 1은 0으로, 0은 1로.
   요지는 원래숫자를 다른 숫자로 바꿔주는 겁니다.

자, 이제 모든게 다 끝났습니다.

만약 이 수($0.a_1a_2a_3\dots$)들의 집합이 셀 수 있다면, 변형한 이 수도 그동안 셌던 수 안에 있어야 합니다.
그러나 이 변형한 수가 그동안 셌던 수 안에 없다면..? 이 수는 셀 수 있다는 가정이 무너져 버리면서 '셀 수 없다'가 되어버립니다.

결과를 까 볼까요?

결과적으로 만들어진 이 수는 지금까지 셌던 모든 수와 n번째 자리가 달라서 그 어느 수와도 같아질 수가 없습니다. 즉, 목록에 존재하지 않는 새로운 실수가 하나 만들어 진거죠!

이 방법으로 목록에 있는 어떤 실수와도 다른 새로운 실수를 끝없이 만들어 낼 수 있음을 보였습니다. 이는 애초에 실수 전체를 자연수와 일대일로 짝짓는 것이 불가능하다는 것을 의미합니다.

결론: 모든 실수를 셀 수 있다고 가정하여 하나의 수 목록을 만들었다고 가정하면, 대각선 논법을 통해 만들어진 새로운 수는 우리가 가정한 목록에 존재하지 않는 수 이므로, 가정이 거짓으로 증명된다.(귀류법) 따라서 실수는 셀 수 없으며, 자연수보다 '한 단계 더 높은' 크기의 무한이다!

 

 

5. 가산무한, 알레프 제로($ \aleph_0 $)

수학자들은 자연수처럼 하나하나 셀 수 있는 무한을 '가산무한(countable infinity)'이라고 부릅니다. 그리고 이 가산무한의 크기를 나타내는 기호로 히브리 문자 첫 글자인 '알레프(ℵ)'에 0을 붙여 알레프 제로($ \aleph_0 $)라고 이름 붙였습니다.

지금까지 살펴본 것처럼, 자연수, 짝수, 정수, 그리고 심지어 분수로 표현 가능한 유리수까지 모두 알레프 제로($ \aleph_0 $)라는 같은 크기의 무한에 속합니다.

 

 

6. 그렇다면 실수는?

자연수와 짝을 지을 수 없었던 실수의 무한은 알레프 제로($ \aleph_0 $)보다 더 큰 무한입니다.
이를 '비가산무한(uncountable infinity)'이라고 부르며, 그 크기는 $ 2^{\aleph_0} $입니다.

더 자세히 알고 싶으시다면... 아래 더 보기를 눌러주세요. 그러나 그냥 '실수는 자연수보다 큰 무한집한이네~'하고 넘어가셔도 무방합니다.

더 보기를 클릭하신 용자분. 환영합니다.

 

이제 좀 더 자세히 알아보도록 하죠.

 

일단, 아까 위에서 대각선 논법에서 살펴봤듯이 이미 0에서 1사이의 수 만으로도 가산무한이 깨지는 것을 보셨을 겁니다.

즉, 이말은 0과 1사이에서 모든 논지를 전개시켜도 무방하다는 의미가 됩니다.

 

그렇다면 [0, 1]구간에서 모든 실수를 2진수로 변환시켜봅시다.

소수점이하가 전부 이진수로 변하면서, 무한이진소수로 표현이 되겠죠?

그리고 이 변한 이진소수는 각자 유일할 것입니다.(물론 0.1 = 0.011111... 같은 '한가지 수를 나타내는 두가지 표현'이 나올 수 있습니다. 그러나 이런 '주소가 두 개인' 숫자들은 전체 실수의 개수에 비하면 무시할 수 있을 만큼 적어서 괜찮습니다.)

 

자, 이제 두가지 방법으로 실수의 크기를 찾아 볼 건데요, 첫번째는 아주 쉽게 직관적으로 이해해보기, 두번째는 집합론적으로 따라가며 이해해보기 입니다.

 

 

1. 매우 쉽게 생각하기(중복순열)

네, 여기서 수학적 엄밀함을 일단 약간은 내려놓고, 쉽게 생각해봅시다.(엄밀함을 내려놓는다고, 틀린말을 하는 건 아닙니다. 개념적 지름길? 같은 느낌이죠)

일단 소수점 이하 자릿수에 들어갈 수 있는 수는 무조건 0 아니면 1입니다.

그리고 소수점 이하 N자리까지 나열한다고 생각하면,

중복순열로 $ _{2} \Pi _{N} $이겠죠?

그리고 이거는 수식으로 $ 2^{N} $입니다. 그리고 N은 무조건 자연수일 수 밖에 업죠. '소수점이하 몇 번째 자리'를 나타내기 때문에요.

 

그렇다면, 아까 자연수 N은 크기가 뭐라고 했죠? $ \aleph_0 $였죠?

그렇다면 실수의 크기는?

네, 자연스럽게 $ 2^{\aleph_0} $라고 유도됩니다.

 

집합론적으로 유도한 것이 아니고, 사실 중복순열은 '유한'에서 정의되는 개념이라 약간의 cheating이긴 합니다만, 수학에서는 오히려 직관적 개념으로 이해하는게 쉬울 때도 있습니다.

 

 

2. 집합론적으로 생각하기

[0, 1] 사이의 모든 실수는 소수점 아래로 0 또는 1이 무한히 나열되는 이진수열로 표현될 수 있다고 했죠?

• 1/3 = 0.010101...2​ -> (0, 1, 0, 1, 0, 1, ...)
• 1/2 = 0.100000...2​ -> (1, 0, 0, 0, 0, 0, ...)
• π−3 = 0.001001...2​ -> (0, 0, 1, 0, 0, 1, ...)

 

여기서 각 숫자는 '무한한 선택의 결과물'로 볼 수 있습니다.

• 첫 번째 자리에 0을 쓸까, 1을 쓸까? (2가지 선택)
• 두 번째 자리에 0을 쓸까, 1을 쓸까? (2가지 선택)
• 세 번째 자리에 0을 쓸까, 1을 쓸까? (2가지 선택)
• ...
• n번째 자리에 0을 쓸까, 1을 쓸까? (2가지 선택)
• 이 선택을 무한히 계속합니다.

 

이것을 집합론의 언어로 표현한 것이 바로 $ \{0,\ 1\}^\mathbb{N} $ 입니다.

• {0, 1}: 각 자리에서 선택할 수 있는 기호의 집합 (0 또는 1)
• $\mathbb{N}$: 자연수 집합 {1, 2, 3, ...}을 의미하며, 여기서는 '첫 번째, 두 번째, 세 번째,...'와 같이 자리의 위치를 나타냅니다.
• $\{0,\ 1\}^\mathbb{N}$: $\mathbb{N}$의 각 원소(각 자리)에 {0, 1}의 원소(0 또는 1)를 하나씩 대응시키는 모든 가능한 함수(경우의 수)의 집합을 의미합니다. 즉, '모든 가능한 무한 이진수열의 집합'을 뜻하는 기호입니다.

그리고 집합론에서 $2^{|A|}$는 A의 멱집합(Power Set), 즉 A의 모든 부분집합들의 집합의 크기를 의미합니다. (여기서 $ |A| $표시는 집합 A의 크기를 뜻합니다)

자, 이 두가지 개념을 가지고 실수의 크기를 유도해 봅시다.

 

핵심 아이디어는 결국 두 개념 '$\{0,\ 1\}^\mathbb{N}$' 과 '자연수의 모든 부분집합'을 1:1로 연결하는 것입니다.

$ \{0,\ 1\}^\mathbb{N} $에 속하는 하나의 무한 이진수열이, 자연수의 부분집합 하나와 완벽하게 짝을 이룰 수 있다면 믿으시겠습니까?

예를 들어보죠. 어떤 이진수열 s = (1, 0, 1, 1, 0, ...) 가 있다고 합시다.

이 수열을 가지고 자연수의 부분집합을 만드는 규칙을 정하는 거예요. "n번째 숫자가 1이면, 자연수 n을 부분집합에 포함시킨다!"

• 첫 번째 숫자(1)가 1이니까 -> 1을 포함
• 두 번째 숫자(2)가 0이니까 -> 2는 미포함
• 세 번째 숫자(3)가 1이니까 -> 3을 포함
• 네 번째 숫자(4)가 1이니까 -> 4를 포함
• 다섯 번째 숫자(5)가 0이니까 -> 5는 미포함
• ... 이렇게 무한히 계속합니다.

결과적으로, 이진수열 s = (1, 0, 1, 1, 0, ...) 는 자연수의 부분집합 {1, 3, 4, ...} 와 정확히 짝을 이룹니다.

이 관계는 완벽한 1:1 대응입니다.

• 어떤 무한 이진수열을 가져와도, 그에 해당하는 부분집합은 유일하게 단 하나 존재합니다.
• 반대로, 자연수의 어떤 부분집합을 가져와도(예: {2, 5, 6}), 그에 해당하는 이진수열 (0, 1, 0, 0, 1, 1, ...)은 유일하게 단 하나 존재합니다.

따라서 $ \{0,\ 1\}^\mathbb{N} $(모든 무한 이진수열의 집합)의 개수는 자연수의 모든 부분집합의 개수와 정확히 같습니다.

 

자연수의 집합 $\mathbb{N}$의 크기가 $ \aleph_0 $​이므로, 자연수의 모든 부분집합의 개수는 $2^{\aleph_0}$입니다. 그러므로 $ \{0,\ 1\}^\mathbb{N}$의 크기(=실수 $\mathbb{R}$의 크기} 역시 $2^{\aleph_0}$가 됩니다.

 

하나 더 나아가서, '왜 우리는 $ \{0,\ 1\}^\mathbb{N}$의 크기의 크기를 본건데 이게 왜 실수 $\mathbb{R}$의 크기와 같은데염?'이라면, $ \tan(\pi(x-\frac{1}{2})) $와 같은 함수를 통과시키면, 0과 1 사이값이 실수 전체로 확장될 수 있기 때문입니다.

이는 $ \aleph_0 $보다 명백히 더 큰 '비가산 무한'입니다. 이 크기가 $ \aleph_0 $ 바로 다음 크기의 무한인 $ \aleph_1 $과 같은지는 연속체 가설에 따라 달라지기에(연속체 가설은 ZFC 공리계에서는 독립적이다. 즉, ZFC로부터 참도, 거짓도 증명할 수 없다.) 아직 해결되지 않은 문제입니다.
이 크기는 또한 연속체의 농도($\mathfrak{c}$)와 같은 다른 기호로도 표현합니다.

 

 

7. 결론

놀랍게도 무한에도 서로 다른 등급이 존재한다는 사실!

무한이라고 다 같은 무한이 아닙니다.
어떤 무한은 셀 수 있고,
어떤 무한은 셀 수조차 없습니다.

칸토어는 바로 이걸 처음으로 엄밀하게 증명해낸 수학자입니다.

그의 손끝에서 ‘무한의 계층 구조’가 드러난 거죠.