[집합론] 11. 가부번집합과 비가부번집합(2. 가부번집합의 성질, 비가부번집합)

[집합론] 11. 가부번집합과 비가부번집합(2. 가부번집합의 성질, 비가부번집합)

가부번집합의 성질

임의의 가부번집합 \(A,\,B\)에 대한 \(A\cup B\)도 가부번집합이다.

증명: 

(1) \(A\cap B=\phi\)일 때 

\(A\,\sim\,\mathbb{N}\), \(\mathbb{N}\,\sim\,\mathbb{N}_{o}\)이므로 \(A\,\sim\,\mathbb{N}_{o}\)이고 마찬가지로 \(B\,\sim\,\mathbb{N}\), \(\mathbb{N}\,\sim\,\mathbb{N}_{e}\)이므로 \(B\,\sim\,\mathbb{N}_{e}\)이다. 그러면 \(A\cup B\,\sim\,\mathbb{N}_{e}\cup\mathbb{N}_{o}\)이고 \(\mathbb{N}_{e}\cup\mathbb{N}_{o}=\mathbb{N}\)이므로 \(A\cup B\,\sim\,\mathbb{N}\)이 되고 따라서 \(A\cup B\)는 가부번집합이다. 

(2) \(A\cap B\neq\phi\)일 때  

\(C=B-A\)라고 하면 \(A\cup C=A\cup B\), \(A\cap C=\phi\)이고 \(C\subset B\)이며 \(C\)는 유한집합 또는 가부번집합이다. 

집합 \(C\)가 유한집합이면 \(A\cup C\)는 가부번집합이고, \(C\)가 가부번집합이면 (1)에 의해 \(A\cup C\)는 가부번집합이고 따라서 \(A\cup B\)도 가부번집합이다. 

 

따름정리: \(n\)개의 가부번집합 \(A_{1},\,A_{2},\,\cdots,\,A_{k},\,\cdots,\,A_{n}\)에 대한 \(\displaystyle\bigcup_{k=1}^{n}{A_{k}}\)도 가부번집합이다. 이 정리의 증명은 수학적귀납법으로 보일 수 있다.

예: 위의 따름정리로부터 정수의 집합은 가부번집합이다.(정수는 양의 정수(자연수)와 0, 음의정수의 합집합이다)  

집합 \(\mathbb{N}\times\mathbb{N}\)은 가부번집합이다. 

증명: 함수 \(f:\,\mathbb{N}\times\mathbb{N}\,\rightarrow\,\mathbb{N}\)를 각 \((j,\,k)\in\mathbb{N}\times\mathbb{N}\)에 대하여 \(f(j,\,k)=2^{j}3^{k}\)로 정의하면 \(f\)는 단사이다. 그러므로 \(\mathbb{N}\times\mathbb{N}\,\sim\,f[\mathbb{N}\times\mathbb{N}]\)이고 \(f[\mathbb{N}\times\mathbb{N}]\subset\mathbb{N}\)이다. 한편 \(\mathbb{N}\times\mathbb{N}\)은 무한집합이므로 \(f[\mathbb{N}\times\mathbb{N}]\)도 무한집합이고, 가부번집합이므로 \(\mathbb{N}\times\mathbb{N}\)도 가부번집합이다.  

따름정리: 각 \(k\in\mathbb{N}\)에 대한 \(A_{k}\)는 가부번집합으로서 모든 \(j,\,k\in\mathbb{N}\)에 대하여 \(A_{j}\cap A_{k}=\phi\,(j\neq k)\)이면 \(\displaystyle\bigcup_{k\in\mathbb{N}}{A_{k}}\)는 가부번집합이다. 

증명: 각 \(k\in\mathbb{N}\)에 대한 함수 \(f_{k}:\,\mathbb{N}\,\rightarrow\,\mathbb{N}\times\{k\}\)를 \(\forall j\in\mathbb{N},\,f_{k}(j)=(j,\,k)\)로 정의하면 이 함수는 일대일대응이다.

