집합의 기수와 무한집합 2 - 무한집합과 유한집합, 가산집합과 비가산집합

 

Post 2 - 무한집합과 유한집합, 가산집합과 비가산집합

안녕하세요! 이번 연재의 두 번째 파트인 무한집합과 가산집합에 대한 내용입니다. 지난 시간에는 집합의 기수(cardinality)에 대해 자세하게 살펴보았는데요. 이번 포스팅부터는 지난 포스팅에서 다룬 내용을 활용하여 본격적으로 집합의 원소의 개수와 무한 집합에 대해 자세하게 알아보도록 하겠습니다.

자연수의 집합과 유한집합

우선 무한에 대해 다루기 전에, 우리에게 친숙한 유한집합과 자연수의 집합에 대해 살펴보도록 하겠습니다.

무한 집합과 유한 집합을 어떻게 정의할까요? 일단 확실한 것은, 유한 집합은 무한 집합이 아닌 집합이고, 무한 집합은 유한 집합이 아닌 집합입니다만, 유한 집합을 엄밀하게 정의하는 것은 생각보다 어려운 일입니다.

지난 포스팅 때 언급하였듯, 자연수에는 두 가지 기능이 있습니다. 그 중 ‘크기’ 혹은 '개수’를 세는 기능을 활용한다면, 어느 집합 $A$의 기수가 자연수로 표현된다면, 그 집합 $A$는 유한 집합이라고 정의할 수 있겠습니다. 현재로서는 이 '정의’로 만족하기로 하고, 무한 집합에 대한 소개를 한 후, 무한 집합을 정의하는 성질을 소개하도록 하겠습니다.

이제 유한 집합에 대한 얘기는 마쳤습니다만, 자연수 전체의 집합 $\mathbb{N}$, 유리수 집합 $\mathbb{Q}$, 실수 집합 $\mathbb{R}$ 등의 무한 집합에 대해서는 기수를 어떻게 정의해야 할 까요? 이 집합들의 기수는 같을까요, 다를까요?

우선 자연수 집합의 기수를 ${\aleph }_0$ (aleph zero, or aleph naught)로 정의하는 것에서 시작하도록 하겠습니다. 자연수 집합이 무한이라는 것은, 자연수의 정의와 완비성 공리를 통해 확인하실 수 있습니다. 어떤 $n$이 자연수라면, $n+1$ 또한 자연수가 되어, 자연수 전체의 집합 $\mathbb{N}$에는 상한이 존재하지 않게 됩니다.

이제 가산집합(countable set)을 정의하고자 합니다. 자연수 전체의 집합 $\mathbb{N}$은 무한 집합이지만, 집합의 모든 원소에 '개수’를 세주는 역할을 하는 하나의 자연수를 대응시킬 수 있습니다(대응 시키는 것이 아니라, 원소의 이름이 자연수죠). 따라서, $\mathbb{N}$은 가산 집합이라고 정의합니다. 또한, (당연하게도) 모든 유한 집합은 가산 집합입니다. 아직 그 예시들을 살펴보지는 않았으나, 가산 집합이 아닌 집합을 비가산 집합(uncountable set)이라고 정의할 수 있습니다.

이제 본 포스팅의 핵심인, 가산집합과 비가산집합을 분류하는 부분입니다. 우선 무한 세계에서 벌어지는 반직관적인 일들을 소개하도록 하겠습니다. $A\approxeq B$ 라는 표현은 집합 $A$와 $B$의 기수가 같음을 의미하는 표기로 이해하시면 됩니다.

Example 1) $\mathbb{N}\approxeq {\mathbb{N}}_{even}$, where ${\mathbb{N}}_{even}$ is the set of even integers.
Proof) Define $f:\mathbb{N}\to {\mathbb{N}}_{even}$ by $f(x)=2x$. Then, $f$ is a bijection.

즉, 짝수 전체의 집합의 기수는 자연수 전체의 집합의 기수와 같다는 뜻입니다. 여기서 반직관적인 부분은, 자연수 전체의 집합의 개수는 짝수의 개수 보다 훨씬 많아보인다는 점입니다. 짝수 전체의 집합은 자연수 전체 집합의 진부분집합이며, 심지어 짝수를 제외한 자연수의 집합에는 홀수가 무한히 많이 있음에도 불구하고, 두 집합의 원소의 '개수’는 같음을 위 예시가 보여주고 있습니다.

하나의 간단한 예시만 살펴보았으나, 무한 집합에서, 그리고 오직 무한 집합일 경우에만 성립하는 성질이 있습니다:

• 무한집합은 자기 자신과 기수가 같은 진부분집합이 존재한다.

실제로 위 성질을 사용하여 무한 집합을 정의한 후, 무한 집합이 아닌 집합을 유한 집합으로 정의하기도 합니다.

