[집합론] 10. 가부번집합과 비가부번집합(1. 유한집합, 무한집합, 집합의 대등)

[집합론] 10. 가부번집합과 비가부번집합(1. 유한집합, 무한집합, 집합의 대등)

유한집합과 무한집합

유한집합은 말 그대로 집합의 개수가 유한한 집합이고, 무한집합은 유한집합과 반대로 집합의 개수가 유한개가 아닌 집합이다. 다음은 무한집합의 수학적 정의이다.

주어진 집합 $X(\neq\phi)$에 대하여 그 진부분집합 $Y$가 존재해서 $X$와 $Y$ 사이의 일대일대응이 존재하면 $X$를 무한집합(infinite set)이라고 하고 무한집합이 아닌 집합을 유한집합(finite set) 이라고 한다. 

다시 말하면 집합 $X$에 대해 $X$가 무한집합일 필요충분조건은 단사 $f:\,X\,\rightarrow\,X$가 존재해서 $f[X]$가 $X$의 부분집합인 것이다.       

예: 공집합 $\phi$와 한원소집합($\{a\}$)는 유한집합이고, 자연수 전체의 집합 $\mathbb{N}$은 무한집합이다. 그 이유는 공집합의 경우 진부분집합이 존재하지 않고, $\{a\}$의 진부분집합은 공집합뿐이지만 $\{a\}$와 $\phi$는 일대일로 대응시킬 수 없기 때문에 $\phi$와 $\{a\}$는 유한집합인 반면 $\mathbb{N}_{e}$, $\mathbb{N}_{o}$를 각각 짝수 자연수, 홀수 자연수 전체의 집합이라고 하면 이들은 자연수 전체집합 $\mathbb{N}$의 부분집합이고 다음과 같이 정의되는 함수 $f:\,\mathbb{N}\,\rightarrow\,\mathbb{N}_{e}$, $g:\,\mathbb{N}\,\rightarrow\,\mathbb{N}_{o}$는 일대일대응이므로 $$f(n)=2n,\,g(n)=2n-1$$ 자연수 $\mathbb{N}$은 무한집합이다. 

(a) 임의의 무한집합의 초집합은 무한집합이다.

(b) 임의의 유한집합의 부분집합은 유한집합이다.

증명:

(a): 임의의 무한집합을 $X$라 하고 그 초집합을 $Y$($X\subset Y$)라고 하자. 무한집합의 정의에 의해 단사 $f:\,X\,\rightarrow\,X$가 존재해서 $f[X]\neq X$이다. 함수 $g:\,Y\,\rightarrow\,Y$를 $$g(y)=\begin{cases}f(y),\,&(y\in X)\\ y,\,&(y\in Y-X)\end{cases}$$ 로 정의하면 이 함수는 단사이고 $g[Y]\neq Y$이므로 따라서 $Y$는 무한집합이다.

(b): 임의의 유한집합을 $Y$라 하고 그 부분집합을 $X$라고 하자. $X$를 무한집합이라고 하면 (a)에 의해 $Y$는 무한집합이어야 하나 이것은 $Y$가 유한집합이라는 가정에 모순이다. 따라서 $X$는 유한집합이다. 

일대일대응 $g:\,X\,\rightarrow\,Y$에 대하여 정의역 $X$가 무한집합이면 공역 $Y$도 무한집합이다.

증명: $X$는 무한집합이므로 무한집합의 정의에 의해 단사 $f:\,X\,\rightarrow\,X$가 존재해서 $f[X]\neq X$이다. 가정에 의해 $g:\,X\,\rightarrow\,Y$는 일대일대응이므로 그 역함수 $g^{-1}:\,Y\,\rightarrow\,X$도 일대일대응이다. 그러면 함수 $h=g\circ f\circ g^{-1}$로 정의되는 함수 $h:\,Y\,\rightarrow\,Y$도 단사이고 $$h[Y]=(g\circ f\circ g^{-1})[Y]=(g\circ f)[g^{-1}[Y]]=(g\circ f)[X]=g[f[X]]$$ 이며 $f[X]\neq X$이므로 $g[f[X]]\neq Y$이다. 따라서 $h[Y]\neq Y$이고 이것은 $h[Y]$가 $Y$의 진부분집합임을 뜻하므로 무한집합의 정의에 의해 $Y$는 무한집합이다. 

위의 정리에서 정의역 $X$가 유한집합이면 공역 $Y$도 무한집합이다.

무한집합 $X$의 임의의 원소 $x_{0}$에 대하여 $X-\{x_{0}\}$은 무한집합이다.

증명: 무한집합의 정의에 의해 단사 $f:\,X\,\rightarrow\,X$가 존재해서 $f[X]\subset X$이다.

1. $x_{0}\in f[X]$

적당한 $x_{1}\in X$가 존재해서 $f(x_{1})=x_{0}$이고 함수 $g:\,X-\{x_{0}\}\,\rightarrow\,X-\{x_{0}\}$를 다음과 같이 정의한다. $$g(x)=\begin{cases}f(x),\,&(x\neq x_{1})\\x_{2},\,&(x=x_{1}\in X-\{x_{0}\})\end{cases}$$ 여기서 $x_{2}$는 집합 $X-f[X](\neq\phi)$의 임의로 고정된 원소이다. 그러면 함수 $g$는 단사이고 $$g[X-\{x_{0}\}]=f[X-\{x_{0},\,x_{1}\}]\cup\{x_{2}\}\neq X-\{x_{0}\}$$ 이므로 $X-\{x_{0}\}$는 무한집합이다.  

