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