집합의 기수와 무한집합 3 - 비가산집합의 예시, Power Set, Cantor Set

 

Post 3 - 비가산집합의 예시, Power Set, Cantor Set

안녕하세요! 벌써 집합의 기수에 관한 마지막 포스팅이 되었습니다. 우리는 지금까지 (상당히 많은 사전 논의를 배제하고) 집합의 기수의 정의, 무한집합과 유한집합, 가산집합과 비가산집합에 대해 살펴보고, 비가산집합과 무한에 대한 연구를 촉발시켰던 칸토어의 정리를 살펴보았습니다. 칸토어 정리의 핵심은, 무한에도 '크기’가 존재하고, 모든 무한 집합의 '크기’가 같지는 않음을 보였음에 있는데요.

얼핏보면 자연수의 개수가 구간 $[0,1]$에 존재하는 실수의 개수보다 훨씬! 많아야 할 것 같습니다. 칸토어의 정리는 그 함의와 증명이 너무 반직관적이어서 당시 많은 수학자에게 비판을 받기도 하였다고 합니다. (와닿지 않으시더라도 괜찮다는 뜻입니다 ㅎㅎ).

사실 칸토어의 정리는 그 논리 전개 방식이 다음 정리 "임의의 집합 $A$에 대해 집합 $A$로부터 집합 $A$의 부분집합의 집합으로의 전사함수는 존재하지 않는다"와 정확하게 같습니다. 따라서 본 포스팅에서는 지난 번 소개했던 칸토어 정리의 이해를 돕기 위해 위 정리를 소개하고, 실수의 집합 $\mathbb{R}$의 기수를 보다 구체적으로 구해보려고 합니다. 그리고 실수의 집합 $\mathbb{R}$과 동일한 기수를 가지는 집합들의 종류를 더 소개하고, 칸토어의 집합을 소개하는 것으로 본 연재를 마치도록 하겠습니다.

Theorem) 임의의 집합 $A$에 대해, $A$에서 $\mathcal{P}(A)$로의 전사함수는 존재하지 않는다. (여기서 $\mathcal{P}(A)$는 $A$의 부분집합들의 집합 or the power set of A)
Proof) 임의의 함수 $f:A\to \mathcal{P}(A)$를 생각하자. 이제, 다음과 같은 집합을 생각한다.
$$C=\{a\in A|a\notin f(a)\}$$
$C$는 $A$의 부분집합이므로, $C\in \mathcal{P}(A)$이다. 그러나, 어떤 $a\in A$에 대해서도, $f(a)\ne C$가 된다. 왜냐하면, $a\in C$이면, $C$의 조건에 의해 $a\notin f(a)$가 되어, $f(a)\ne C$이다. 이제, $a\notin C$이면, $a\in f(a)$가 되어, $f(a)\ne C$이다. 어느 경우에도 $f(a)\ne C$이므로 $f$는 전사가 될 수 없다.

사실 위의 증명도 꽤나 머리가 아픈 증명이긴 합니다만, 칸토어 정리의 증명과 대조하여 음미해보시면 이해가 될 것이라 생각합니다. 그리고 마지막으로 언급할 것은, 위의 정리에서 집합 $A$는 임의의 집합이므로, 무한 집합일 경우에도 성립합니다. 또한, $\mathcal{P}(A)$의 기수는 $\mathrm{card}(2^A)$로 표기합니다.

위 정리를 기억하시면 다음 내용을 이해하는데 용이할 것이라 생각합니다.

Theorem) $\mathrm{card}(\mathbb{R})=\mathrm{card}(2^{\mathbb{N}})$
Proof) $\mathcal{P}(\mathbb{N})$에서 $\mathbb{R}$로의 전단사 함수를 잡으면 됩니다. 증명의 편의를 위해 슈뢰더-베른슈타인 정리를 활용하고자 합니다. 또한, 이후 증명할 것이나, $\mathbb{R}$과 구간 $[0,1]$의 기수는 동일하기 때문에, $\mathcal{P}(\mathbb{N})$에서 $[0,1]$로의 전단사 함수를 잡아보도록 하겠습니다.