즉 \(\mathbb{N}\,\sim\,\mathbb{N}\times\{k\}\). 여기서 각 \(k\in\mathbb{N}\)에 대하여 \(A_{k}\,\sim\,\mathbb{N}\), \(\mathbb{N}\,\sim\,\mathbb{N}\times\{k\}\)이므로 \(A_{k}\,\sim\,\mathbb{N}\times\{k\}\)이고 따라서 \(\displaystyle\bigcup_{k\in\mathbb{N}}{A_{k}}\,\sim\,\bigcup_{k\in\mathbb{N}}{\mathbb{N}\times\{k\}}\)이다. \(\displaystyle\bigcup_{k\in\mathbb{N}}{\mathbb{N}\times\{k\}}\)는 가부번집합 \(\mathbb{N}\times\mathbb{N}\)과 대등하므로 \(\displaystyle\bigcup_{k\in\mathbb{N}}{A_{k}}\)는 가부번집합이다.  

 

유리수의 집합 \(\mathbb{Q}\)는 가부번집합이다. 

증명: 각 유리수를 \(\displaystyle\frac{p}{q}\)의 형태로 나타내는데 여기서 \(p\in\mathbb{Z}\), \(q\in\mathbb{N}\)이고 \(\text{gcd}(p,\,q)=1\)(\(p\)와 \(q\)의 최대공약수는 1)이다.$$\mathbb{Q}_{+}=\left\{\frac{p}{q}\,|\,\frac{p}{q}>0\right\},\mathbb{Q}_{-}=\left\{-\frac{p}{q}\,|\,\frac{p}{q}\in\mathbb{Q}_{+}\right\}$$로 각각 놓으면 \(\mathbb{Q}=\mathbb{Q}_{+}\cup\{0\}\cup\mathbb{Q}_{-}\)이고 이때 \(\mathbb{Q}_{+}\,\sim\,\mathbb{Q}\)이다. 그러므로 \(\mathbb{Q}\)가 가부번집합임을 보이기 위해서는 \(\mathbb{Q}\)가 가부번집합임을 보이면 된다.

여기서 함수 \(f:\,\mathbb{Q}_{+}\,\rightarrow\,\mathbb{N}\times\mathbb{N}\)를 \(\displaystyle f\left(\frac{p}{q}\right)=(p,\,q)\)로 정의하면 이 함수는 단사이므로 \(\mathbb{Q}_{+}\,\rightarrow\,f[\mathbb{Q_{+}}]\)이고 \(f[\mathbb{Q}_{+}]\subset\mathbb{N}\times\mathbb{N}\)이다. 또한 \(\mathbb{Q}_{+}\)는 \(\mathbb{N}\)의 초집합이므로 무한집합이다. 그러므로 \(f[\mathbb{Q}_{+}]\)는 가부번집합 \(\mathbb{N}\times\mathbb{N}\)의 무한부분집합이므로 가부번집합이고 따라서 \(\mathbb{Q}_{+}\)는 가부번집합이다.  

임의의 무한집합에 대하여 그 부분집합으로서 가부번집합인 것이 존재한다. 

증명: 임의의 무한집합을 \(X(\neq\phi)\)라고 놓고, 여기서 하나의 원소 \(x_{1}\)을 선택한다. 다음으로 집합 \(X-\{x_{1}\}\)에서 선택한 하나의 원소를 \(x_{2}\)라고 한다. 마찬가지로 집합 \(X-\{x_{1},\,x_{2}\}\)에서 하나의 원소 \(x_{3}\)을 선택한다. 이와같이 원소 \(x_{k-1}\)를 정한 다음 집합 \(X-\{x_{1},\,x_{2},\,\cdots,\,x_{k-1}\}\)의 원소 하나를 \(x_{k}\)라 하면 각 \(k\in\mathbb{N}\)에 대한 \(x_{k}\)가 존재한다. 이때 집합 \(\{x_{k}\,|\,k\in\mathbb{N}\}\)은 \(X\)의 부분집합으로서 가부번집합이다.  

