가산집합(Countable set)

정의1

자연수 집합 $\mathbb{N} = \{ 0,1,2,\cdots \}$에서 $S$로의 전단사함수가 존재할때

집합 $S$를 가부번(denumerable) 또는 가산 무한으로 정의한다.

 

집합 $S$가 유한이거나 가부번이면 $S$를 가산이라 정의한다.

$S$가 가산이 아니면 $S$를 비가산이라 정의한다.

 

 

 

정리9

다음이 성립한다.

1. 집합 $S$가 가부번이기 위한 필요충분조건은 $S$에서 $\mathbb{N}$으로의 전단사함수가 존재하는 것이다.

2. 집합 $S_{1}$이 가부번이기 위한 필요충분조건은 $S_{1}$에서 가부번인 집합 $S_{2}$로의 전단사함수가 존재하는 것이다.

3. 무한인 가산집합은 가부번이다.

증명

1.

집합 $S$가 가부번이면 전단사함수 $f : \mathbb{N} \to S$가 존재하므로

함수 정리로 $f$의 역함수 $f^{-1} : S\to \mathbb{N}$가 존재하고 전단사이다.

역으로 전단사함수 $g : S\to \mathbb{N}$가 존재하면

함수 정리로 $g$의 역함수 $g^{-1} : \mathbb{N} \to S$가 존재하고 전단사이다.

2.

집합 $S_1, S_2$이 가부번이면

전단사함수 $f : \mathbb{N} \to S_1$와 $g : \mathbb{N} \to S_2$가 존재하고 함수 정리로 $f$의 역함수 $f^{-1} : S_1 \to \mathbb{N}$은 전단사이므로

합성함수 $g \circ f^{-1}  : S_1 \to S_2$는 함수 정리로 전단사이다.

역으로 $S_2$가 가부번일때 전단사함수 $f :S_{1} \to S_{2}$가 존재하면

$S_2$가 가부번이므로 전단사함수 $g : \mathbb{N} \to S_2$가 존재하고 함수 정리로 $g$의 역함수 $g^{-1} : S_2 \to \mathbb{N}$는 전단사이므로

합성함수 $g^{-1} \circ f : S_1 \to \mathbb{N}$는 함수 정리로 전단사이고 1번으로 $S_1$은 가부번이다.

3.

가산이면 유한이거나 가부번이므로 무한인 가산집합은 가부번이다.

 

 

 

정리1

자연수 집합 $\mathbb{N}$의 데카르트곱 $\mathbb{N} \times \mathbb{N}$은 가부번이다.

증명

합공식으로 모든 자연수 $k \in \mathbb{N}$에 대해

$\psi(k) = 0 +1 +2+ \cdots + k = \dfrac{1}{2}\cdot k\cdot (k+1)$인 함수 $\psi : \mathbb{N} \to \mathbb{N}$를 정의할때

모든 $m,n \in \mathbb{N}$에 대해 $h(m,n) = \psi(m+n) + m$인 함수 $h : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$가 단사임을 보인다.

$(m_1,n_1) \ne (m_2,n_2)$인 $(m_1,n_1) , (m_2,n_2) \in \mathbb{N} \times \mathbb{N}$는 $m_1 \ne m_2$ 또는 $n_1 \ne n_2$ 중 하나가 성립하므로

$m_1+n_1 \ne {m_2}+{n_2}$가 성립하거나

$m_1+n_1={m_2}+{n_2}$일때 $m_1 \ne {m_2}$가 성립한다.

 

$m_1+n_1 \ne {m_2}+{n_2}$일때 일반성을 잃지 않고 $m_1+n_1 < {m_2}+{n_2}$라고 가정하면

$m_1+n_1 +1 \le {m_2}+{n_2}$이고

$\psi(m_1+n_1 +1) = \dfrac{1}{2}\cdot (m_1+n_1+1 ) \cdot (m_{1}+n_1+2) \le \dfrac{1}{2}\cdot (m_{2}+n_2 ) \cdot (m_{2}+n_2+1) = \psi(m_2+n_2)$이므로

