前エントリの証明を簡潔にした。命題3・4を経由せずに命題5を帰納法で直接証明し、命題4はその特別な場合(命題6(1))として証明した。また命題6(2)では自然数の整列性を積極的に用いた。なお、対応が分かりやすいよう、命題番号はそのままとした。
【命題1】単射の定義域と値域とは対等である。
(証明)単射$f:X\to Y$に対し写像$\begin{array}{ccc
}X&\to&f[X]\\x&\mapsto&f(x)\end{array}$は$\mbox{dom}(f)$から$\mbox{ran}(f)$への全単射となる。■
【定義】集合$A\subseteq\mathbb{N}$に対し写像$C_A:\mathbb{N}\to\mathbb{N}$を次のように再帰的に定義する。ただし$n'$は後続数$n\cup\{n\}$を表す。\[C_A(0)=0,\]\[C_A(n')=\left\{\begin{array}{ll}(C_A(n))'&(n\in A)\\C_A(n)&(n\notin A)\end{array}\right.\]
【命題2】任意の$A\subseteq\mathbb{N},n\in\mathbb{N}$に対して$C_A(n)\leq n$であり、等号は$n\subseteq A$のときのみ成立する。
(証明)$A\subseteq\mathbb{N}$を任意にとり、$n$についての帰納法を用いる。まず$C_A(0)=0\leq 0$であり、$0=0$と$0\subseteq A$はともに真である。$C_A(n)\leq n$(等号は$n\subseteq A$のときのみ成立)を仮定すると、$C_A(n')$は$C_A(n)$または$(C_A(n))'$のいずれかの値をとるから、どちらにせよ$n'$以下である。$C_A(n')=n'$となるのは$C_A(n)=n$かつ$C_A(n')=(C_A(n))'$のときのみ、すなわち$n\subseteq A$かつ$n\in A$のときのみであり、これは$n'\subseteq A$とまとめられる。■
【命題5】任意の$A\subseteq\mathbb{N}, n\in\mathbb{N}$に対して、$C_A\vert_{A\cap n}$は単射であり、その値域は$C_A(n)$である。
(証明)任意に$A$をとって$\varphi(n)$:「$C_A\vert_{A\cap n}$は単射であり、その値域は$C_A(n)$である」とおき、$n$についての帰納法を用いる。$\varphi(0)$については空写像が単射であり値域が空であることから従う。$\varphi(n)$を仮定して$\varphi(n')$を導く。$C_A\vert_{A\cap n'}$という写像は、$n\notin A$のときは$C_A\vert_{A\cap n}$と同じであり、$n\in A$のときはこれに$n\mapsto C_A(n)$という対応を追加したものである。$\varphi(n)$により値域はそれぞれ$C_A(n)$と$C_A(n)\cup\{C_A(n)\}$であり、いずれにせよ$C_A\vert_{A\cap n'}$は単射であり値域は$C_A(n')$と書ける。■
【命題6】(1)$A\subseteq n\in\mathbb{N}$なる任意の$A,n$について、$C_A\vert_A$は単射であり、その値域は$C_A(n)$である。
(2)$A\subseteq\mathbb{N}$が$A\subseteq n$なる$n\in\mathbb{N}$を持たない(つまり、いかなる$n\in\mathbb{N}$に対しても$A\backslash n\neq\varnothing$である)とき、$C_A\vert_A$は単射であり、その値域は$\mathbb{N}$である。
(証明)(1)$A\subseteq n$から$A=A\cap n$、これと命題5により従う。
(2)(単射性)$x,y\in A$かつ$x\neq y$を仮定して$C_A(x)\neq C_A(y)$を導く。$x\in y$または$y\in x$が成り立つので、前者の場合について示せば後者も同様である。命題5により、$C_A\vert_{A\cap y}$の値域は$C_A(y)$である。$x$はこの写像の定義域に属すので$C_A(x)\in C_A(y)$、したがって$C_A(x)\neq C_A(y)$である。
(値域)帰納法を用いて$\mathbb{N}\subseteq\mbox{ran}(C_A\vert_A)$を示す。まず$A=A\backslash 0\neq\varnothing$から$k=\mbox{min} A$がとれて、命題5より$C_A(k)=\mbox{ran}(C_A\vert_{A\cap k})=\mbox{ran}(C_A\vert_\varnothing)=\varnothing=0$、したがって$0$は$C_A\vert_A$の値域に属す。次に$n\in\mbox{ran}(C_A\vert_A)$を仮定して$n'\in\mbox{ran}(C_A\vert_A)$を導く。この仮定により$C_A(s)=n$ なる$s\in A$がとれるが、$A\backslash s'\neq\varnothing$により$t=\mbox{min}(A\backslash s')$がとれる。すると$A\cap t=A\cap s'$であり、命題5により$C_A(t)=\mbox{ran}(C_A\vert_{A\cap t})=\mbox{ran}(C_A\vert_{A\cap s'})=C_A(s')=(C_A(s))'=n'$となるから、$n'$は$C_A\vert_A$の値域に属す。■
【命題7】(1)$n\in\mathbb{N}, A\subseteq n$のとき、$A$は有限集合であり、$\mbox{Card}(A)=C_A(n)\leq n$である(等号は$A=n$のときのみ成立)。
(2)$A\subseteq\mathbb{N}$が$A\subseteq n$なる$n\in\mathbb{N}$を持たないとき、$A$は可算無限集合である。
(証明)(1)命題6(1)と命題1により$A$と$C_A(n)\in\mathbb{N}$は対等であるから$A$は有限集合であり、$\mbox{Card}(A)=C_A(n)$である。また命題2よりこれは$n$以下であり、等号は$n\subseteq A$のとき、すなわち$A=n$のときのみ成立する。
(2)命題6(2)と命題1により$A$と$\mathbb{N}$は対等であるから、$A$は可算無限集合である。■