수학/집합론

[집합의 크기] ch2. 가산집합과 비가산집합

김한결 2022. 11. 22. 18:43

이전 읽을거리)

[집합론 기초] ch5. 집합의 모임

데카르트 곱의 일반화된 정의

ch1. 유한집합

다음 읽을거리: ch3. 유리수 집합과 실수 집합의 크기

무한의 정의

마치 자연수의 절편이 유한집합의 원형이듯이, 모든 자연수의 집합은 가산무한집합이라고 불리는 것들의 원형이다. 앞으로 유한하지도, 가산무한하지도 않은 집합을 구성하는 것에 대해 살펴볼 것이다.

Definition. 집합 $A$ 가 유한하지 않으면 무한하다(infinite)고 한다. 일대일대응 $A\to\mathbb{N}$ 이 존재하면 $A$ 가 셀 수 있게 무한하다(countably infinite)고 하거나 가산무한이라고 한다.

예를들면, 모든 정수의 집합 $\mathbb{Z}$ 는 셀 수 있게 무한하다. 다음의 함수 $f:\mathbb{Z}\to\mathbb{N}$ 은 일대일대응이다.

$$f(n)=\begin{cases}2n&\text{for }n>0\\-2n+1&\text{for }n\le 0\end{cases}$$

또 다른 예시로 $\mathbb{N}\times\mathbb{N}$ 는 셀 수 있게 무한하다. $\mathbb{N}\times\mathbb{N}$ 의 각 원소를 좌표평면의 제1사분면 위의 격자점으로 표현하여 아래의 그림과 같이 세는 방법을 생각해볼 수 있다.

이는 자연수에서 자연수의 순서쌍으로의 일대일대응을 만드는 방법을 보여주고있다. 물론 그림은 증명이 아니지만, 일대일대응이 존재함을 암시하기에는 충분하다. 증명은 후술할 것이다.

Definition. 유한하거나 셀 수 있게 무한한 집합을 셀 수 있다(countable)고 하거나 가산이라고 한다. 셀 수 있지 않은 집합을 셀 수 없다(uncountable)고 하거나 비가산이라고 한다.

가산의 성질

다음은 집합이 셀 수 있음을 보이는 유용한 판정법을 알려준다.

Theorem 2.1. 공집합이 아닌 집합 $B$ 에 대해 다음의 세 명제는 동치이다.
(1) $B$ 는 셀 수 있다.
(2) 전사함수 $\mathbb{N}\to B$ 가 존재한다.
(3) 단사함수 $B\to\mathbb{N}$ 이 존재한다.

Proof.

($1\Rightarrow 2$) 가산집합 $B$ 를 생각하자. 만약 $B$ 가 셀 수 있게 무한하면 정의에 따라 전단사함수 $\mathbb{N}\to B$ 가 존재한다. 만약 $B$ 가 유한하면 정의에 따라 어떤 자연수 $n$ 에 대해 전단사함수 $h:\{1,\ldots,n\}\to B$ 가 존재한다. 이때 다음과 같이 $h$ 를 확장하여 얻은 함수 $f:\mathbb{N}\to B$ 는 전단사이다.

$$f(i)=\begin{cases}h(i)&\text{if }i\in\{1,\ldots,n\}\\h(1)&\text{otherwise}\end{cases}$$

($2\Rightarrow 3$) 전사함수 $f:\mathbb{N}\to B$ 에 대해, 함수 $g:B\to\mathbb{N}$ 을 각 $b\in B$ 에 대해 $g(b)=\text{min }f^{-1}(\{b\})$ 라고 정의하자. $f$ 는 전사이므로 $f^{-1}(\{b\})$ 는 공집합이 아니며 정렬원리에 따라 최소원소가 존재하므로 $g$ 가 잘 정의된다. 이때 $b\neq b'$ 에 대해 $f^{-1}(\{b\})$ 와 $f^{-1}(\{b'\})$ 는 서로소이므로 각 집합의 최소원소도 서로 다르다. 따라서 $g$ 는 단사이다.

($3\Rightarrow 1$) 단사함수 $g:B\to\mathbb{N}$ 에 대해, $g$ 의 치역을 $S$ 라고 하자. 이때 함수 $h:B\to S$ , $h(b)=g(b)$ 는 전단사이다. 만약 $\mathbb{N}$ 의 부분집합인 $S$ 가 셀 수 있다면 $\mathbb{N}$ 또는 자연수의 절편으로의 전단사함수 $\pi$ 가 존재하여 함수 $h\circ\pi$ 로써 $B$ 가 셀 수 있음을 알 수 있다. 그러므로 이를 증명하기 위해서는 $N$ 의 모든 부분집합이 셀 수 있음을 보이는 것으로 충분하다. $\mathbb{N}$ 의 부분집합 $C$ 를 생각하자.