2. $x_{0}\in X-f[X]$

함수 $g:\,X-\{x_{0}\}\,\rightarrow\,X-\{x_{0}\}$를 다음과 같이 정의한다. $$\forall x\in\{X-\{x_{0}\}\},\,g(x)=f(x)$$ 여기서 $f:\,X\,\rightarrow\,X$가 단사이므로 $g:\,X-\{x_{0}\}\,\rightarrow\,X-\{x_{0}\}$도 단사이다. $$g[X-\{x_{0}\}]=f[X]-\{x_{0}\}\neq X-\{x_{0}\}$$ 이므로 $X-\{x_{0}\}$은 무한집합이다.

위의 결과로부터 어느 경우에도 $X-\{x_{0}\}$는 무한집합이다.   

예: 각 $k\in\mathbb{N}$에 대하여 $\mathbb{N}_{k}=\{1,\,2,\,3,\,\cdots,\,k\}$는 유한집합이다.

증명: 수학적귀납법으로 증명한다.

$k=1$이면 분명히 참이다. 적당한 $k\in\mathbb{N}$에 대하여 $\mathbb{N}_{k}$를 유한집합이라 하자. $\mathbb{N}_{k+1}=\mathbb{N}_{k}\cup\{k+1\}$이 무한집합이면 $\mathbb{N}_{k}=\mathbb{N}_{k+1}-\{k+1\}$도 무한집합이 되는데 이것은 $\mathbb{N}_{k}$가 유한집합이라는 가정에 모순이다. 그러므로 $\mathbb{N}_{k}$가 유한집합이면 $\mathbb{N}_{k+1}$도 유한집합이다. 따라서 수학적귀납법에 의해 각 $k\in\mathbb{N}$에 대한 $\mathbb{N}_{k}$는 유한집합이다.

 

유한집합을 다음과 같이 정의할 수 있다. 

집합 $X$가 유한집합일 필요충분조건은 $X=\phi$이거나 $X$와 $\mathbb{N}_{k}$ 사이에 일대일대응이 존재하는 것이다.    

집합의 대등 

두 집합 $X,\,Y$에 대해 일대일대응 $f:\,X\,\rightarrow\,Y$가 존재하면 $X$와 $Y$는 대등(equipotent)하다고 하고 $X\,\sim\,Y$로 나타낸다. 

예: $f:\,X\,\sim\,Y\wedge g:\,Y\,\sim\,Z\,\Rightarrow\,g\circ f:\,X\,\sim\,Z$

*$f:\,X\,\rightarrow\,Y$는 "$f:\,X\,\rightarrow\,Y$는 일대일대응이므로 $X\,\rightarrow\,Y$"를 뜻한다. 

집합족 $\mathcal{P}$에서의 관계 $\mathcal{R}$을 다음과 같이 정의하자.

$\mathcal{P}$의 임의의 원소 $X,\,Y$에 대하여 $$X\,\sim\,Y\,\Leftrightarrow\,X\mathcal{R}Y$$ 여기서 $\mathcal{R}$은 $\mathcal{P}$에서 동치관계이다.(증명생략)   

예: 실수 상의 두 함수 $f(x)=2x-1$, $\displaystyle g(x)=\tan\left(\frac{\pi}{2}x\right)$로부터 구간 $(0,\,1)$은 $(-1,\,1)$과 대등하고 즉, $(0,\,1)\,\sim\,(-1,\,1)$, 구간 $(-1,\,1)$은 실수 전체 $\mathbb{R}$과 대등하다 즉, $(-1,\,1)\,\sim\,\mathbb{R}$. 

더 나아가서 $(0,\,1)\,\sim\,\mathbb{R}$이다.  

 

집합 $X,\,Y,\,Z,\,W$에 대하여 $X\cap Z=\phi$, $Y\cap W=\phi$, $f:\,X\,\sim\,Y\wedge g:\,Z\,\sim\,W$이면 $f\cup g:\,X\cup Z\,\rightarrow\,Y\cup W$가 성립한다.  

증명: 두 함수 $f:\,X\,\rightarrow\,Y$, $g:\,Z\,\rightarrow\,W$에 대하여 $X\cap Z=\phi$이므로 $f\cup g:\,X\cup Z\,\rightarrow\,Y\cup W$이다. 

집합 $X,\,Y,\,Z,\,W$에 대하여 $X\,\sim\,Y$, $Z\,\sim\,W$이면, $X\times Z\,\sim\,Y\times W$가 성립한다. 

증명: $f:\,X\,\sim\,Y$, $g:\,Z\,\sim\,W$라 놓고 각 $(x,\,z)\in X\times Z$에 대하여 $(f\times g)(x,\,z)=(f(x),\,g(z))$로 정의된 함수 $f\times g:\,X\times Z\,\rightarrow\,Y\times W$는 일대일대응이다.

집합 $X$에 대하여 $X\,\sim\,\mathbb{N}$일 때 $X$를 가부번집합(번호를 붙일 수 있는 집합, denumberable)이라 하고 유한집합 또는 가부번집합 어느것이나 가산집합(countable)이라고 한다. 

집합 $X$가 가부번집합이면 일대일대응 $f:\,\mathbb{N}\,\rightarrow\,X$가 존재한다. 

임의의 가부번집합의 부분집합으로서 무한집합인 것도 가부번집합이다.(증명생략) 

위의 정리로부터 가산집합의 임의의 부분집합도 가산집합이 됨을 알 수 있다.

참고자료: 

집합론, You-Feng Lin. Shwu-Yeng T. Lin 저, 이흥천 옮김, 경문사