$\begin{align*} h(m_1,n_1) &= \psi(m_1+n_1)+m_1 \\[0.5em] & <  \psi(m_1+n_1)+ m_1+(n_1+1) \\[0.5em] & \qquad = \frac{1}{2}\cdot (m_1+n_1) \cdot (m_1+n_1 +1)+ (m_1+n_1 +1) \\[0.5em] & \qquad =  (m_1+n_1+1)\cdot \left (\frac{1}{2} \cdot (m_1+n_1)+1 \right ) \\[0.5em]   & \qquad = \frac{1}{2}\cdot (m_1+n_1+1) \cdot (m_1+n_1+2) \\[0.5em]  & \qquad = \psi(m_1+n_1+1) \\[0.5em] & \le  \psi({m_2} + {n_2} ) = h({m_2},{n_2})  \text{   가 되어} \end{align*}$

$h(m_1,n_1) \ne h({m_2},{n_2}) $이다.

 

$m_1+n_1={m_2}+{n_2}$이고 $m_1 \ne {m_2}$이면

$h(m_1,n_1) -m_1 = \psi(m_1+n_1) = \psi({m_2}+{n_2}) = h({m_2},{n_2})-{m_2}$이므로

$ h(m_1,n_1) - h({m_2},{n_2})  = m_1 - {m_2} \ne 0 $으로 $h(m_1,n_1) \ne h({m_2},{n_2}) $가 되어 $h$는 단사이다.

 

$p \ge 1$인 모든 $p \in \mathbb{N}$에 대해

$p < \psi(p+1) = 0+1  +\cdots + p + (p+1)$이므로 집합 $E_{p} = \left \{k\in \mathbb{N}  :  p < \psi(k) \right \} $는 공집합이 아니고

$E_p \subseteq \mathbb{N}$이므로 정렬성에 의해 $k_{p} \ge 1$인 최소 원소 $k_p \in E_p$가 존재하여

$k_p - 1 \notin E_p$이므로 $\psi(k_{p}-1) \le p < \psi(k_{p}) = \psi(k_{p}-1)+k_{p}$이고

$0 = \psi(k_p -1) - \psi(k_p - 1) \le  p -\psi(k_{p}-1) \le \psi(k_p -1) + k_p  - \psi(k_p- 1) -1 = k_p -1$이다.

$m_{p} = p -\psi(k_{p}-1) $이면 $0\le m_{p} \le k_{p}-1$이고

$-k_p=-k_p +1 -1\le -m_p -1 \le -1$이므로 $0 = k_p - k_p   \le k_p- m_p-1 \le k_p-1$이 되어

$n_{p} = k_{p} - m_{p} -1 $이면 $0\le n_{p} \le k_{p} -1$이다.

따라서 $p \ge 1$일때 모든 $p \in \mathbb{N}$에 대해

$\begin{align*} h(m_{p},n_{p}) & = \psi(m_p + n_p) + m_p \\[0.5em] & = \frac{1}{2}\cdot (m_p + n_p ) \cdot  (m_p + n_p +1) +m_p \\[0.5em] &= \frac{1}{2}\cdot (m_p + k_p - m_p-1  ) \cdot (m_p + k_p - m_p-1 +1   ) + m_p\\[0.5em] & = \frac{1}{2}\cdot (k_p-1) \cdot k_p  + p - \psi(k_p -1) \\[0.5em] & = \psi(k_p -1) + p - \psi(k_p-1 ) \\[0.5em] & =p \text{ 인}\end{align*}$

$(m_{p},n_{p}) \in \mathbb{N} \times \mathbb{N}$가 존재하고

$0 \in \mathbb{N}$에 대해 $h(0,0) = \psi(0+0) + 0 = 0$인 $(0,0) \in \mathbb{N}\times \mathbb{N}$이 존재하여 $h$는 전사이므로

$h : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$는 전단사이고 위 정리로 $\mathbb{N} \times \mathbb{N}$은 가부번이다.

 

 

 

정리2

무한집합 $A$가 자연수 집합 $\mathbb{N}$의 부분집합이 $A \subseteq \mathbb{N}$일때

모든 $n \in \mathbb{N}$에 대해 $\varphi(n+1) > \varphi(n) \ge n$인 전단사함수 $\varphi :\mathbb{N} \to A$가 유일하게 존재하여 $A$는 가부번이다.

증명

존재성

