[집합론] 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 저, 이흥천 옮김, 경문사