만약 $C$ 가 유한하다면 정의에 따라 셀 수 있다. 그러므로 이 증명을 위해 필요한 것은 $\mathbb{N}$ 의 모든 무한부분집합 $C$ 가 셀 수 있게 무한하다는 성질이다. 이 표현은 분명히 타당하다. 올바른 순서로 집합 $\mathbb{N}$ 을 취하고, $C$ 에 속하지 않는 $\mathbb{N}$ 의 모든 점들을 "지워버리는" 것으로 $C$ 의 원소를 무한수열로 재배열할 수 있다.

이러한 주장의 놀라운 타당성은 이것이 상당히 형식적이지 못하다는 사실을 간과하게 만들기도 한다. 형식적인 증명에는 많은 주의가 필요하다. 나머지 증명은 아래의 도움정리에서 이어진다. $\square$

Lemma 2.2. $\mathbb{N}$ 의 무한부분집합은 셀 수 있게 무한하다.

Proof. $\mathbb{N}$ 의 무한부분집합 $C$ 에 대해 전단사함수 $h:\mathbb{N}\to C$ 를 귀납적으로 정의하자. 먼저 $C$ 의 최소원소를 $h(1)$ 이라고 하자. 이제 $h(1),\ldots,h(n-1)$ 이 정의되었다고 가정하고 $h(n)$ 을 $C\setminus h(\{1,\ldots,n-1\})$ 의 최소원소라고 정의하자. 이때 만약 $C\setminus h(\{1,\ldots,n-1\})$ 이 공집합이라면 $C$ 는 $h(\{1,\ldots,n\})$ 의 부분집합이며 따름정리 1.6.에 따라 $C$ 가 유한하다는 모순이 발생하므로 $C\setminus h(\{1,\ldots,n-1\})$ 는 공집합이 아니다. 따라서 $h(n)$ 은 잘 정의된다. 이제 귀납법에 따라 모든 $n\in\mathbb{N}$ 에 대해 $h(n)$ 이 정의된다.

$h$ 가 단사임을 보이는 것은 쉽다. 주어진 $m<n$ 에 대해 $h(m)$ 은 $h(\{1,\ldots,n-1\})$ 에 속하고, 정의에 따라 $h(n)$ 은 속하지 않는다. 따라서 $h(m)\neq h(n)$ 이므로 원하는 결과를 얻는다.

$h$ 가 전사임을 보이자. $C$ 의 임의의 원소 $c$ 에 대해 $C$ 가 $h$ 의 치역에 속함을 보이자. $h$ 는 단사이기 때문에 함수 $g:\mathbb{N}\to h(\mathbb{N})$ 을 $g(n)=h(n)$ 으로 정의한다면 $g$ 는 전단사이므로 $h(\mathbb{N})$ 은 무한하다. 따라서 $h(\mathbb{N})$ 은 유한집합 $\{1,\ldots,c\}$ 에 속하지 않는다. 그러므로 $h(n)\neq c$ 이도록 하는 $n\in\mathbb{N}$ 이 존재하며, 특히 $h(n)>c$ 이다. $\mathbb{N}$ 의 원소 중 $h(m)\ge c$ 를 만족하는 최소원소 $m$ 을 선택하자. ($h(m)\ge c$ 를 만족하는 자연수 $m$ 은 $h(n)>c$ 를 만족하는 $n$ 이 있으므로 적어도 하나 존재하며, 정렬원리에 따라 이러한 최소원소 $m$ 이 존재한다) 이때 모든 $i<m$ 에 대해 $h(i)\ge c$ 가 성립하지 않으므로 ($m$ 은 이러한 성질을 만족하는 최소원소라 하였기 때문) $h(i)<c$ 이며, 따라서 $h(i)\neq c$ 이므로 $c$ 는 $h(\{1,\ldots,m-1\})$ 에 속하지 않는다. 여기서 $h(m)$ 은 $C\setminus h(\{1,\ldots,m-1\})$ 의 최소원소로 정의되었으므로 $h(m)\le c$ 가 반드시 성립해야 함을 안다. 두 개의 부등식을 같이 쓰면 $h(m)=c$ 이므로 $h$ 는 전사이다. $\square$

Corollary 2.3. 가산집합의 부분집합은 셀 수 있다.