$A$가 무한이므로 $A \ne \emptyset$이고 $A \subseteq \mathbb{N}$이므로 정렬성에 의해 최소 원소가 존재한다.

$\varphi(0) = \min A$로 정의할때 임의의 $n \in \mathbb{N}$에 대해 $\varphi(0), \varphi(1), \cdots, \varphi(n) $이 정의되어 있으면

$A_{n} = A \setminus \left \{ \varphi(0), \varphi(1), \cdots, \varphi(n) \right \}$은 무한집합 정리로 무한이므로 $A_n \ne \emptyset$이고 $A_n \subseteq \mathbb{N}$이 되어

$\varphi(n+1) = \min A_n$형태로 강귀납적으로 함수 $\varphi : \mathbb{N} \to A$를 정의한다.

$\varphi(n+1) = \varphi(n)$인 $n \in \mathbb{N}$이 존재하면 $\varphi(n) = \varphi(n+1) =\min A_n \in A_{n} = A\setminus \{ \varphi(0),\cdots, \varphi(n) \}$이므로

모순이 되어 모든 $n \in \mathbb{N}$에 대해 $\varphi(n+1) \ne \varphi(n)$이다.

또 $n\ge 1$일때 $\varphi(n+1),\varphi(n) = \min A_{n-1} \in A_{n-1} = A \setminus \{ \varphi(0),\cdots ,\varphi(n-1) \}$이므로

$\varphi(n+1) < \varphi(n)$이면 $\varphi(n)$이 최소라는 가정에 모순이 되어 $\varphi(n+1) > \varphi(n)$이다.

비슷하게 $\varphi(1), \varphi(0) = \min A \in A$이므로 $\varphi(1) > \varphi(0)$이고 모든 $n \in \mathbb{N}$에 대해 $\varphi(n+1) > \varphi(n)$이다.

귀납법으로 모든 $n \in \mathbb{N}$에 대해 $\varphi(n) \ge n$임을 보인다.

$n = 0$이면 $\varphi(0) \in A \subseteq \mathbb{N}$이고 $\varphi(0) = 0 +\varphi(0)$이므로 자연수 부등식의 정의로 $\varphi(0) \ge 0$이다.

모든 $k \in \mathbb{N}$에 대해 $\varphi(k) \ge k$이면 

$\varphi(k+1) > \varphi(k) \ge k$이므로 $\varphi(k+1) > k$이고 자연수 부등식 정리로 $\varphi(k+1) \ge k+1$이 되어

모든 $n \in \mathbb{N}$에 대해 $\varphi(n+1) > \varphi(n) \ge n$이다.

전단사

$\varphi(n+1) > \varphi(n) > \cdots >\varphi(0) $이므로 $m>n$인 임의의 $m,n \in \mathbb{N}$에 대해 $\varphi(m) > \varphi(n)$이고 $\varphi$는 단사이다.

$\varphi : \mathbb{N} \to A$가 전사가 아니라고 가정하면 

$\varphi(\mathbb{N})$의 여집합 $A \setminus \varphi(\mathbb{N}) \subseteq \mathbb{N}$은 공집합이 아니므로 정렬성에 의해 최소 원소 $p \in A \setminus \varphi(\mathbb{N})$이 존재한다.

$p \notin \left \{ \varphi(0), \varphi(1), \cdots, \varphi(p) \right \} \subset  \varphi(\mathbb{N})$이므로 $p \in A \setminus \left \{ \varphi(0), \varphi(1), \cdots, \varphi(p) \right \} = A_{p} $이고 

$A_{p}$의 최소 원소가 $\varphi(p+ 1)$이므로 $\varphi(p+ 1) \le p$가 되어 $\varphi(p+1) > \varphi(p) \ge p$임에 모순이다.

$A \setminus \varphi(\mathbb{N})$은 공집합이고 $\varphi(\mathbb{N}) \subseteq A$이므로 집합정리로 $\varphi(\mathbb{N}) = A$가 되어 함수정리로 $\varphi$는 전사이다.

따라서 모든 $n \in \mathbb{N}$에 대해 $\varphi(n+1) > \varphi(n) \ge n$인 전단사함수 $\varphi :\mathbb{N} \to A$가 존재한다.

유일성