우선 본 증명의 핵심은 $[0,1]$의 수를 이진법으로 전개할 수 있다는 것입니다. 다만 무한소수에 대한 부분을 주의해야 합니다. 예를 들어, $\mathrm{0.10000..}{.}_{(2)}$와 $\mathrm{0.011111..}{.}_{(2)}$는 같은 수이기 때문에, 함수가 전단사임을 보임에 있어 걸림돌이 됩니다. 따라서 우리는 둘 중에 하나의 표현방법만을 택하도록 하겠습니다. 본 증명에서는 후자의 표현방법을 사용합니다. 그래야 1을 표현하는 데 번거로움이 없습니다.

단사함수 $f:[0,1]\to 2^{\mathbb{N}}$를 정의해보고자 합니다. 임의의 $a\in [0,1]$에 대해, $a$를 위에서 논의한 것과 같은 방식으로 이진법과 소수 표현을 사용해 표현해보면, $a=0.a_1{a}_2{a}_3...$가 되고, $a_i=0\text{ or }1$이 됩니다. 이제 $f(a)=\{n\in \mathbb{N}|a_n=1\}$로 정의 하겠습니다. 그러면, 위 함수는 이진수 표기법이 유일하므로 잘 정의되었고, 단사가 됨을 확인하실 수 있습니다.

이제 단사함수 $g:2^{\mathbb{N}}\to [0,1]$를 정의하고자 합니다. 본 증명에서는 앞서 말한 무한소수의 문제 때문에 이진수 표기법을 사용하지 않는 것이 더 편합니다. 이제 $g$를 다음과 같이 정의하도록 하겠습니다. $A\in \mathcal{P}(A)$에 대해, $$g(A)=0.a_1{a}_2{a}_3...,\{\begin{array}{l}{a}_i=2\text{ if }i\in A\\ a_i=0,\text{otherwise}\end{array}$$
로 정의하면, $g$ 역시 잘 정의되었고, 단사 함수임이 분명합니다. 따라서 증명이 끝납니다.

이제 칸토어 집합을 소개하기 전 마지막 내용입니다. 위에서 $[0,1]$과 $\mathbb{R}$의 기수는 같다고 말하였는데요. $\mathbb{R}=(-\infty ,\infty )$로 이해하였을 때, 보다 강한 조건인 다음 명제가 성립합니다.

Theorem) 임의의 두 구간 사이에는 전단사 함수가 존재한다.
Proof) 우선, 구간에는 총 9가지 종류가 있습니다. $$(-\infty ,\infty ),(a,b),[a,b],[a,b),(a,b],[a,\infty ),(a,\infty ),(-\infty ,b),(-\infty ,b]$$
전단사 함수의 합성은 전단사이기 때문에, 총 8개의 함수만 잡아주면 됩니다. 또, 이미 우리가 잘 알고 있는 함수를 사용해서 잡아줄 수도 있습니다만, 몇 가지 경우는 증명이 꽤나 까다롭습니다 (힐베르트의 호텔과 비슷한 논의를 사용해야 합니다).

구체적으로 함수를 잡는 것은 본 포스팅에서 중요하게 다루는 부분과 무관하므로, 몇 가지 예시만 소개하도록 하겠습니다.