Proof. 가산집합 $B$ 의 부분집합 $A$ 를 생각하자. 정리 2.1.에 따라 단사함수 $f:B\to\mathbb{N}$ 이 존재하며, $f|_A:A\to\mathbb{N}$ 은 단사함수이므로 다시 정리 2.1.에 따라 $A$ 는 셀 수 있다. $\square$

Corollary 2.4. $\mathbb{N}\times\mathbb{N}$ 은 셀 수 있게 무한하다.

Proof. 이를 증명하는 것은 단사함수 $f:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ 가 존재함을 보이는것으로 충분하다. 함수 $f$ 를 $f(n,m)=2^n3^m$ 이라고 정의하자. $f$ 가 단사임을 보이는 것은 쉽다. $2^n3^m=2^p3^q$ 라고 하자. 만약 $n<p$ 라면 $3^m=2^{p-n}3^q$ 이며 이는 $3^m$ 이 모든 자연수 $m$ 에 대해 홀수임에 모순된다. 따라서 $n=p$ 이다. 그러므로 $3^m=3^q$ 이며, 만약 $m<q$ 라면 $1=3^{q-m}$ 이라는 모순이 발생한다. 따라서 $m=g$ 이다. $\square$

양의 유리수의 집합 $\mathbb{Q}_+$ 에 대해 함수 $g:\mathbb{N}\times\mathbb{N}\to\mathbb{Q}_+$ 를 $g(n,m)=\frac{m}{n}$ 이라고 정의하자. $\mathbb{N}\times\mathbb{N}$ 는 셀 수 있으므로 전사함수 $f:\mathbb{N}\to\mathbb{N}\times\mathbb{N}$ 가 존재하며, 합성함수 $g\circ f:\mathbb{N}\to\mathbb{Q}_+$ 는 전사이므로 $\mathbb{Q}_+$ 는 셀 수 있다. 그리고 물론, $\mathbb{Q}_+$ 는 $\mathbb{N}$ 를 포함하므로 무한하다.

유리수 집합에 대해서도 비슷한 증명이 가능하다. 이에 대해서는 다음 포스팅에서 다룬다.

Theorem 2.5. 가산집합의 가산 합집합은 셀 수 있다.

Proof. $\{1,\ldots,n\}$ 또는 $\mathbb{N}$ 인 인덱스 집합 $J$ 에 대항, 가산집합의 모임인 인덱스 패밀리 $\{A_n\}_{n\in J}$ 를 생각하자. 편의를 위해 각 $A_n$ 이 공집합이 아니라고 가정하자. (이 가정은 아무것도 바꾸지 않을 것이다)

각 $n\in J$ 에 대해, $A_n$ 은 셀 수 있으므로 전사함수 $f_n:\mathbb{N}\to A_n$ 이 존재한다. 비슷하게, $J$ 도 셀 수 있으므로 전사함수 $g:\mathbb{N}\to J$ 가 존재한다. 이제 다음과 같이 새로운 함수 $h$ 를 정의하자.

$$h:\mathbb{N}\times\mathbb{N}\to\bigcup_{n\in J}A_n\qquad h(k,m)=f_{g(k)}(m)$$

$h$ 가 전사임은 거이 자명하다. 모든 $a\in\bigcup_{n\in J}A_n$ 은 어떤 $n\in J$ 에 대해 $a\in A_n$ 이며 $f_n$ 은 전사이므로 어떤 $m\in\mathbb{N}$ 에 대해 $f_n(m)=a$ 이다. 또한 $g$ 는 전사이므로 어떤 $k\in\mathbb{N}$ 에 대해 $g(k)=n$ 이므로 $f_{g(k)}(m)=a$ 이다. 정리하면 어떤 $k\in\mathbb{N}$ , $m\in\mathbb{N}$ 에 대해 $h(k,m)=a$ 이므로 $h$ 는 전사이다. 한편 $\mathbb{N}\times\mathbb{N}$ 은 $\mathbb{N}$ 과 일대일대응을 이루므로 전사함수 $\mathbb{N}\to\bigcup_{n\in J}A_n$ 가 존재함을 알 수 있다. 따라서 이 합집합은 셀 수 있다. $\square$

Theorem 2.6. 가산집합의 유한 곱은 셀 수 있다.

Proof. 먼저 두 가산집합 $A,B$ 의 곱 $A\times B$ 가 셀 수 있음을 보이자. 만약 $A$ 또는 $B$ 가 공집합이면 $A\times B=\varnothing$ 이므로 $A\times B$ 는 셀 수 있다. 그 밖의 경우, 전사함수 $f:\mathbb{N}\to A$ 와 $g:\mathbb{N}\to B$ 가 존재한다. 이제 함수 $h:\mathbb{N}\times\mathbb{N}\to A\times B$ 를 $h(n,m)=\big(f(n),g(m)\big)$ 이라고 정의하면 $h$ 는 전사이며 $\mathbb{N}\times\mathbb{N}$ 은 $\mathbb{N}$ 과 일대일대응을 이루므로 $A\times B$ 는 셀 수 있다.