이제 자연수 집합 $\mathbb{N}$과 동등한 집합들을 더 살펴보도록 하겠습니다. 대부분의 경우 증명 없이 넘어갈 것인데, 집합론 기본서를 참고하시거나 구글링을 통해 손 쉽게 증명을 찾으실 수 있습니다.

Example 2) $\mathbb{N}\approxeq \mathbb{N}\times \mathbb{N}$
Proof) 이 경우 전단사 함수를 다음과 같이 잡을 수 있습니다. $f:\mathbb{N}\times \mathbb{N}\to \mathbb{N}$ by $f(m,n)=\frac{1}{2}[(m+n{)}^2+3m+n]$. 여기서 [ ] 는 반올림 함수입니다. 실제 이 함수가 단사임은 쉽게 보일 수 있고, 전단사임을 보이기 위해 역함수를 직접 잡을 수 있습니다. 우선 다음 사실을 이용 하겠습니다. 각 $k\in \mathbb{N}$에 대해 다음을 만족하는 유일한 자연수 $l\in \mathbb{N}$이 존재합니다:
$$\frac{1}{2}l(l+1)\le k<\frac{1}{2}(l+1)(l+2)$$
이제 $g(k)$를 다음과 같이 정의하면 $f$와 $g$는 역함수 관계이고, 이는 $f$가 전단사 함수임을 함축합니다. (역함수 관계임을 보이기 위해서는 두 함수의 합성이 각각 identity mapping이 됨을 보이시면 됩니다).
$$g(k)=(k-\frac{1}{2}l(l+1),l-[k-\frac{1}{2}l(l+1)])$$
Example 3) A countable union of countable sets is countable.
Example 4) A countable product of countable sets is countable.
Example 5) $\mathbb{N}\approxeq \mathbb{Q}$
Proof) 우선, $f:\mathbb{N}\to \mathbb{Q}$를 $f(x)=x$로 정의하면, $f$는 단사함수가 되므로, $\mathrm{card}(\mathbb{N})\le \mathrm{card}(\mathbb{Q})$가 됩니다. 이제 슈뢰더-베른슈타인 정리에 의해, $\mathbb{Q}$에서 $\mathbb{N}$으로의 단사 함수를 정의하면 됩니다. 이는 유리수를 다음과 같은 방법으로 '나열’하면 됩니다.

두 개의 단사함수를 정의하면, $\mathrm{card}(\mathbb{Q})\le \mathrm{card}(\mathbb{N})$이 됩니다. 전 포스팅에서, 기수는 크기와 관련된 세 가지 공리를 만족한다 하였으니, $\mathrm{card}(\mathbb{N})=\mathrm{card}(\mathbb{Q})$가 됩니다.

이제 본 포스팅의 마지막 내용입니다. 자연수 집합의 기수와 유리수 집합의 기수는 같음을 보였으나, 과연 실수의 집합 또한 자연수의 집합과 대등, 즉 가산 집합일지 보여보고자 합니다. 여기서 꽤나 놀라운 결과가 나오는데요. 구간 $[0,1]$ 안에 존재하는 실수의 개수가 자연수 전체의 개수보다 많다는 것입니다.

Cantor’s Theorem) 집합 $\mathbb{N}$에서 구간 $[0,1]$로의 전사함수가 존재하지 않는다.
Proof) $f:\mathbb{N}\to [0,1]$일 때, 각 $n=0,1,2,...$의 상 $f(n)$을 무한소수로 표기하면,
$$\begin{gathered} f(0)=0.x_{00}{x}_{01}{x}_{02}... \\ f(1)=0.x_{10}{x}_{11}{x}_{12}... \\ f(2)=0.x_{20}{x}_{21}{x}_{22}... \\ ... \\ f(n)=0.x_{n0}{x}_{n1}{x}_{n2}... \end{gathered}$$
로 표기된다. 이제 수열 $(a_n)$을 다음과 같이 정의하면,
$$a_n=\{\begin{array}{l}0,x_{nn}\ne 0\\ 1,x_{nn}=0\end{array}$$
$\alpha =0.a_0{a}_1{a}_2...a_n...\in [0,1]$이나, 모든 자연수 $n$에 대해 $f(n)\ne \alpha$이어서 $f$는 전사함수가 될 수 없습니다.

$[0,1]$은 $\mathbb{R}$의 진부분집합이므로 (실제로, 다음 포스트에서 자세히 살펴보겠지만 $[0,1]$은 $\mathbb{R}$과 대등합니다), 실수의 개수는 자연수의 개수보다 많다고 볼 수 있겠습니다. 즉, 실수의 집합이 비가산집합(uncountable set)의 대표적인 예시입니다.

본 포스트에서 유한집합과 무한집합, 가산집합과 비가산집합에 대해 알아보았고, 예시들을 통해 무한집합의 성질에 대해 간략하게 알아보았습니다. 다음 포스트에서는 보다 많은 예시를 소개하고, 보다 심화된 내용인 칸토어 집합을 소개하도록 하겠습니다.