모든 $n \in \mathbb{N}$에 대해 $f(n+1) > f(n) \ge n$인 전단사함수 $f : \mathbb{N} \to A$가 존재할때

강귀납법으로 모든 $n \in \mathbb{N}$에 대해 $f(n) = \varphi(n)$임을 보인다.

$n = 0$이면 모든 $x \in A$에 대해 $\min A \le x$이므로 $\min A \le f(0) <f(1) < \cdots  $이다.

$f(0) \ne \min A$라고 가정하면 $\min A < f(0)< f(1)< \cdots $이고 $0$보다 작은 자연수는 존재하지 않아

$f$의 값이 $\min A \in A$가 될 수 없으므로 $f$가 전사임에 모순이 되어 $f(0) = \min A = \varphi(0)$이다.

모든 $k \in \mathbb{N}$에 대해 $f(0) = \varphi(0) ,\cdots, f(k) = \varphi(k)$라고 가정하면

$f$는 단사이므로 $f(k+1) \in A_k = A \setminus \{ f(0) = \varphi(0), \cdots,  f(k) = \varphi(k) \}) $이고 $\min A_k \le f(k+1)$이다.

$\min A_k \ne f(k+1)$라고 가정하면 $\min A_k < f(k+1) < f(k+2) < \cdots$이고 $f(0), \cdots, f(k) \notin A_k$이므로

$f$의 값이 $\min A_k \in A$가 되는 자연수가 존재하지 않아 $f$가 전사임에 모순이므로

$f(k+1) = \min A_k = \varphi(k+1)$이다.

따라서 모든 $n \in \mathbb{N}$에 대해 $f(n) = \varphi(n)$이 되어 $f = \varphi$이다.

 

 

 

정리3

자연수 집합 $\mathbb{N}$의 임의의 부분집합 $A \subseteq \mathbb{N}$는 가산이다.

증명

$A$가 유한이면 정의에 의해 가산이고

$A$가 무한이면 위 정리로 전단사함수 $\varphi :\mathbb{N} \to A$가 존재하여 $A$는 가부번이다.

 

 

 

정리4

집합 $S,T$가 $T \subseteq S$일때 $S$가 가산이면 $T$도 가산이다.

증명

$S$가 유한이면 유한집합정리로 $T$도 유한이므로 가산이다.

$S$가 가부번일때 $T$가 유한이면 가산이므로 $T$가 무한이라 가정한다.

$S$가 가부번이므로 위 정리로 전단사함수 $\psi : S \to \mathbb{N}$가 존재하고

모든 $x \in T\subseteq S$에 대해 $\psi(x) = f(x)$인 함수 $f: T \to $ $\psi(T)$는 함수 정리로 전단사이다.

또 $ \psi(T) \subseteq \mathbb{N}$이므로 위 정리로 $\psi(T)$는 가산이고

$\psi(T)$가 유한이면 유한집합 정리로 $T$도 유한이 되어 가정에 모순이므로 $\psi(T)$는 무한이고 위 정리로 가부번이다.

따라서 집합 $T$에서 가부번인 집합 $\psi(T)$로의 전단사함수가 존재하므로 위 정리로 $T$는 가부번이다.

 

 

 

정리5

집합 $S,T$가 $T \subseteq S$일때 $T$가 비가산이면 $S$도 비가산이다.

증명

위 정의로 가산의 반대는 비가산이므로 위 정리의 대우로 성립한다.

 

 

 

정리6

$S \ne \emptyset$일때 다음 세 조건은 동치이다.

1. 집합 $S$는 가산이다.

2. 자연수 집합 $\mathbb{N}$에서 $S$로의 전사함수가 존재한다.

3. $S$에서 $\mathbb{N}$으로의 단사함수가 존재한다.

증명

$1 \to 2$

집합 $S$가 유한이면 $\mathbb{Z}_{n} = \left \{ 0, 1,2, \cdots, n-1 \right \}$에서 $S$로의 전단사함수 $h : \mathbb{Z}_{n} \to S$가 존재한다.

함수 $H : \mathbb{N} \to S$를 $k \in \mathbb{N}$에 대해 $H(k) = \begin{cases} h(k) & k< n \text{ 일때}  \\[0.5em] h(n-1) & n \le k \text{ 일때}  \end{cases}  $  로 정의하면 $H$는 전사함수이다.