이제 귀납법으로 본 정리를 증명하자. 가산집합 $A_1,\ldots,A_n$ 에 대해 $A_1\times\cdots\times A_{n-1}$ 이 셀 수 있다고 가정하고 $A_1\times\cdots\times A_n$ 이 셀 수 있음을 보이자. 먼저 $(A_1\times\cdots\times A_{n-1})\times A_n$ 과 $A_1\times\cdots\times A_n$ 사이에는 자명한 일대일대응

$$\big((x_1,\ldots,x_{n-1}),x_n\big)\leftrightarrow(x_1,\ldots,x_n)$$

이 존재한다는 사실을 기억하자. 귀납법 가정에 따라 $A_1\times\cdots\times A_{n-1}$ 과 $A_n$ 은 셀 수 있으므로 위의 논의에 따라 이 두 집합의 곱은 셀 수 있다. 따라서 $A_1\times\cdots\times A_n$ 도 셀 수 있으므로 귀납법에 따라 원하는 결과를 얻는다. $\square$

셀 수 없는 집합의 예시

위 정리에서 가산집합의 유한 곱이 가산임을 알아보았다. 여기에서 앞서나가 가산집합의 가산 곱도 셀 수 있다고 주장하고 싶어지지만, 이는 사실이 아니다.

Theorem 2.7. $\{0,1\}^\omega$ 는 셀 수 없다.

※ $\{0,1\}^\omega$ 란 집합 $\{0,1\}$ 의 원소를 성분으로 갖는 $\omega$-순서쌍의 집합으로 $\{0,1\}\times\{0,1\}\times\cdots$ 라고도 표기한다. $\omega$-순서쌍이란 정의역이 $\mathbb{N}$ 인 함수이며, 직관적으로는 "셀 수 있게 무한히 많은 성분을 갖는 순서쌍" 으로 이해된다. 자세한 내용은 데카르트 곱의 일반화된 정의 참고.

Proof. 이를 증명하기 위해 모든 함수 $g:\mathbb{N}\to\{0,1\}^\omega$ 가 전사일 수 없음을 보이자. 각 $n\in\mathbb{N}$ 에 대해 다음과 같이 쓰자.

$$g(n)=(x_{n1},x_{n2},\ldots,x_{nm},\ldots)$$

이때 각 $x_{ij}$ 는 0 또는 1이다. 이제 다음과 같이 $\{0,1\}^\omega$ 의 원소 $\text{y}=(y_1,y_2,\ldots)$ 를 정의하자.

$$y_n=\begin{cases}0&\text{if }x_{nn}=1\\1&\text{if }x_{nn}=0\end{cases}$$

모든 $n\in\mathbb{N}$ 에 대해 $g(n)$ 과 $\text{y}$ 는 n번째 성분이 다르므로 $\text{y}$ 는 $g$ 의 치역에 포함되지 않는다. 따라서 $g$ 는 전사가 아니다. $\square$

$\{0,1\}$ 의 가산 데카르트 곱 $\{0,1\}^\omega$ 은 비가산집합의 한 가지 예시이다. 다른 예시로는 $\mathcal{P}(\mathbb{N})$ 이 있으며, 이는 정리 2.1.과 아래의 정리로 얻어지는 결과이다.

Theorem 2.8. 집합 $A$ 에 대해 단사함수 $\mathcal{P}(A)\to A$ 는 존재하지 않으며 전사함수 $A\to\mathcal{P}(A)$ 는 존재하지 않는다.

Proof. 일반적으로, 공집합이 아닌 집합 $B$ 에 대해 단사함수 $f:B\to C$ 가 존재한다면 전사함수 $g:C\to B$ 가 존재한다. 이러한 함수 $g$ 는 $f$ 의 치역의 원소 $c$ 에 대해서는 $g(c)=f^{-1}(c)$ 라고 정의하고, $C$ 의 나머지 원소에 대해서는 무작위로 정의하여 구성하여 얻을 수 있다.

