復習：可算について
$X$ を集合とする。
| $X {\rm は有限集合}$ | $:\Leftrightarrow$ | $\exi n \in {\mathbb N} \; \exi {\rm 可逆写像} f : n \rightarrow X$ |
| $X {\rm は無限集合}$ | $:\Leftrightarrow$ | $X {\rm は有限集合ではない}$ |
$\all m, n \in {\mathbb N} \;\parenth{ \exi {\rm 可逆写像} f : m \rightarrow n \Rightarrow m \equ n }$ が成り立つ。
- $m$ についての帰納法で証明する。
- $m \equ 0$ ならば、$\all n \in {\mathbb N} \;\parenth{ \exi {\rm 可逆写像} f : 0 \rightarrow n \Rightarrow 0 \equ n }$ は明らかである。
- [帰納法]$\all n \in {\mathbb N} \;\parenth{ \exi {\rm 可逆写像} h : m \rightarrow n \Rightarrow m \equ n }$ を仮定する。
- $n \in {\mathbb N}$ とし、$\exi {\rm 可逆写像} f : m+1 \rightarrow n$ を仮定する。
- $g : n \rightarrow n, k \mapsto \left\{\begin{array}{@{}l@{}l@{}} k & \parenth{ k \in n \backslash \{ n-1, f(m) \} } \\ f(m) & \parenth{ k \equ n-1 } \\ n-1 & \parenth{ k \equ f(m) } \end{array}\right.$ と置く。
- $g \circ g \equ id_n$ なので $g {\rm は可逆写像}$ であり、従って、$(g \circ f) : m+1 \rightarrow n {\rm は可逆写像}$ である。
- 従って、$(g \circ f)(m) \equ n-1$ に注意すると、制限写像 $(g \circ f)|_m : m \rightarrow n-1 {\rm は可逆写像}$ である。
- 従って、仮定[帰納法]より、$m \equ n-1$ である。
- よって、$m+1 \equ m \cup \{m\} \equ n-1 \cup \{n-1\} \equ n$ である。
- よって、$\all n \in {\mathbb N} \;\parenth{ \exi {\rm 可逆写像} f : m+1 \rightarrow n \Rightarrow m+1 \equ n }$ である。
${\mathbb N} {\rm は無限集合}$ が成り立つ。
- $m \in {\mathbb N}$ に対し、$g_m : {\mathbb N} \backslash \{m\} \rightarrow {\mathbb N}, k \mapsto \left\{\begin{array}{@{}l@{}l@{}} k & \parenth{ k \lt m } \\ k-1 & \parenth{ m \lt k } \end{array}\right.$ と置く。
これは明らかに可逆写像である。 - $n$ についての帰納法で証明する。
- $n \equ 0$ ならば、$\all f : 0 \rightarrow {\mathbb N} \; f {\rm は可逆写像ではない}$ である。
- [帰納法]$n \in {\mathbb N}$ とし、$\all f : n \rightarrow {\mathbb N} \; f {\rm は可逆写像ではない}$ を仮定する。
- $f : n+1 \rightarrow {\mathbb N}$ を任意に取る。
- $f$ の制限を $f|_n : n \rightarrow {\mathbb N} \backslash \{ f(n) \}$ で表す。
- 仮定[帰納法]より、$g_{f(n)} \circ f|_n : n \rightarrow {\mathbb N} {\rm は可逆写像ではない}$ である。
- 従って、$g_{f(n)} {\rm は可逆写像}$ より、$f|_n \equ g_{f(n)}^{-1} \circ ( g_{f(n)} \circ f|_n ) : n \rightarrow {\mathbb N} \backslash \{ f(n) \} {\rm は可逆写像ではない}$ である。
- よって、$f : n+1 \rightarrow {\mathbb N} \; {\rm は可逆写像ではない}$ である。
- よって、$\all f : n+1 \rightarrow {\mathbb N} \; f {\rm は可逆写像ではない}$ である。
- $m \in {\mathbb N}$ に対し、$g_m : {\mathbb N} \backslash \{m\} \rightarrow {\mathbb N}, k \mapsto \left\{\begin{array}{@{}l@{}l@{}} k & \parenth{ k \lt m } \\ k-1 & \parenth{ m \lt k } \end{array}\right.$ と置く。
$X$ を集合とする。
| ${\mathbb N} \ni n {\rm は}X{\rm の濃度}$ $\parenth{ {\rm Card}\;X \equ n }$ |
$:\Leftrightarrow$ | $\exi {\rm 可逆写像} f : n \rightarrow X$ |
| $X {\rm は可算無限集合}$ $\parenth{ {\rm Card}\;X \equ \aleph_0 }$ |
$:\Leftrightarrow$ | $\exi {\rm 可逆写像} f : {\mathbb N} \rightarrow X$ |
| $X {\rm は可算集合}$ | $:\Leftrightarrow$ | $X {\rm は有限集合または可算無限集合}$ |
$A \subset {\mathbb N}$ に対して、${\rm Cnt}_A : {\mathbb N} \rightarrow {\mathbb N}$ を、$\left\{\begin{array}{@{}r@{}c@{}l@{}} {\rm Cnt}_A(0) & :\equiv & 0 \\ {\rm Cnt}_A(n+1) & :\equiv & \left\{\begin{array}{@{}l@{}l@{}} {\rm Cnt}_A(n)+1 & \parenth{ n \in A } \\ {\rm Cnt}_A(n) & \parenth{ n \not\in A } \end{array}\right. \end{array}\right.$
によって定義する。
によって定義する。
$\all A \subset {\mathbb N} \; \all n \in {\mathbb N} \; \all k \leq n \; {\rm Cnt}_A(k) \equ {\rm Cnt}_{A \cap n}(k)$ が成り立つ。
- $k$ に関する帰納法によって示す。
- $k \equ 0$ の時は明らかである。
- $k$ の時の成立を仮定し、$k+1 \leq n$ を仮定する。
- $k \not\in A$ の時：
- $k \in A$ の時：
- よって、${\rm Cnt}_A(k+1) \equ {\rm Cnt}_{A \cap n}(k+1)$ である。
$\all n \in {\mathbb N} \; \all A \subset n \;\left\{\begin{array}{@{}c@{}l@{}} {\rm (1)} & {\rm 制限写像} {\rm Cnt}_A|_A : A \rightarrow {\rm Cnt}_A(A) \;{\rm は可逆写像} \\ {\rm (2)} & {\rm Card}(A) \equ {\rm Cnt}_A(A) \equ {\rm Cnt}_A(n) \leq n \\ {\rm (3)} & {\rm Cnt}_A(n) \equ n \Rightarrow A \equ n \end{array}\right.$ が成り立つ。
- $n$ に関する帰納法によって証明する。
- $n \equ 0$ の時は、$A \equ \phi$ なので、$\left\{\begin{array}{@{}l@{}} {\rm Cnt}_\phi|_\phi : \phi \rightarrow \phi \;{\rm は可逆写像} \\ {\rm Card}\;\phi \equ {\rm Cnt}_\phi(0) \equ 0 \\ A \equ \phi \equ 0 \end{array}\right.$ である。
- $n$ の時の成立を仮定し、$A \subset n+1$ とする。
- $A_n :\equiv A \cap n \subset n$ と置く。
- $A_n$ に対して帰納法の仮定より、$\left\{\begin{array}{@{}l@{}l@{}} {\rm Cnt}_{A_n}|_{A_n} : A_n \rightarrow {\rm Cnt}_{A_n}(A_n) \;{\rm は可逆写像} & {\rm かつ} \\ {\rm Card}(A_n) \equ {\rm Cnt}_{A_n}(A_n) \equ {\rm Cnt}_{A_n}(n) \leq n & {\rm かつ} \\ {\rm Cnt}_{A_n}(n) \equ n \Rightarrow A_n \equ n & \end{array}\right.$ である。
- まず、${\rm (1),(2)}$ を示す。
- $n \not\in A$ の時：
- $A \subset n$ つまり $A \equ A \cap n \equ A_n$ なので、帰納法の仮定から ${\rm (1),(2)}$ がそのまま成り立つ。
- $n \in A$ の時：
${\rm Cnt}_A(A) \equ {\rm Cnt}_A(n+1)$ が成り立つ。
- $A \subset n+1$ なので $\subset$ は明らかである。
- ${\rm Cnt}_A(k) \in {\rm Cnt}_A(n+1), k \in n+1$ とする。
- $k \in n$ の時：
- ${\rm Cnt}_A(k)$ $\equ$ (1) ${\rm Cnt}_{A_n}(k)$ $\in$ $k \in n$ ${\rm Cnt}_{A_n}(n)$ $\equ$ 帰納法の仮定 ${\rm Cnt}_{A_n}(A_n)$
- 従って、$\exi l \in A_n \; {\rm Cnt}_A(k) \equ {\rm Cnt}_{A_n}(l)$ である。
- また、${\rm Cnt}_{A_n}(l)$ $\equ$ (1) ${\rm Cnt}_A(l) \in {\rm Cnt}_A(A)$ である。
- 以上より、${\rm Cnt}_A(k) \in {\rm Cnt}_A(A)$ である。
- $k \equ n$ の時：
- $k \equ n \in A$ なので、 ${\rm Cnt}_A(k) \equ {\rm Cnt}_A(n) \in {\rm Cnt}_A(A)$ である。
- ${\rm Cnt}_A(n+1)$ $\equ$ ${\rm Cnt}$ の定義 ${\rm Cnt}_A(n) + 1$ $\equ$ (1) ${\rm Cnt}_{A_n}(n) + 1$ $\leq$ 帰納法の仮定 $n+1$ である。
- $x, y \in A, {\rm Cnt}_A(x) \equ {\rm Cnt}_A(y)$ とする。
- $x, y \in A_n$ の時：
- ${\rm Cnt}_{A_n}(x) \equ {\rm Cnt}_A(x) \equ {\rm Cnt}_A(y) \equ {\rm Cnt}_{A_n}(y)$ である。
- 従って、帰納法の仮定より、$x \equ y$ である。
- $x \equ n \lor y \equ n$ の時：
- どちらでも同じなので、$x \equ n$ とする。
- $\all k \in A_n \; {\rm Cnt}_A(k) \equ {\rm Cnt}_{A_n}(k) \in {\rm Cnt}_{A_n}(A_n)$ $\equ$ 帰納法の仮定 ${\rm Cnt}_{A_n}(n) \equ {\rm Cnt}_A(n) \equ {\rm Cnt}_A(y)$ である。
- よって、$y \not\in A_n$ つまり $y \equ n$ である。
- よって、${\rm Cnt}_A|_A : A \rightarrow {\rm Cnt}_A(A) \; {\rm は可逆写像}$ である。
- よって、${\rm Card}(A) \equ {\rm Cnt}_A(A) \equ {\rm Cnt}_A(n+1)$ である。
- ${\rm (3)}$${\rm Cnt}_A(n+1) \equ n+1$ と仮定する。
- ${\rm Cnt}_A(n) \equ {\rm Cnt}_{A_n}(n)$ $\leq$ 帰納法の仮定 $n \lt n+1 \equ {\rm Cnt}_A(n+1)$ なので、${\rm Cnt}_A$ の定義より、$n \in A$
つまり、$n+1 \equ {\rm Cnt}_A(n+1) \equ {\rm Cnt}_A(n)+1$ である。 - 従って、$n \equ {\rm Cnt}_A(n) \equ {\rm Cnt}_{A_n}(n)$ である。
- よって、帰納法の仮定より、$A_n \equ n$ である。
- よって、$A \equ A_n \coprod \{n\} \equ n \coprod \{n\} \equ n+1$ である。
$\all A \subset {\mathbb N} \;\parenth{ \all n \in {\mathbb N} \; A \not\subset n \Rightarrow {\rm Cnt}_A|_A : A \rightarrow {\mathbb N} \;{\rm は可逆写像} }$ が成り立つ。
- $n \in {\mathbb N}$ に対して、$A_n :\equiv A \cap n$ と置く。
- ${\rm (i)}$$x, y \in A \; {\rm Cnt}_A(x) \equ {\rm Cnt}_A(y)$ とする。
- $n :\equiv \max\{x,y\} + 1 \in {\mathbb N}$ と置く。
- $x, y \lt n$ なので $x, y \in A_n$ である。
- ${\rm Cnt}_{A_n}(x)$ $\equ$ (1)と$x \lt n$ ${\rm Cnt}_A(x) \equ {\rm Cnt}_A(y)$ $\equ$ (1)と$y \lt n$ ${\rm Cnt}_{A_n}(y)$ である。
- 従って、(2)より ${\rm Cnt}_{A_n}|_{A_n} : A_n \rightarrow {\mathbb N} \; {\rm は単射}$ なので、$x \equ y$ である。
- ${\rm (ii)}$全射であることを示すためには、 $\all n \in {\mathbb N} \; n \in {\rm Cnt}_A(A)$ を示せばよい。
- $n \in {\mathbb N}$ に関する帰納法によって示す。
- (ア)$\bigcup\limits_{n \in {\mathbb N}} A_n \equ \bigcup\limits_{n \in {\mathbb N}} \parenth{ A \cap n } \equ A \cap \bigcup\limits_{n \in {\mathbb N}} n \equ A \cap {\mathbb N} \equ A$ $\nequ$ 仮定[$\all n \in {\mathbb N} \; A \not\subset n$] $\phi$ である。
- 従って、$\exi l \in {\mathbb N} \; A_l \nequ \phi$ である。
- $a :\equiv \min A_l$ と置く。
- $\all k \lt a \; k \not\in A_l$ なので、${\rm Cnt}_{A_l}(a) \equ 0$ である。
- 従って、$0 \equ {\rm Cnt}_{A_l}(a) \equ {\rm Cnt}_A(a) \in {\rm Cnt}_A(A)$ である。
- (イ)[帰納法]$n \in {\mathbb N}, n \in {\rm Cnt}_A(A)$ を仮定する。
- $\exi k \in A \; n \equ {\rm Cnt}_A(k)$ である。
- 従って、定義により ${\rm Cnt}_A(k+1) \equ {\rm Cnt}_A(k) + 1 \equ n + 1$ である。
- また、仮定より $A \not\subset k+1$ なので、$A_{k+1} \subset k+1$ より、$A_{k+1} \nequ A$ つまり $A \backslash A_{k+1} \nequ \phi$ である。
- $m :\equiv \min\parenth{ A \backslash A_{k+1} }$ と置く。
- $m$ の最小性から $k+1 \leq \all m^\prime \lt m \;\; m^\prime \not\in A$ なので、${\rm Cnt}_A(m) \equ {\rm Cnt}_A(k+1)$ である。
- よって、$n+1$ $\equ$ cnt(k+1)=n+1 ${\rm Cnt}_A(k+1) \equ {\rm Cnt}_A(m)$ $\in$ $m \in A$ ${\rm Cnt}_A(A)$ である。
- よって、$\all n \in {\mathbb N} \; n \in {\rm Cnt}_A(A)$ である。
以下では、$A \subset {\mathbb N}$ とする。
$\parenth{ \exi n \in {\mathbb N} \; A \subset n \Leftrightarrow A {\rm は有限集合} }$ が成り立つ。
- $\Rightarrow$(2)より、${\rm 制限写像} {\rm Cnt}_A|_A : A \rightarrow {\rm Cnt}_A(n) \; {\rm は可逆写像}$ である。
- 従って、定義により $A {\rm は有限集合}$ である。
- $\Leftarrow$[対偶法]$\all n \in {\mathbb N} \; A \not\subset n$ と仮定する。
- (3)より、${\rm 制限写像} {\rm Cnt}_A|_A : A \rightarrow {\mathbb N} \; {\rm は可逆写像}$ である。
- $n \in {\mathbb N}, f : n \rightarrow A$ を任意に取る。
- 上の命題の(2)より、$({\rm Cnt}_A|_A \circ f) : n \rightarrow {\mathbb N} \; {\rm は可逆写像でない}$ である。
- 従って、$f {\rm は可逆写像でない}$ である。
- よって、$A {\rm は有限集合でない}$ である。
$A {\rm は可算集合}$ が成り立つ。
- $\exi n \in {\mathbb N} \; A \subset n$ の時：
- (4)より $A {\rm は有限集合}$ である。
- $\all n \in {\mathbb N} \; A \not\subset n$ の時：
- (3)より $A {\rm は可算無限集合}$ である。
- $\exi n \in {\mathbb N} \; A \subset n$ の時：
- $X$ を集合とする。
以下は同値である：
$\begin{array}{@{}c@{}l@{}} {\rm (i)} & X {\rm は可算集合} \\ {\rm (ii)} & \exi f : X \rightarrow {\mathbb N} \; {\rm は単射} \\ {\rm (iii)} & X \equ \phi \lor \exi g : {\mathbb N} \rightarrow X \; {\rm は全射} \end{array}$- ${\vcenter{ \begin{xy}*[F**:black][white]\xymatrix@C=20pt@R=15pt{ {\rm (i)} \ar@<1ex>[r]^-{(ア)} & {\rm (ii)} \ar@<1ex>[l]^-{(イ)} \ar@<1ex>[r]^-{(ウ)} & {\rm (iii)} \ar@<1ex>[l]^-{(エ)} }\end{xy}}}$の順に示す。
- (ア)$X {\rm は有限集合}$ の時：
- $n \in {\mathbb N}, f : X \rightarrow n \;{\rm は可逆写像}$ とする。
- $n \subset {\mathbb N}$ なので $f$ の終集合を拡張した写像 $f : X \rightarrow {\mathbb N} \;{\rm は単射}$ である。
- $X {\rm は可算無限集合}$ の時：
- $\exi {\rm 可逆写像} f : X \rightarrow {\mathbb N}$ なので $f {\rm は単射}$ である。
- (イ)仮定より、$f : X \rightarrow f(X) \; {\rm は可逆写像}$ である。
- $\exi n \in {\mathbb N} \; f(X) \subset n$ の時：
- (2)より、${\rm 制限写像} {\rm Cnt}_{f(X)}|_{f(X)} : f(X) \rightarrow {\rm Cnt}_{f(X)}(n) \; {\rm は可逆写像}$ である。
- 従って、${\rm Cnt}_{f(X)} \circ f : X \rightarrow {\rm Cnt}_{f(X)}(n) \; {\rm は可逆写像}$ である。
- よって、$X {\rm は有限集合}$ である。
- $\all n \in {\mathbb N} \; f(X) \not\subset n$ の時：
- (3)より、${\rm 制限写像} {\rm Cnt}_{f(X)}|_{f(X)} : f(X) \rightarrow {\mathbb N} \; {\rm は可逆写像}$ である。
- 従って、${\rm Cnt}_{f(X)} \circ f : X \rightarrow {\mathbb N} \; {\rm は可逆写像}$ である。
- よって、$X {\rm は可算無限集合}$ である。
- (ウ)$X \nequ \phi$ として $a \in X$ を取って固定する。
- $g : {\mathbb N} \rightarrow X, n \mapsto \left\{\begin{array}{@{}l@{}l@{}} x & \parenth{ n \equ f(x) \in f(X) {\rm の時} } \\ a & \parenth{ n \not\in f(X) {\rm の時} } \end{array}\right. \; {\rm は全射}$ である。
- (エ)$X \equ \phi$ の時は明らかなので、 $\exi g : {\mathbb N} \rightarrow X \; {\rm は全射}$ とする。
- $f : X \rightarrow {\mathbb N}, x \mapsto \min g^{-1}(\{x\}) \; {\rm は単射}$ である。
$X, Y$ を集合とし、$f : X \rightarrow Y$ を写像とする。
- $f {\rm は単射}$ とする。
$\begin{array}{@{}c@{}l@{}c@{}l@{}} (1) & Y {\rm は可算集合} & \Rightarrow & X {\rm は可算集合} \\ (2) & Y {\rm は有限集合} & \Rightarrow & \left\{\begin{array}{@{}l@{}l@{}} X {\rm は有限集合} & {\rm かつ} \\ {\rm Card}(X) \leq {\rm Card}(Y) & {\rm かつ} \\ {\rm Card}(X) \equ {\rm Card}(Y) & \Rightarrow f {\rm は全単射} \end{array}\right. \end{array}$ が成り立つ。
- $(1)$仮定より、$\exi g : Y \rightarrow {\mathbb N} \; {\rm は単射}$ である。
- よって、$(g \circ f) : X \rightarrow {\mathbb N} \; {\rm は単射}$ である。
- $(2)$$\exi n \in {\mathbb N} \; \exi {\rm 可逆写像} g : Y \rightarrow n$ である。
- $g(f(X)) \subset n$ なので、${\rm Cnt}_{g(f(X))}|_{g(f(X))} : g(f(X)) \rightarrow {\rm Cnt}_{g(f(X))}(n) \; {\rm は可逆写像}$ である。
- 従って、$({\rm Cnt}_{g(f(X))} \circ g \circ f) : X \rightarrow f(X) \rightarrow g(f(X)) \rightarrow {\rm Cnt}_{g(f(X))}(n) \; {\rm は可逆写像}$ である。
- よって、$X {\rm は有限集合}$ であり、${\rm Card}(X) \equ {\rm Cnt}_{g(f(X))}(n) \leq n \equ {\rm Card}(Y)$ である。
- ${\rm Card}(X) \equ {\rm Card}(Y)$ と仮定する。
- ${\rm Cnt}_{g(f(X))}(n) \equ {\rm Card}(X) \equ {\rm Card}(Y) \equ n$ なので $g(f(X)) \equ n \; \parenth{ \equ g(Y) }$ である。
- よって、$f(X) \equ Y$ つまり $f {\rm は全射}$ である。
- $f {\rm は全射}$ とする。
$\begin{array}{@{}c@{}l@{}c@{}l@{}} (1) & X {\rm は可算集合} & \Rightarrow & Y {\rm は可算集合} \\ (2) & X {\rm は有限集合} & \Rightarrow & \left\{\begin{array}{@{}l@{}l@{}} Y {\rm は有限集合} & {\rm かつ} \\ {\rm Card}(X) \geq {\rm Card}(Y) & {\rm かつ} \\ {\rm Card}(X) \equ {\rm Card}(Y) & \Rightarrow f {\rm は全単射} \end{array}\right. \end{array}$ が成り立つ。
- $(1)$$X \equ \phi$ ならば $Y \equ \phi$ なので、$g : {\mathbb N} \rightarrow X \; {\rm は全射}$ とする。
- $(f \circ g) : {\mathbb N} \rightarrow Y \; {\rm は全射}$ である。
- $(2)$仮定[$X {\rm は有限集合}$]より、$\exi n \in {\mathbb N} \; \exi {\rm 可逆写像} g : n \rightarrow X$ である。
- 従って、$(f \circ g) : n \rightarrow Y \; {\rm は全射}$ である。
- $h : Y \rightarrow n, y \mapsto \min (f \circ g)^{-1}(\{y\})$ と定義する。
${\vcenter{ \begin{xy}*[F**:black][white]\xymatrix@C=20pt@R=15pt{ n \ar@<0.5ex>[r]^-{g} & X \ar@<0.5ex>[r]^-{f} & Y \ar@<0.5ex>@/^/[ll]^-{h} }\end{xy}}}$ - 定義より $(f \circ g) \circ h \equ {\rm id}_Y$ なので、$h {\rm は単射}$ である。
- 従って、$(g \circ h) : Y \rightarrow X \; {\rm は単射}$ である。
- よって、(1)より、$Y {\rm は有限集合}$ かつ ${\rm Card}(Y) \leq {\rm Card}(X)$ である。
- ${\rm Card}(Y) \equ {\rm Card}(X)$ を仮定する。
- (1)より $(g \circ h) {\rm は全単射}$ である。
- ${\rm id}_Y \equ (f \circ g) \circ h \equ f \circ (g \circ h)$ なので、$f \equ (g \circ h)^{-1} \;{\rm は全単射}$ である。
$1 \leq \all n \in {\mathbb N} \; {\mathbb N}^n {\rm は可算無限集合}$ が成り立つ。
- $g : {\mathbb N} \times {\mathbb N} \rightarrow {\mathbb N}^+, (m, n) \mapsto 2^m (2n+1)$ と置く。
$g {\rm は可逆写像}$ が成り立つ。
- ${\rm (1)}$$(m_i, n_i) \in {\mathbb N} \times {\mathbb N} \;\parenth{ i \equ 0, 1 }$ とし、 $g(m_0, n_0) \equ g(m_1, n_1)$ を仮定する。
- 素因数分解の一意性定理より、$m_0 \equ m_1$ である。
- 従って、$2n_0 + 1 \equ 2n_1 + 1$ つまり $n_0 \equ n_1$ である。
- ${\rm (2)}$$k \in {\mathbb N}^+$ を任意に取る。
- $k$の素因数分解を考え、偶数の部分と奇数の部分を分けて考えれば、
$\exi (m, n) \in {\mathbb N} \times {\mathbb N} \; g(m,n) \equ k$ である。
- 以下、$n \in {\mathbb N}$ に関する帰納法によって証明する。
- $n \equ 1$ の時は明らかである。
- $1 \leq n \in {\mathbb N}, {\rm 可逆写像}f : {\mathbb N}^n \rightarrow {\mathbb N}$ とする。
- 可逆写像gと帰納法の仮定より、 $(g \circ (f, {\rm id}_{\mathbb N})) : {\mathbb N}^{n+1} \equ {\mathbb N}^n \times {\mathbb N} \rightarrow {\mathbb N} \times {\mathbb N} \rightarrow {\mathbb N}^+ \;{\rm は可逆写像}$ である。
- 明らかに、$h : {\mathbb N}^+ \rightarrow {\mathbb N}, k \mapsto k-1 \; {\rm は可逆写像}$ である。
$X, Y$ を集合とする。
$X, Y {\rm は可算集合} \Rightarrow X \times Y {\rm は可算集合}$ が成り立つ。
- 仮定より、$\left\{\begin{array}{@{}l@{}l@{}} \exi {\rm 単射} f : X \rightarrow {\mathbb N} & {\rm かつ} \\ \exi {\rm 単射} g : Y \rightarrow {\mathbb N} & \end{array}\right.$ である。
- 従って、$(f, g) : X \times Y \rightarrow {\mathbb N} \times {\mathbb N} \; {\rm は単射}$ である。
- また、${\mathbb N} \times {\mathbb N} {\rm は可算集合}$ である。
- 以上より、$X \times Y {\rm は可算集合}$ である。
${\frak X}$ を集合とする。
${\frak X} {\rm は可算集合} {\rm かつ} \all X \in {\frak X} \; X {\rm は可算集合} \Rightarrow^{AC} \bigcup {\frak X} {\rm は可算集合}$ が成り立つ。
- 仮定より、$\phi \nequ \all X \in {\frak X} \; \exi {\rm 全射} f_X : {\mathbb N} \rightarrow X$ である。
- 従って、選択公理より、そのような全射の列$(f_X)_{\phi \nequ X \in {\frak X}}$ が存在する。
- $f : {\frak X} \backslash \{\phi\} \times {\mathbb N} \rightarrow \bigcup \parenth{ {\frak X} \backslash \{\phi\} }, (X, n) \mapsto f_X(n)$ と定義する。
- 仮定[${\frak X} {\rm は可算集合}$]より、$\parenth{ {\frak X} \backslash \{\phi\} } \times {\mathbb N} {\rm は可算集合}$ である。
- 従って、$f {\rm は全射}$ より、$\bigcup {\frak X} \equ \bigcup \parenth{ {\frak X} \backslash \{\phi\} } {\rm は可算集合}$ である。
$X$ を集合とする。
${\rm Fin}(X) \quad:\equiv\quad \Set{ A \subset X }{ A {\rm は有限集合} }$
${\rm bin} : {\rm Fin}({\mathbb N}) \rightarrow {\mathbb N}, A \mapsto \sum\limits_{m \in A} 2^m$ と定義する。
- 従って、${\rm Fin}({\mathbb N}) {\rm は可算無限集合}$ である。
${\rm bin} {\rm は可逆写像}$ が成り立つ。
- ${\rm (1)}$ $n \in {\mathbb N}$ に関する帰納法により、$\all n \in {\mathbb N} \; \all A \subset n \; {\rm bin}(A) \lt 2^n$ である。
$\all n \in {\mathbb N} \; \all A, B \subset n \;\parenth{ {\rm bin}(A) \equ {\rm bin}(B) \Rightarrow A \equ B}$ が成り立つ。
- $n \in {\mathbb N}$ に関する帰納法で証明する。
- $n \equ 0$ ならば $A \equ B \equ \phi$ である。
- $n \in {\mathbb N}$ の時の成立を仮定し、$A, B \subset n+1 {\rm かつ} {\rm bin}(A) \equ {\rm bin}(B)$ とする。
$n \in A \Leftrightarrow n \in B$ が成り立つ。
- $\Rightarrow$$2^n \equ {\rm bin}(\{n\}) \leq {\rm bin}(A) \equ {\rm bin}(B)$ である。
- 従って、A⊆n⇒bin(A)＜2^nより、$B \not\subset n$ である。
- よって、$B \subset n+1$ を合わせて、$n \in B$ である。
- $\Leftarrow$同様である。
- 従って、${\rm bin}$ の定義と${\rm bin}(A) \equ {\rm bin}(B)$より、${\rm bin}(A \backslash \{n\}) \equ {\rm bin}(B \backslash \{n\})$ である。
- 従って、帰納法の仮定より、$A \backslash \{n\} \equ B \backslash \{n\}$ である。
- よって、再度n∈A⇔n∈Bより、$A \equ B$ である。
- $\all A, B \in {\rm Fin}({\mathbb N}) \; \exi n \in {\mathbb N} \; A, B \subset n$ である。
- 以上より、${\rm bin} {\rm は単射}$ である。
- ${\rm (2)}$
$\all n \in {\mathbb N} \; \all k \in 2^n \; \exi A \in {\rm Fin}({\mathbb N}) \; {\rm bin}(A) \equ k$ が成り立つ。
- $n \in {\mathbb N}$ に関する帰納法で証明する。
- $n \equ 0$ ならば、$2^0 \equ 1 \equ \{0\}$ なので、$A \equ \phi$ として ${\rm bin}(\phi) \equ 0$ である。
- $n \in {\mathbb N}$ の時の成立を仮定し、$k \in 2^{n+1}$ とする。
- $k \lt 2^n$ ならば帰納法の仮定から成立は明らかなので、$2^n \leq k \lt 2^{n+1}$ とする。
- $0 \leq k - 2^n \lt 2^n$ なので、帰納法の仮定より、$\exi A \in {\rm Fin}({\mathbb N}) \; {\rm bin}(A) \equ k - 2^n$ である。
- ${\rm bin}(A) \equ k - 2^n \lt 2^n \equ {\rm bin}(\{n\})$ なので $n \not\in A$ である。
- また、$A \in {\rm Fin}({\mathbb N})$ なので、明らかに$A \coprod \{n\} \in {\rm Fin}({\mathbb N})$ である。
- 以上より、${\rm bin}(A \coprod \{n\}) \equ {\rm bin}(A) + {\rm bin}(\{n\}) \equ k$ である。
- $\all n \in {\mathbb N} \; n \lt 2^n$ なので ${\mathbb N} \equ \bigcup\limits_{n \in {\mathbb N}} 2^n$ である。
- 以上より、${\rm bin} {\rm は全射}$ である。
- ${\mathbb N}^{({\mathbb N})} :\equiv \Set{ a \in {\mathbb N}^{\mathbb N} }{ \Set{ n \in {\mathbb N} }{ a(n) \nequ 0 } {\rm は有限集合} }$ と置く。
${\mathbb N}^{({\mathbb N})} {\rm は可算無限集合}$ が成り立つ。
- $m : {\mathbb N}^{({\mathbb N})} \backslash \{ \boldsymbol{0} \} \rightarrow {\mathbb N}, a \mapsto \max\Set{ n \in {\mathbb N} }{ a(n) \nequ 0 }$ と置く。
- $f : {\mathbb N}^{({\mathbb N})} \rightarrow {\rm Fin}({\mathbb N})$ を
$a \mapsto \left\{\begin{array}{@{}c@{}l@{}} \phi & \parenth{ \all n \in {\mathbb N} \; a(n) \equ 0 } \\ \{ a(0) - 1 \} & \parenth{ m(a) \equ 0 } \\ \Set{ \sum\limits_{l=0}^k a(l) + k }{ k \lt m(a) } \cup \left\{ \sum\limits_{l=0}^{m(a)} a(l) + (m(a)-1) \right\} & \parenth{ m(a) \geq 1 } \end{array}\right.$
で定義する。 - 前命題を考えれば、$f {\rm は可逆写像}$ であることを証明すれば良いので、逆写像を定義する。
- $\phi \nequ A \in {\rm Fin}({\mathbb N})$ に対し、$a_A$ を
${\rm Card}_A \equ 1$ の時：- $k \in {\mathbb N}, a_A(k) :\equiv \left\{\begin{array}{@{}l@{}l@{}} {\rm Cnt}_A^{-1}(0) + 1 & \parenth{ k \equ 0 } \\ 0 & \parenth{ {\rm Card}(A) \leq k } \end{array}\right.$
- $k \in {\mathbb N}, a_A(k) :\equiv \left\{\begin{array}{@{}l@{}l@{}} {\rm Cnt}_A^{-1}(0) & \parenth{ k \equ 0 } \\ {\rm Cnt}_A^{-1}(k) - {\rm Cnt}_A^{-1}(k-1) - 1 & \parenth{ 1 \leq k \lt {\rm Card}(A) - 1 } \\ {\rm Cnt}_A^{-1}(k) - {\rm Cnt}_A^{-1}(k-1) & \parenth{ k \equ {\rm Card}(A) - 1 } \\ 0 & \parenth{ {\rm Card}(A) \leq k } \end{array}\right.$
($制限写像 {\rm Cnt}_A : A \rightarrow {\rm Card}(A) \; {\rm は可逆写像}$ であることに注意。)
$g : {\rm Fin}({\mathbb N}) \rightarrow {\mathbb N}^{({\mathbb N})}, A \mapsto \left\{\begin{array}{@{}l@{}l@{}} {\rm ゼロ列}\boldsymbol{0} & \parenth{ A \equ \phi } \\ a_A & \parenth{ A \nequ \phi } \end{array}\right.$ と置く。 - $f,g$ で $\boldsymbol{0}$ と $\phi$ が対応しているので、これ以外の対応について考える。
- ${\rm (1)}$$(g \circ f) \equ {\rm id}_{{\mathbb N}^{({\mathbb N})}}$ を示す。
- $\boldsymbol{0} \nequ a \in {\mathbb N}^{({\mathbb N})}$ を任意に取る。$a_{f(a)} \equ a$ を示せば良い。
- ${\rm (i)}$$m(a) \equ 0$ の時について。
- この時は、$a(0) \nequ 0 {\rm かつ} 1 \leq \all k \in {\mathbb N} \; a(k) \equ 0$ である。
- $a_{f(a)}(0) \equ {\rm Cnt}_{f(a)}^{-1}(0) + 1 \equ (a(0) - 1) + 1 \equ a(0)$ である。
- $1 \leq \all k \in {\mathbb N} \; a_{f(a)}(k)$ $\equ$ ${\rm Card}(f(a)) \equ 1$ $0 \equ a(k)$ である。
- よって、$a_{f(a)} \equ a$ である。
- ${\rm (ii)}$$m(a) \geq 1$ の時について。
$\begin{array}{@{}l@{}l@{}} \all k \lt m(a) \; {\rm Cnt}_{f(a)}\left( \sum\limits_{l=0}^k a(l) + k \right) \equ k & {\rm かつ} \\ {\rm Cnt}_{f(a)}\left( \sum\limits_{l=0}^{m(a)} a(l) + m(a) - 1 \right) \equ m(a) & \end{array}$ が成り立つ。
- $\all A \subset {\mathbb N} \; \all p \in {\mathbb N} \; \all q \lt p \; \parenth{ q \leq \all k \lt p \; k \not\in A \Rightarrow {\rm Cnt}_A(p) \equ {\rm Cnt}_A(q) }$ である。
- ${\rm (ア)}$ $\all p \lt a(0) \; p \not\in f(a)$ なので、${\rm Cnt}_{f(a)}(a(0)) \equ {\rm Cnt}_{f(a)}(0) \equ 0$ である。
- ${\rm (イ)}$[帰納法]$k \lt m(a)$ に対して成り立つことを仮定し、 $k + 1 \lt m(a)$ とする。
- $\sum\limits_{l=0}^{k} a(l) + k + 1 \leq \all p \lt \sum\limits_{l=0}^{k+1} a(l) + (k+1) \;\; p \not\in f(a)$ なので、
Cntが一定の値を取る条件より ${\rm Cnt}_{f(a)}\left( \sum\limits_{l=0}^{k+1} a(l) + (k+1) \right) \equ {\rm Cnt}_{f(a)}\left( \sum\limits_{l=0}^{k} a(l) + k + 1 \right)$ である。 - よって、${\rm Cnt}_{f(a)}\left( \sum\limits_{l=0}^{k+1} a(l) + (k+1) \right)$ $\equ$ $\sum\limits_{l=0}^{k} a(l) + k \in f(a)$ ${\rm Cnt}_{f(a)}\left( \sum\limits_{l=0}^{k} a(l) + k \right) + 1$ $\equ$ 帰納法の仮定 $k + 1$ である。
- ${\rm (ウ)}$ $\sum\limits_{l=0}^{m(a)-1} a(l) + m(a) \leq \all p \lt \sum\limits_{l=0}^{m(a)} a(l) + m(a) - 1 \;\; p \not\in f(a)$ である。
- よって、$\begin{array}[t]{@{}l@{}c@{}l@{}} {\rm Cnt}_{f(a)}\left( \sum\limits_{l=0}^{m(a)} a(l) + m(a) - 1 \right) & \equ & {\rm Cnt}_{f(a)}\left( \sum\limits_{l=0}^{m(a)-1} a(l) + m(a) \right) \\ & \equ & {\rm Cnt}_{f(a)}\left( \sum\limits_{l=0}^{m(a) - 1} a(l) + m(a) - 1 \right) + 1 \\ & \equ & ( m(a) - 1 ) + 1 \\ & \equ & m(a) \end{array}$ である。
- 従って、$\begin{array}[t]{@{}l@{}c@{}l@{}} {\rm Card}(f(a)) & \equ & {\rm Cnt}_{f(a)}(f(a)) \\ & \equ & \begin{array}{@{}l@{}l@{}} & \Set{ {\rm Cnt}_{f(a)}\left( \sum\limits_{l=0}^k a(l) + k \right) }{ k \lt m(a) } \\ \cup & \left\{ {\rm Cnt}_{f(a)}\left( \sum\limits_{l=0}^{m(a)} a(l) + m(a) - 1 \right) \right\} \end{array} \\ & \equ & \Set{ k }{ k \leq m(a) } \\ & \equ & m(a)+1 \end{array}$ である。
- $k \in {\mathbb N}$ を任意に取る。
- $k \equ 0$ の時：
- $a_{f(a)}(0) \equ {\rm Cnt}_{f(a)}^{-1}(0) \equ a(0)$ である。
- $1 \leq k \lt {\rm Card}(f(a)) - 1 \equ m(a)$ の時：
- $\begin{array}[t]{@{}r@{}c@{}l@{}} a_{f(a)}(k) & \equ & {\rm Cnt}_{f(a)}^{-1}(k) - {\rm Cnt}_{f(a)}^{-1}(k-1) - 1 \\ & \equ & \parenth{ \sum\limits_{l=0}^k a(l) + k } - \parenth{ \sum\limits_{l=0}^{k-1} a(l) + (k-1) } - 1\\ & \equ & a(k) \end{array}$ である。
- $k \equ {\rm Card}(f(a)) - 1 \equ m(a)$ の時：
- $\begin{array}[t]{@{}r@{}c@{}l@{}} a_{f(a)}(m(a)) & \equ & {\rm Cnt}_{f(a)}^{-1}(m(a)) - {\rm Cnt}_{f(a)}^{-1}(m(a)-1) \\ & \equ & \parenth{ \sum\limits_{l=0}^{m(a)} a(l) + m(a) - 1 } - \parenth{ \sum\limits_{l=0}^{m(a)-1} a(l) + m(a) - 1 } \\ & \equ & a(m(a)) \end{array}$ である。
- ${\rm Card}(f(a)) \leq k$ の時：
- $a_{f(a)}(k) \equ 0$ $\equ$ $m(a)+1 \equ {\rm Card}(f(a)) \leq k$ $a(k)$ である。
- 以上より、$g(f(a)) \equ a_{f(a)} \equ a$ である。
- ${\rm (2)}$$\phi \nequ A \in {\rm Fin}({\mathbb N})$ を任意に取る。$f(a_A) \equ A$ を示せば良い。
- ${\rm Card}(A) \equ 1$ の時：
- $a_A$ の定義より、$m(a_A) \equ 0$ である。
- $f(a_A) \equ \{ a_A(0) - 1 \} \equ \{ {\rm Cnt}_A^{-1}(0) \} \equ A$ である。
- ${\rm Card}(A) \geq 2$ の時：
- $p :\equiv {\rm Card}(A) - 1$ と置く。
- $\all a, b \in A \;\parenth{ a \lt b \Leftrightarrow {\rm Cnt}_A(a) \lt {\rm Cnt}_A(b) }$ なので、${\rm Cnt}_A^{-1}(p-1) \lt {\rm Cnt}_A^{-1}(p)$ である。
- 従って、$a_A(p) \equ {\rm Cnt}_A^{-1}(p) - {\rm Cnt}_A^{-1}(p-1) \gt 0$ であり、ゆえに、$m(a_A) \equ p$ である。
- 定義より、$\all k \lt {\rm Card}(A) - 1 \;\parenth{ \equ m(a_A) } \; \sum\limits_{l=0}^k a_A(l) + k \equ {\rm Cnt}_A^{-1}(k)$ である。
- ${\rm Cnt}_A^{-1}(m(a_A)) \equ {\rm Cnt}_A^{-1}(m(a_A)-1) + a_A(m(a_A)) \equ \sum\limits_{l=0}^{m(a_A)} a_A(l) + (m(a_A)-1)$ である。
- 従って、$\begin{array}[t]{@{}l@{}c@{}l@{}} f(g(A)) \equ f(a_A) & \equ & \begin{array}[t]{@{}c@{}l@{}} & \Set{ \sum\limits_{l=0}^k a_A(l) + k }{ k \lt m(a_A) } \\ \cup & \left\{ \sum\limits_{l=0}^{m(a)} a_A(l) + m(a_A) - 1 \right\} \end{array} \\ & \equ & \Set{ {\rm Cnt}_A^{-1}(k) }{ k \leq m(a_A) } \\ & \equ & \Set{ {\rm Cnt}_A^{-1}(k) }{ k \lt {\rm Card}(A) } \\ & \equ & A \end{array}$ である。
$X$ を集合とする。
$X {\rm は可算集合} \Rightarrow {\rm Fin}(X) {\rm は可算集合}$ が成り立つ。
- 仮定より、$\exi {\rm 単射} f : X \rightarrow {\mathbb N}$ である。
- $\all A \in {\rm Fin}(X) \; f(A) \in {\rm Fin}({\mathbb N})$ である。
- $f_* : {\rm Fin}(X) \rightarrow {\rm Fin}({\mathbb N}), A \mapsto f(A)$ と置く。
- ${\rm Fin}({\mathbb N}) {\rm は可算集合} {\rm かつ} f_* {\rm は単射}$ なので ${\rm Fin}(X) {\rm は可算集合}$ である。