$S$가 가부번이면 $\mathbb{N}$에서 $S$로의 전단사함수가 존재하여 $\mathbb{N}$에서 $S$로의 전사함수가 존재한다.

$2 \to 3$

$H : \mathbb{N} \to S$가 전사함수이면 모든 $s \in S$에 대해 $H(n) = s$인 $n \in \mathbb{N}$이 존재하고

집합 $ \{ n\in \mathbb{N} : H(n) = s \}$은 정렬성에 의해 최소 원소가 존재하므로

모든 $s \in S$에 대해 $G(s) = \min \left \{ n\in \mathbb{N} : H(n) = s \right \}$인 함수 $G : S \to \mathbb{N}$를 정의할 수 있다.

따라서 임의의 $s_{1}, s_{2} \in S$에 대해

$G(s_{1}) = \min \left \{ n\in \mathbb{N} : H(n) = s_{1} = s_{2} \right \} =  G(s_{2})$이면 $s_{1} = s_{2}$가 되어 $G$는 $S$에서 $\mathbb{N}$으로의 단사함수이다.

$3 \to 1$

$S$가 유한이면 가산이므로 $S$가 무한이라 가정하고

$G : S \to \mathbb{N}$가 단사이면 함수 정리로 모든 $s \in S$에 대해 $G_1(s) = G(s)$인 함수 $G_1 : S \to G(S)$은 전단사이다.

$G(S) \subseteq \mathbb{N}$은 위 정리로 가산이고

$G(S)$가 유한이면 유한집합 정리로 $S$도 유한이 되어 가정에 모순이므로 $G(S)$는 무한이고 위 정리로 가부번이다.

따라서 $S$에서 가부번인 집합 $G(S)$로의 전단사함수 $G_1$이 존재하여 위 정리로 집합 $S$는 가부번이다.

 

 

 

정리8

다음이 성립한다.

1. 임의의 $n \in $ $\mathbb{N}$에 대해 $A_{0}, A_1,A_2, \cdots, A_n$이 모두 가산이면 ${\displaystyle \bigcup_{m =0}^{n} } A_{m}$도 가산이다.

2. 모든 자연수 $m \in \mathbb{N}$에 대해 $A_{m}$이 가산이면 $A = $ ${\displaystyle \bigcup_{m=0}^{\infty} } A_{m}$도 가산이다.

증명

1.

$n \in \mathbb{N}$에 대한 귀납법을 사용한다.

$n = 0$일때는 자명하다.

모든 $k \in \mathbb{N}$에 대해 $\displaystyle \bigcup_{m =0}^{k} A_{m} $이 가산이라고 가정할때

$\displaystyle \bigcup_{m =0}^{k}  A_{m} = \emptyset$이면 집합정리로 $\displaystyle \bigcup_{m =0}^{k+1} A_{m} = \left ( \bigcup_{m = 0}^k A_m \right ) \cup A_{k+1} =A_{k+1}$은 가산이고

$A_{k+1} =\emptyset$이면 집합정리와 귀납가정으로 $\displaystyle \bigcup_{m =0}^{k+1} A_{m} = \left ( \bigcup_{m = 0}^k A_m \right ) \cup A_{k+1} = \bigcup_{m = 0}^k A_m$은 가산이다.

${\displaystyle \bigcup_{m =0}^{k} } A_{m} \ne \emptyset$이고 $A_{k+1} \ne \emptyset$이면

위 정리로 전사함수 $\displaystyle f : \mathbb{N} \to  \bigcup_{m = 0}^{k}A_m$가 존재하고 $A_{k+1}$도 가산이므로 전사함수 $g : \mathbb{N} \to  A_{k+1}$가 존재한다.

함수 $B : \mathbb{N} \times \mathbb{N} \to \displaystyle \bigcup_{m=0}^{k+1}A_m$를 $(i,j) \in \mathbb{N} \times \mathbb{N}$에 대해 $B(i,j) =  \begin{cases} \displaystyle f(j), & i = 0 \text{ 일때} \\ \displaystyle g(j) , & i \ne 0 \text{ 일때} \end{cases}$ 로 정의하면