비가부번집합

수직선에서 열린단위구간 \((0,\,1)\)은 무한집합으로서 비가부번집합이다. 

증명: 먼저 \(x\in(0,\,1)\)을 소수 \(0.x_{1}x_{2}x_{3}\cdots\,(x_{n}\in\{0,\,1,\,2,\,\cdots,\,9\})\)로 전개한다. 이 경우 유한소수로 전개된 수도 무한소수 한 가지로 나타내기 위해 유한소수의 마지막 숫자에서 1을 줄이고 숫자 9를 따라 적도록 한다.(예: 0.25를 0.25000....이 아닌 0.24999....으로 나타낸다)

이러한 약속하에 구간 \((0,\,1)\)의 두 수가 같을 필요충분조건은 각각의 소수전개에 있어서 대응하는 숫자들이 같은 것이다. 그러므로 \(0.x_{1}x_{2}x_{3}\cdots\), \(0.y_{1}y_{2}y_{3}\cdots\)에 대하여 소수점 아래 \(k\)째 자리에서 \(x_{k}\neq y_{k}\)이면 \(x\neq y\)이다. 

\((0,\,1)\)이 가부번집합이라고 하면 일대일대응 \(f:\,\mathbb{N}\,\rightarrow\,(0,\,1)\)이 존재하여 \((0,\,1)\)의 모든 원소를 다음과 같이 나열할 수 있다.$$\begin{align*}f(1)&=0.a_{11}a_{12}a_{13}\cdots\\f(2)&=0.a_{21}a_{22}a_{23}\cdots\\f(3)&=0.a_{31}a_{32}a_{33}\cdots\\ \vdots\\f(k)&=0.a_{k1}a_{k2}a_{k3}\cdots\\ \vdots\\(a_{jk}&\in\{0,\,1,\,2,\,\cdots,\,9\})\end{align*}$$위와 같이 나열된 \(f(k)\)들 중 어느 것과도 다른 하나의 수 \(z\in(0,\,1)\)을 다음과 같이 구성한다.

각 \(k\in\mathbb{N}\)에 대하여 \(a_{kk}\neq5\)이면 \(z_{k}=5\), \(a_{kk}=5\)이면 \(z_{k}=1\).

그러면 \(z=0.z_{1}z_{2}z_{3}\cdots\)는 \(0<z<1\)이므로 \(z\in(0,\,1)\)이고 \(z_{1}\neq a_{11}\)이므로 \(z\neq f(1)\)이다. 여기서 가정에 따라 \(f[\mathbb{N}]=(0,\,1)\)이므로 \(z\notin(0,\,1)\)이 되는데 이것은 \(z\in(0,\,1)\)에 모순이다.     

 

따름정리: 실수 전체의 집합 \(\mathbb{R}\)은 무한집합으로서 비가부번집합이다. 그 이유는 다음의 함수에 의해 \((0,\,1)\)과 \(\mathbb{R}\)이 대등하기 때문이다.$$f(x)=\tan\left(\frac{2x-1}{2}\pi\right)$$ 

예: 무리수의 집합 \(\mathbb{R}-\mathbb{Q}\)는 무한집합으로서 비가부번집합이다.

증명: \(\mathbb{R}-\mathbb{Q}\)를 가부번집합이라고 하자. \(\mathbb{Q}\)는 가부번집합이므로 \((\mathbb{R}-\mathbb{Q})\cup\mathbb{Q}=\mathbb{R}\)이 되고 \(\mathbb{R}\)은 가부번집합이어야 하나 이것은 앞의 따름정리에 의해 모순이다. 따라서 \(\mathbb{R}-\mathbb{Q}\)는 비가부번집합이다.

참고자료:  

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