그러므로, 단사함수 $\mathcal{P}(A)\to A$ 가 존재하지 않음을 보이는 것은 전사함수 $A\to\mathcal{P}(A)$ 가 존재하지 않음을 보이는 것으로 충분하다. 함수 $g:A\to\mathcal{P}(A)$ 를 생각하자. 각 $a\in A$ 에 대해 $g(a)$ 는 $A$ 의 어떤 부분집합이며, 이는 $a$ 를 포함하거나 포함하지 않는다. $g(a)$ 가 $a$ 를 포함하지 않도록 하는 $A$ 의 모든 원소 $a$ 의 집합을 $B$ 라고 하자. 즉,

$$B=\{a:a\in A\setminus g(a)\}$$

이다. (이때 $B$ 는 $g$ 에 따라 공집합이거나 또는 $A$ 그 자체일 수도 있지만 이는 중요하지 않다) 이렇게 정의된 $A$ 의 부분집합 $B$ 가 $g$ 의 치역에 속하지 않음을 보이자. 모순을 보이기 위해 어떤 $a_0\in A$ 에 대해 $g(a_0)=B$ 라고 가정하자. 이때 $a_0$ 은 $B$ 에 속하는가, 속하지 않는가? $a_0$ 과 $B$ 의 정의에 따라 다음의 세 명제는 동치이다.

$$a_0\in B\iff a_0\in A\setminus g(a_0)\iff a_0\in A\setminus B$$

이에 따르면 $a_0$ 는 $B$ 와 $A\setminus B$ 모두에 속하므로 모순이다. 따라서 $\mathcal{P}(A)$ 의 원소 $B$ 는 $g$ 의 치역에 속하지 않으므로 $g$ 는 전사가 아니다. $\square$

무한집합의 성질

지금까지 집합을 두 가지로 나누는 중요한 기준은 셀 수 있는가 없는가였다. 마지막으로는 가산과 비가산을 구분하지 않고 그저 무한집합에 대해 성립하는 성질을 간단하게 알아보자.

Theorem 2.9. 집합 $A$ 에 대해 다음의 세 명제는 동치이다.
(1) 단사함수 $\mathbb{N}\to A$ 가 존재한다.
(2) $A$ 에서 $A$ 의 어떤 진부분집합으로의 전단사함수가 존재한다.
(3) $A$ 는 무한하다.

Proof.

($1\Rightarrow 2$) 단사함수 $f:\mathbb{N}\to A$ 에 대해 $f$ 의 치역을 $B$ 라고 하고 $f(n)=b_n$ 이라고 표기하자. $f$ 는 단사이므로 $n\neq m$ 이면 $b_n\neq b_m$ 이다. 함수 $g:A\to A\setminus\{a_1\}$ 을 다음과 같이 정의하자.

$$\forall n\in\mathbb{N},\;g(b_n)=b_{n+1}$$

$$g(x)=x\quad\text{for }x\in A\setminus B$$

함수 $g$ 는 $A$ 에서 각 점 $f(n)$ 은 $f(n+1)$ 로 옮기고, 그 외의 점은 제자리로 옮기는 함수이다. 이는 자명하게 전단사이므로 원하는 결과를 얻는다.

($2\Rightarrow 3$) 따름정리 1.3.에 따라, $B$ 가 유한하면 $B$ 에서 $B$ 의 진부분집합으로의 전단사함수는 존재하지 않는다. 이의 대우를 취하면 원하는 결과를 얻는다.

($3\Rightarrow 1$) 귀납적으로 단사함수 $f:\mathbb{N}\to A$ 를 구성하자. 우선 $A$ 는 공집합이 아니므로 $A$ 의 어떤 원소 $a_1$ 을 택하여 $f(1)=a_1$ 이라고 할 수 있다. 이제 $f(1),\ldots,f(n-1)$ 이 정의되었다고 가정하고 $f(n)$ 을 정의하자. 집합 $A$ 는 무한하므로 유한집합 $h(\{1,\ldots,n-1\})$ 에 속할 수 없으며, 따라서 $A\setminus h(\{1,\ldots,n-1\})$ 는 공집합이 아니다. 그러므로 이 집합의 어떤 원소 $a_n$ 을 택하여 $f(n)=a_n$ 이라고 할 수 있다. 귀납법에 따라 $f$ 는 모든 $n\in\mathbb{N}$ 에 대하여 정의된다.

$f$ 가 단사임을 보이는 것은 쉽다. $m<n$ 에 대하여 $f(m)$ 은 $f(\{1,\ldots,n-1\})$ 에 속하고, 정의에 따라 $f(n)$ 은 속하지 않으므로 $f(m)\neq f(n)$ 을 얻는다. $\square$

읽어주셔서 감사합니다.

References)

[1] James R. Munkres. (2000). Topology. Pearson College Div.