모든 $\displaystyle a \in \bigcup_{m =0}^{k+1}  A_{m}$에 대해 

$\displaystyle a \in \bigcup_{m =0}^{k}  A_{m}$이면 $f$가 전사이므로 $B(0, j) = f(j) = a$인 $(0,j) \in \mathbb{N} \times \mathbb{N}$가 존재하고

$a \in A_{k+1}$이면 $g$가 전사이므로 $B(1, j) = g(j) = a$인 $(1,j) \in \mathbb{N} \times \mathbb{N}$가 존재하여 $B$는 전사이다.

위 정리로 $\mathbb{N} \times \mathbb{N}$이 가산이므로 위 정리로 전사함수 $h : \mathbb{N} \to \mathbb{N} \times \mathbb{N}$이 존재하고 

함수 정리로 합성함수 $B \circ h : \mathbb{N} \to \displaystyle \bigcup_{m =0}^{k+1} A_m$가 전사이므로 위 정리로 $ \displaystyle \bigcup_{m=0}^{k+1}  A_{m}$은 가산이다.

따라서 모든 $n \in \mathbb{N}$에 대해 $ \displaystyle \bigcup_{m=0}^{n} A_{m}$은 가산이다.

2.

$ A = {\displaystyle \bigcup_{m=0}^{\infty} } A_{m} = \emptyset$이면 $A$는 유한이므로 가산이다.

$ A = {\displaystyle \bigcup_{m=0}^{\infty} } A_{m} \ne \emptyset$이면 $A_{m_i} \ne \emptyset$인 $m_i \in \mathbb{N}$가 존재하므로

$ A = \displaystyle \bigcup_{m=0}^{\infty} A_{m} =\bigcup_{i = 0}^{k} A_{m_i} $인 $k \in \mathbb{N}$가 존재하면 1번으로 $A$는 가산이고

$ A = \displaystyle \bigcup_{m=0}^{\infty} A_{m} =\bigcup_{i = 0}^{k} A_{m_i} $인 $k \in \mathbb{N}$가 존재하지 않으면 $ A = \displaystyle \bigcup_{m=0}^{\infty} A_{m} =\bigcup_{i = 0}^{\infty} A_{m_i} $이다.

또 모든 $i \in \mathbb{N}$에 대해 $A_{m_i} \ne \emptyset$이고 $A_{m_i}$가 가산이므로 위 정리로 전사함수 $\varphi_{i} : \mathbb{N} \to  A_{m_i}$가 존재하여

함수 $B : \mathbb{N} \times \mathbb{N} \to A$를 $(i,n) \in \mathbb{N} \times \mathbb{N}$에 대해 $B(i,n) = \varphi_{i}(n)$으로 정의하면

모든 $a \in A$에 대해 $a \in A_{m_i}$인 $i \in \mathbb{N}$가 존재하고

$\varphi_{i}$가 전사이므로 모든 $a \in A_{m_i}$에 대해 $B(i,n) = \varphi_{i}(n) = a$인 $n \in \mathbb{N}$이 존재하여 $B$는 전사이다.

위 정리로 $\mathbb{N} \times \mathbb{N}$이 가산이므로 위 정리로 전사함수 $f : \mathbb{N} \to \mathbb{N} \times \mathbb{N}$이 존재하고 

함수 정리로 합성함수 $B \circ f : \mathbb{N} \to A$가 전사이므로 위 정리로 $ A = \displaystyle \bigcup_{m=0}^{\infty}  A_{m} = \bigcup_{i = 0}^\infty A_{m_i}$는 가산이다.

 

 

 

정리7

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

증명

임의의 $0$이 아닌 유리수 $r \in \mathbb{Q}$은 순서성질로 $r = \dfrac{p}{q}$ 또는 $r = -\dfrac{p}{q}$인 양의 정수 $p, q \in \mathbb{Z}^+$가 존재하고

유리수집합은 양의 유리수집합 $\mathbb{Q}^{+}$, 음의 유리수집합 $\mathbb{Q}^{-}$와 $\left \{0 \right \}$의 합집합 $\mathbb{Q} = \mathbb{Q}^{-} \cup \left \{0 \right \} \cup \mathbb{Q}^{+}$이다.