1. $f:(a,b)\to (-\infty ,\infty )$ by $f=tan(\frac{\pi }{b-a}(x-\frac{b+a}{2}))$
2. $f:(-\infty ,\infty )\to (a,\infty )$ by $f=e^x+a$
3. $f:[a,b]\to [a,b)$ by $f(x)=\{\begin{array}{l}b-\frac{b-a}{2}\text{ if }x=b\\ b-\frac{b-a}{n+2}\text{ if }x=b-\frac{b-a}{n}\\ x\text{ otherwise}\end{array}$

등의 방식으로 나머지 함수들을 찾으실 수 있습니다.

이제 본 포스팅의 마지막 내용인 칸토어 집합(Cantor Set)에 대한 정리입니다. 우선 칸토어 집합이 무엇인지 설명하고 그 함의에 대해 설명하도록 하겠습니다.

Definition) (칸토어 집합) 구간 $I=[0,1]$에 대해, $I_1,I_2,I_3...$를 다음과 같이 정의한다. $$I_1=I\backslash J_1=I\backslash \left(\frac{1}{3},\frac{2}{3}\right)$$
즉, 구간을 삼등분 하여 가운데 열린구간을 제외한다. $I_{n+1}$은 $I_n$의 구간들을 각각 삼등분하여 가운데 열린구간을 제외하여 표기한다.
$$I_2=I_1\backslash \left(\frac{1}{9},\frac{2}{9}\right)\cup \left(\frac{7}{9},\frac{8}{9}\right)$$
이러한 방식으로 $I_n$을 구성해나가고, 구성된 모든 $I_n$의 교집합을 칸토어 집합으로 정의한다. 즉, $C={\cap }_{n=1}^{\infty }{I}_n$ 이다.

이제 특이한 점은, 이러한 과정을 통해 제거한 열린구간의 길이를 전부 합치면, 초항이 $\frac{1}{3}$, 공비가 $\frac{2}{3}$인 무한 수열이 되어, 그 합이 $1$이 됩니다. 즉, 칸토어 집합의 원소들의 '길이’를 재면, 0이 되어 $C$ 안에 남아 있는 점은 거의 없어야 할 것 같습니다. 그러나 실제로 칸토르 집합은 비가산 집합이 됩니다. (띠용!)

이를 보이기 위해 $C$에서 구간 $[0,1]$로의 전사 함수를 잡을 수 있는데요. $C$안의 원소를 삼진법으로 전개를 하면, 그 소수점 자리에는 $0$과 $2$만이 나옴을 알 수 있습니다. 이제 $2$가 나오는 자리를 $1$로 대치하면, 구간 $[0,1]$의 점이 되어 $C$에서 $[0,1]$로의 전사함수를 잡을 수 있습니다. 즉, $\mathrm{card}(C)\ge \mathrm{card}([0,1])$이 되고, 구간 $[0,1]$은 비가산 집합이므로, $C$ 또한 비가산 집합입니다. 추가로, $\mathcal{P}(\mathbb{N})$에서 $C$로의 전단사 함수를 직접 잡을수도 있습니다.

칸토어가 이 내용을 발표하였을 때 왜 반발이 거셌는지 이해가 되는 것도 같습니다. 여기서 한 걸음 더 나아가면, 칸토어 집합 안에는 어떤 구간도 포함되지 않음을 보일 수 있습니다. 즉, discrete한 점들로만 이루어져 있고, 그 길이를 전부 합하면 $0$임에도 불구하고 비가산 집합인 아주 요상한(?) 예시가 되겠습니다. 그리고 첫 포스팅에서 말씀드렸듯, 르벡 적분과 확률론에서 아주 중요한 개념인 측도(measure)의 개념의 탄생에 밑바탕이 된 것이 칸토어 집합이기도 합니다.

이것으로 제가 처음 계획했던 내용은 모두 공유드린 것 같습니다. 사실 제가 소개드린 내용들은, 그 증명과 디테일을 모두 기억하기보다 결과와 함의를 위주로 기억하셔도 충분하실 것 같습니다 (수학과에 진학하시면 2,3학년 초반 집합론, 해석학 관련 과목에서 심도있게 배우실 기회가 있으실 겁니다). 저 또한 세세한 증명보다는 혼자 생각하기 어려운 증명의 경우 아이디어만 제시해드리고, 내용과 흐름을 위주로 설명을 드리고자 하였습니다.

혹여 틀린 부분이나, 이해가 안 되는 부분은 댓글을 남겨주시면 부가 설명을 드려보도록 하겠습니다. 기회가 된다면 또 다시 새로운 수학 얘기로 찾아오겠습니다. 읽어주셔서 감사합니다 :)