위 정리로 $ \mathbb{N} \times \mathbb{N}$은 가산이므로 위 정리로 전사함수 $f : \mathbb{N} \to \mathbb{N} \times \mathbb{N}$가 존재하고

모든 $m,n \in \mathbb{N}$에 대해 $g(m,n) = \dfrac{m+1}{n+1}$인 함수 $g : \mathbb{N} \times \mathbb{N} \to \mathbb{Q}^+$는

모든 $r \in \mathbb{Q}^+$에 대해 $g(p-1,q-1) = r = \dfrac{p}{q}$인 $p,q \in \mathbb{Z}^+$가 존재하므로 전사가 되어

함수 정리로 $g \circ f : \mathbb{N} \to \mathbb{Q}^+$는 전사이고 다시 위 정리로 $\mathbb{Q}^+$는 가산이다.

비슷하게 $\mathbb{Q}^-$도 가산이므로 위 정리로 $\mathbb{Q} = \mathbb{Q}^{-} \cup \left \{0 \right \} \cup \mathbb{Q}^{+}$는 가산이다.

또 $\mathbb{N} \subset \mathbb{Q}$이므로 무한집합 정리로 $\mathbb{Q}$는 무한이 되어 가부번이다.

 

 

 

정리10

집합 $A\ne \emptyset$가 가산일때 다음이 성립한다.

1. $A$의 모든 유한인 부분집합들의 집합은 가산이다.

2. 크기가 유한인 모든 $A$의 배열들의 집합은 가산이다.

증명

1.

$A$가 가산이면

위 정리로 단사함수 $f : A \to \mathbb{N}$가 존재하고 함수 정리로 $f$의 정의역을 임의로 축소한 함수는 단사이므로

유한인 임의의 부분집합 $B \subseteq A$에 대해

$B$가 공집합이면 $f(B)$도 공집합이고 $B$가 공집합이 아니면 함수 정리로 $f(B)$는 원소개수가 $B$와 같은 유한집합이다.

$A$의 모든 유한인 부분집합들의 집합 $\mathcal{F}$이고 소수가 $p_0 = 2, p_1 = 3, p_2 = 5,p_3 = 7 ,\cdots$일때

임의의 $B \in \mathcal{F}$에 대해 $B$가 공집합이면 $g(B) = 0$이고

$B$가 공집합이 아니면 모든 $n \in f(B)$에 대해 소수 $p_n$들의 곱 $\displaystyle g(B) = \prod_{n \in f(B)}p_n$인 함수 $g : \mathcal{F} \to  \mathbb{N}$는

모든 $B_1,B_2 \in \mathcal{F}$에 대해 $g(B_1) = g(B_2)$일때

$g(B_1) = g(B_2)$가 $0$이면 $B_1,B_2$는 공집합이므로 $B_1 =  B_2$이고

$g(B_1) = g(B_2)$가 $0$이 아니면 $B_1,B_2$는 공집합이 아니므로 $f(B_1),f(B_2)$는 원소개수가 $1$개 이상이고

$\displaystyle g(B_1) = \prod_{n \in f(B_1)}p_n  = \prod_{n\in f(B_2)} p_n = g(B_2)$이므로 산술의 기본정리로 $f(B_1) = f(B_2)$가 되어

$f$가 단사임에 따라 함수 정리로 $B_1=f^{-1}(f(B_1)) = f^{-1}(f(B_2)) = B_2$이다.

따라서 $g$는 단사이므로 위 정리로 $A$의 모든 유한인 부분집합들의 집합 $\mathcal{F}$는 가산이다.

2.

$A$가 가산이면 위 정리로 단사함수 $f : A \to \mathbb{N}$가 존재하고 크기가 유한인 모든 $A$의 배열들의 집합이 $\mathcal{S}$일때

임의의 $a \in \mathcal{S}$는 배열의 크기 $k \in \mathbb{N}$가 $0$이 아니면 $a(0),a(1),\cdots , a(k-1) \in A$이다.

$k = 0$이면 $h(a) = 0$이고

$k \ge 1$이면 소수 $p_0 = 2, p_1 = 3, p_2 = 5,p_3 = 7 ,\cdots$에 대해 $h(a) = p_0^{f(a(0))}\cdot p_1^{f(a(1))}\cdot \; \cdots \; \cdot p_{k-1}^{f(a(k-1))}$인

함수 $h : \mathcal{S} \to \mathbb{N}$는 모든 $a,b \in \mathcal{S}$에 대해 $h(a) = h(b)$일때

$h(a) = h(b)$가 $0$이면 $a,b$는 빈 배열이므로 공함수이고 공함수 정리로 공함수는 유일하므로 $a = b$이다.

$h(a) = h(b)$가 $0$이 아닐때 산술의 기본정리로 $a,b$의 크기는 $k\ge 1$로 동일하고

$h(a) = p_0^{f(a(0))}\cdot p_1^{f(a(1))}\cdot \; \cdots \; \cdot p_{k-1}^{f(a(k-1))} = p_0^{f(b(0))}\cdot p_1^{f(b(1))}\cdot \; \cdots \; \cdot p_{k-1}^{f(b(k-1))} = h(b)$이므로

$f(a(0)) = f(b(0)),f(a(1)) = f(b(1)),\cdots , f(a(k-1))=f(b(k-1)) $가 되어

$f$가 단사임에 따라 $a(0) =b(0),a(1) = b(1),\cdots , a(k-1)=b(k-1) $이고 함수의 상등으로 $a = b$이다.

따라서 $h$는 단사가 되어 위 정리로 크기가 유한인 모든 $A$의 배열들의 집합 $\mathcal{S}$는 가산이다.

 

 

 

정리11

집합 $X$가 비가산이면 $A $ $\subset$ $ X$이고 가부번인 집합 $A$가 존재한다.

증명

$X$는 비가산이므로 $X \ne \emptyset$이 되어 선택정리로 임의의 $x \in X$를 선택할때

$X$는 무한이므로 무한집합 정리로 $X \setminus \{ x\}$는 무한이 되어 다시 선택정리로 $x_0 \in X \setminus \{ x\}$을 선택할 수 있다.

모든 $n \in \mathbb{N}$에 대해 $x_0,x_1,\cdots,x_n \in X\setminus \{ x\}$이 강귀납적으로 정의되면

$X$는 무한이므로 무한집합 정리로 $X \setminus \{ x, x_0,x_1,\cdots,x_n\}$도 무한이 되어

다시 선택정리로 $x_{n+1} \in X \setminus \{ x, x_0,x_1,\cdots,x_n\}$을 선택한다.

모든 $n \in \mathbb{N}$에 대해 $x_n \in X$이 유일하므로 $f(n) = x_n $인 함수 $f : \mathbb{N} \to X$를 정의하고

$A= f(\mathbb{N}) $로 정의할때 모든 $n \in \mathbb{N}$에 대해 $g(n) = f(n)$인 함수 $g : \mathbb{N} \to A$는

모든 $y \in A = f(\mathbb{N})$에 대해 $g(n) = f(n) = y$인 $n \in \mathbb{N}$이 존재하므로 전사이고

$n < m$인 임의의 $n,m \in \mathbb{N}$에 대해 $g(m) = f(m) = x_m \in X \setminus \{ x,x_0,x_1,\cdots, x_n,x_{n+1},\cdots, x_{m-1} \}$이므로

$g(m) = f(m) = x_m \ne x_n = f(n) = g(n)$이 되어 $g$는 단사이다.

따라서 $A$는 가부번이고 모든 $n \in \mathbb{N}$에 대해 $x_n \ne x$이므로 $x \notin A$일때 $x \in X$가 되어 $A \subset X$이다.

 

 

 

-------------------------------------------------------------------------------

정의의 링크 : 

https://openknowledgevl.tistory.com/9#def번호

번호는 해당 정의 옆에 붙어있는 작은 숫자입니다.

 

정리의 링크 : 

https://openknowledgevl.tistory.com/9#thm번호

번호는 해당 정리 옆에 붙어있는 작은 숫자입니다.

 

위 내용은 아래의 출처를 기반으로 정리한 내용입니다.

틀린 내용이 존재할 수 있습니다.

 

출처(저자 - 제목 - ISBN13)

Robert G. Bartle - Introduction to real analysis - 9788993543766

Terence Tao - Analysis 1 - 9791156646662

A. G. Hamilton - Logic for Mathematicians - 9780521368650