§E1.18等濃度と可算性

証明.(1)を示す。集合$\{x\in\mathbb N_{\geq0}\mid x=0\text{ または }\exists y\in\mathbb N_{\geq0}\ (x=S(y))\}$は$0$を含み後続について閉じているから、§E1.14 命題 1.2の部分集合に対する帰納法により$\mathbb N_{\geq0}$に等しい。したがって零でない自然数はある自然数の後続である。

(2)を示す。$m\leq S(n)$かつ$m\neq S(n)$ならば$m\leq n$である。実際、$m+k=S(n)=n+1$を満たす$k\in\mathbb N_{\geq0}$を取ると、$k=0$の場合は$m=S(n)$となるので$k\neq0$であり、(1)により$k=S(k')$となる$k'\in\mathbb N_{\geq0}$が存在し、$m+k'+1=n+1$から§E1.14 命題 1.2 (1)の消去律によって$m+k'=n$、すなわち$m\leq n$である。この含意と§E1.14 命題 1.2 (4)により、$m<S(n)$と「$m<n$または$m=n$」とは同値である。$n=0$のとき、$m<0$を満たす$m$は存在しないので$\{m\in\mathbb N_{\geq0}\mid m<0\}=\emptyset=0$である。$n=\{m\in\mathbb N_{\geq0}\mid m<n\}$とすると、いま得た同値により

である。よって§E1.14 命題 1.2の部分集合に対する帰納法により、すべての$n$について主張が成り立つ。

(3)を示す。(2)により$n=\{k\in\mathbb N_{\geq0}\mid k<n\}$であるから、$m\in n$と$m<n$とは同値である。

(4)を示す。$m\leq n$とすると、§E1.14 命題 1.2 (4)の推移性から$\{k\in\mathbb N_{\geq0}\mid k<m\}\subseteq\{k\in\mathbb N_{\geq0}\mid k<n\}$であり、(2)により$m\subseteq n$である。▨

証明.(1)を示す。$n=0$のとき$0=\emptyset$であり、$S(0)=\{0\}$は空でないから$S(0)\to0$という写像自体が存在しない。

単射$S(n)\to n$が存在しないとし、$f\colon S(S(n))\to S(n)$が単射であるとする。$a=f(S(n))\in S(n)$とおき、写像$\sigma\colon S(n)\to S(n)$を、$a=n$のときは恒等写像、$a\neq n$のときは$a$と$n$を入れ替えて他を動かさない写像として定める。どちらの場合も$\sigma$は全単射であるから、$g=\sigma\circ f$は単射であり$g(S(n))=n$である。$i\in S(n)$ならば$i\neq S(n)$であり$g$は単射であるから$g(i)\neq n$、すなわち$g(i)\in S(n)$かつ$g(i)\neq n$である。定義 1.2の$S(n)=n\cup\{n\}$により$g(i)\in n$であるから、$g$の$S(n)$への制限は単射$S(n)\to n$を与える。これは帰納法の仮定に反する。よって$n$についての帰納法により、各$n$について単射$S(n)\to n$は存在しない。

(2)を示す。単射$u\colon m\to n$が存在し、$m\leq n$でないとする。§E1.14 命題 1.2 (4)により$n<m$である。補題 1.3 (3)と定義 1.2の$S(n)=n\cup\{n\}$により、$m<S(n)$と「$m<n$または$m=n$」とは同値であるから、この含意の対偶によって$n<m$から$S(n)\leq m$が従う。補題 1.3 (4)により$S(n)\subseteq m$である。$u$を$S(n)$へ制限すると単射$S(n)\to n$が得られ、(1)に反する。▨

証明. 全単射$b\colon m\to X$と$c\colon n\to X$が存在するとする。$c^{-1}\circ b\colon m\to n$と$b^{-1}\circ c\colon n\to m$はいずれも全単射であり、とくに単射である。補題 2.1 (2)により$m\leq n$かつ$n\leq m$であるから、§E1.14 命題 1.2 (4)の反対称性によって$m=n$である。▨

証明. 各$n\in\mathbb N_{\geq0}$について、$n$の部分集合はすべて有限である。実際、$A\subseteq0=\emptyset$ならば$A=\emptyset$であり、空写像が全単射$0\to A$を与える。$n$の部分集合がすべて有限であるとし、$A\subseteq S(n)=n\cup\{n\}$とする。$A\cap n$は$n$の部分集合であるから、全単射$b\colon k\to A\cap n$が存在する。$n\notin A$ならば$A=A\cap n$であり$A$は有限である。$n\in A$ならば、$b$を$k\mapsto n$で延長した写像は全単射$S(k)\to A$であるから、$A$は有限である。よって§E1.14 命題 1.2の部分集合に対する帰納法により、各$n$の部分集合はすべて有限である。

(1)を示す。$F$は有限であるから全単射$c\colon n\to F$が存在し、$n=\#F$である。$c^{-1}[S]$は$n$の部分集合であるから有限であり、全単射$d\colon k\to c^{-1}[S]$が存在する。$c$の$c^{-1}[S]$への制限は$c^{-1}[S]$から$S$への全単射であるから、その合成は全単射$k\to S$を与える。したがって$S$は有限であり$\#S=k$である。

(2)を示す。$d$と包含写像$c^{-1}[S]\subseteq n$の合成は単射$k\to n$であるから、補題 2.1 (2)により$k\leq n$、すなわち$\#S\leq\#F$である。

(3)を示す。$S\neq F$とし、$t\in F\setminus S$を取る。$S\cup\{t\}\subseteq F$であり、全単射$k\to S$を$k\mapsto t$で延長すると全単射$S(k)\to S\cup\{t\}$が得られるので、$\#(S\cup\{t\})=S(k)$である。(2)を$S\cup\{t\}\subseteq F$に適用すると$S(k)\leq n$であり、$\#S=k<S(k)\leq n=\#F$である。▨

証明.(1)を示す。単射$v\colon\mathbb N_{\geq0}\to X$が存在し、$X$が有限であるとする。全単射$b\colon n\to X$を取る。補題 1.3 (2)により$S(n)\subseteq\mathbb N_{\geq0}$であるから、$v$の$S(n)$への制限と$b^{-1}$の合成は単射$S(n)\to n$を与える。これは補題 2.1 (1)に反する。よって$X$は無限である。

(2)を示す。$X$が可算ならば全単射$\mathbb N_{\geq0}\to X$が存在し、これは単射であるから、(1)により$X$は無限である。

(3)を示す。$X$が有限かつ可算であるとすると、(2)により$X$は無限となり、有限であることに反する。▨

証明.(1)を示す。$\#I=0$ならば$I=\emptyset$であり、空写像が条件を満たす。$\#I=S(k)$とし、全単射$b\colon S(k)\to I$を取る。$I'=b[k]$とおくと$b$の$k$への制限は全単射$k\to I'$であるから$\#I'=k$であり、$\#I$についての帰納法の仮定により$f'(i)\in A_i$を各$i\in I'$で満たす写像$f'$が存在する。$A_{b(k)}\neq\emptyset$であるから元$a\in A_{b(k)}$を一つ取り、$f$を$I'$上で$f'$、$b(k)$で$a$と定める。定義 1.2の$S(k)=k\cup\{k\}$により$I=b[S(k)]=I'\cup\{b(k)\}$であるから、$f$は求める写像である。

(2)を示す。各$y\in F$に対して$A_y=p^{-1}[\{y\}]$とおくと、$p$が全射であるから$A_y\neq\emptyset$である。(1)を$I=F$と$(A_y)_{y\in F}$に適用して写像$s$を得ると、各$y$について$s(y)\in p^{-1}[\{y\}]$、すなわち$p(s(y))=y$である。▨

証明. 各$t\in\mathbb N_{\geq0}$に対して$M_t=\{m\in M\mid t<m\}$とおく。$M_t=\emptyset$とすると$M\subseteq S(t)$となり、補題 2.4 (1)により$M$は有限となって仮定に反するので、$M_t\neq\emptyset$である。$M=\emptyset$ならば$M$は有限であるから、$M\neq\emptyset$でもある。$\mathbb N_{\geq0}$の空でない部分集合$A$は最小元をもつ。実際、$0\in A$ならば$0$が$A$の最小元であり、$0\notin A$ならば$A\subseteq\mathbb Z_{\geq1}$であるから、「数学的帰納法の論理構造」の§A3.10 定理 2.1が$A$の最小元を与える。そこで$h\colon\mathbb N_{\geq0}\to\mathbb N_{\geq0}$を$h(t)=\min M_t$と定め、「帰納法と再帰的な定義」の§D2.1 定理 4.4を$V=\mathbb N_{\geq0}$、$g(0)=\min M$、$h_S=h$に適用して

を満たす写像$r\colon\mathbb N_{\geq0}\to\mathbb N_{\geq0}$を得る。$\min M\in M$であり、$h(t)\in M_t\subseteq M$であるから、帰納法により各$r(k)$は$M$に属する。また$r(S(k))\in M_{r(k)}$より$r(k)<r(S(k))$であり、§E1.14 命題 1.2 (4)の推移性から$k<l$ならば$r(k)<r(l)$である。したがって$r$は単射である。さらに$r(0)\geq0$であり、$r(k)\geq k$ならば$r(S(k))>r(k)\geq k$から$r(S(k))\geq S(k)$であるから、帰納法により各$k$について$k\leq r(k)$である。

$M\setminus r[\mathbb N_{\geq0}]\neq\emptyset$とし、§A3.10 定理 2.1によりその最小元$m$を取る。$r(0)=\min M\leq m$であり、$m\notin r[\mathbb N_{\geq0}]$であるから$r(0)<m$である。集合$K=\{k\in\mathbb N_{\geq0}\mid m\leq r(k)\}$は$m\leq r(m)$より空でないので、その最小元$k_1$を取る。$r(0)<m$より$k_1\neq0$であるから$k_1=S(k_0)$と書け、$k_1$の最小性により$r(k_0)<m$である。$m\in M$かつ$r(k_0)<m$であるから$m\in M_{r(k_0)}$であり、$r(S(k_0))=\min M_{r(k_0)}\leq m$である。一方$S(k_0)=k_1\in K$より$m\leq r(S(k_0))$であるから$r(S(k_0))=m$となり、$m\notin r[\mathbb N_{\geq0}]$に反する。よって$r$は全単射$\mathbb N_{\geq0}\to M$であり、$M$は可算である。▨

証明.(1)$A$は空でないので、その元$a_0$を一つ取る。$n\in i(A)$のとき、$i$が単射であるから$i(a)=n$を満たす$a\in A$は一意である。よって主張の対応は写像$e\colon\mathbb Z_{\geq0}\to A$を定める。各$a\in A$について$i(a)\in i(A)$かつ$e(i(a))=a$であるから、$e$は全射である。

(2)$e$は全射であるから、各$a\in A$について$\{n\in\mathbb Z_{\geq0}\mid e(n)=a\}$は空でない。$\mathbb Z_{\geq0}$の空でない部分集合は最小元をもつので、その最小元$j(a)$が定まり、$j$は写像$A\to\mathbb Z_{\geq0}$である。$j(a)=j(b)$とすると、$e(j(a))=a$と$e(j(b))=b$から$a=b$である。よって$j$は単射である。

(1)と(2)が同値の両方向を与える。

(3)$i(A)\neq\mathbb Z_{\geq0}$とし、$i(A)$に属さない$n$を一つ取る。$e$の定め方により$e(n)=a_0$であり、$e(i(a_0))=a_0$である。$i(a_0)\in i(A)$であるから$n\neq i(a_0)$であり、相異なる二点$n$と$i(a_0)$における$e$の値がともに$a_0$となる。よって$e$は単射でない。▨

証明.(1)を示す。単射$X\to\mathbb N_{\geq0}$が存在すれば、定義 1.2 (3)により$X$は高々可算である。逆に$X$が高々可算であるとする。単射$X\to\mathbb N_{\geq0}$が存在する場合はそのままである。$X$が有限である場合には全単射$b\colon n\to X$が存在し、補題 1.3 (2)により$n\subseteq\mathbb N_{\geq0}$であるから、$b^{-1}$と包含写像の合成が単射$X\to\mathbb N_{\geq0}$を与える。

(2)を示す。$X$が有限ならば定義 1.2 (3)により高々可算であり、$X$が可算ならば全単射$\mathbb N_{\geq0}\to X$の逆写像が単射$X\to\mathbb N_{\geq0}$を与えるので高々可算である。逆に$X$を高々可算とし、$X$が有限でないとする。(1)により単射$u\colon X\to\mathbb N_{\geq0}$を取る。$u$は$X$から像$u[X]$への全単射であるから、$u[X]$が有限ならば$X$も有限となる。したがって$u[X]$は無限であり、補題 3.1により可算である。全単射$\mathbb N_{\geq0}\to u[X]$と$u^{-1}$の合成が全単射$\mathbb N_{\geq0}\to X$を与えるので、$X$は可算である。

(3)を示す。$X\neq\emptyset$とする。(1)により、$X$が高々可算であることと単射$X\to\mathbb N_{\geq0}$が存在することは同値である。また、定義 1.2により$\mathbb N_{\geq0}=\mathbb Z_{\geq0}$であるから、補題 3.2により、単射$X\to\mathbb N_{\geq0}$が存在することと全射$\mathbb N_{\geq0}\to X$が存在することは同値である。二つの同値をあわせると主張が従う。▨

証明.$X$を高々可算集合、$S\subseteq X$とする。定理 3.3 (1)により単射$u\colon X\to\mathbb N_{\geq0}$を取る。$u$の$S$への制限は単射$S\to\mathbb N_{\geq0}$であるから、定理 3.3 (1)により$S$は高々可算である。▨

証明.定理 3.3 (1)により単射$u\colon S\to\mathbb N_{\geq0}$を取る。各$y\in f[S]$に対して$\{u(s)\mid s\in S,\ f(s)=y\}$は$\mathbb N_{\geq0}$の空でない部分集合であるから、§A3.10 定理 2.1により

が定まる。$g(y)=g(y')$とすると、$u(s)=g(y)$かつ$f(s)=y$を満たす$s\in S$と、$u(s')=g(y')$かつ$f(s')=y'$を満たす$s'\in S$が取れる。$u(s)=u(s')$と$u$の単射性から$s=s'$であり、$y=f(s)=f(s')=y'$である。したがって$g$は単射であり、定理 3.3 (1)により$f[S]$は高々可算である。▨

証明.定理 3.3 (1)により単射$u\colon S\to\mathbb N_{\geq0}$を取り、$s_0\in S$を一つ取る。$n\in\mathbb Z_{\geq1}$に対して、$n-1\in u[S]$のとき$e(n)=u^{-1}(n-1)$、$n-1\notin u[S]$のとき$e(n)=s_0$と定める。$s\in S$に対して$n=u(s)+1$とおくと$n\in\mathbb Z_{\geq1}$かつ$e(n)=s$であるから、$e$は全射である。▨

証明.(1)を示す。$T(k)=\frac{k(k+1)}{2}$とおく。$T(0)=0$であり、$T(S(k))=T(k)+k+1$であるから、帰納法により各$T(k)$は自然数であり、$\pi(m,n)=T(m+n)+n$は$\mathbb N_{\geq0}$に値をとる。また$T$は狭義単調増加であり、$T(k)\geq k$である。

各$s\in\mathbb N_{\geq0}$に対して$J_s=\{t\in\mathbb N_{\geq0}\mid T(s)\leq t<T(S(s))\}$とおく。$T(S(s))=T(s)+s+1$であるから$J_s=\{T(s)+j\mid j\leq s\}$であり、$m+n=s$を満たす対$(m,n)$に対する$\pi(m,n)=T(s)+n$の値の全体はちょうど$J_s$に等しい。

$t\in\mathbb N_{\geq0}$を取る。$T(S(t))\geq S(t)>t$であるから$\{s\in\mathbb N_{\geq0}\mid t<T(s)\}$は空でなく、§A3.10 定理 2.1によりその最小元$s_1$が定まる。$T(0)=0\leq t$であるから$s_1\neq0$であり、$s_1=S(s_0)$と書ける。最小性により$T(s_0)\leq t<T(S(s_0))$であるから$t\in J_{s_0}$である。$T$が狭義単調増加であることから、$s\neq s'$ならば$J_s\cap J_{s'}=\emptyset$である。よって各$t$はちょうど一つの$J_s$に属する。

$\pi(m,n)=\pi(m',n')=t$とすると、$t\in J_{m+n}\cap J_{m'+n'}$であるから$m+n=m'+n'=s$であり、$T(s)+n=T(s)+n'$から$n=n'$、したがって$m=m'$である。よって$\pi$は単射である。$t\in\mathbb N_{\geq0}$に対して$t\in J_s$となる$s$を取り、$n=t-T(s)$、$m=s-n$とおくと$n\leq s$であり$\pi(m,n)=t$である。よって$\pi$は全射である。

(2)を示す。$\pi$の逆写像は全単射$\mathbb N_{\geq0}\to\mathbb N_{\geq0}\times\mathbb N_{\geq0}$であるから、$\mathbb N_{\geq0}\times\mathbb N_{\geq0}$は可算である。▨

証明.(1)を示す。「整除・余りとユークリッドの互除法」の除法の原理により、各$n\in\mathbb N_{\geq0}$に対して$n=2k$または$n=2k+1$を満たす$k\in\mathbb N_{\geq0}$がただ一つ定まる。そこで写像$g\colon\mathbb N_{\geq0}\to\mathbb Z$を

によって定める。表示の一意性により$g$は写像である。$a\in\mathbb Z$とする。§E1.14 命題 1.4 (3)の同一視のもとで$0\leq a$ならば$g(2a)=a$であり、$a<0$ならば$-a-1\in\mathbb N_{\geq0}$であって$g(2(-a-1)+1)=a$であるから、$g$は全射である。$g(2k)=g(2k')$ならば$k=k'$、$g(2k+1)=g(2k'+1)$ならば$k=k'$である。また$g(2k)=k\geq0$かつ$g(2k'+1)=-(k'+1)<0$であるから、偶数の像と奇数の像は交わらない。したがって$g$は単射であり、全単射$\mathbb N_{\geq0}\to\mathbb Z$である。よって$\mathbb Z$は可算である。

(2)を示す。$g\times g$は全単射$\mathbb N_{\geq0}\times\mathbb N_{\geq0}\to\mathbb Z\times\mathbb Z$であるから、補題 3.8の$\pi$の逆写像との合成は全単射$\mathbb N_{\geq0}\to\mathbb Z\times\mathbb Z$を与える。よって$\mathbb Z\times\mathbb Z$は可算であり、定理 3.3 (2)により高々可算である。$\mathbb Z\times\mathbb Z_{\neq0}$はその部分集合であるから、補題 3.4により高々可算である。§E1.14 定義 1.5により$\mathbb Q$は$\mathbb Z\times\mathbb Z_{\neq0}$の商集合であり、$(a,b)\mapsto[a,b]_{\mathbb Q}$は$\mathbb Z\times\mathbb Z_{\neq0}$から$\mathbb Q$への全射である。したがって補題 3.5により$\mathbb Q$は高々可算である。

§E1.14 命題 1.4 (3)と§E1.14 命題 1.6 (2)の合成$\nu\colon\mathbb N\to\mathbb Q$は単射であるから、補題 2.5 (1)により$\mathbb Q$は無限である。よって定理 3.3 (2)により$\mathbb Q$は可算である。▨

証明.(2)を示す。$A$と$B$を高々可算とし、定理 3.3 (1)により単射$u\colon A\to\mathbb N_{\geq0}$と$v\colon B\to\mathbb N_{\geq0}$を取る。写像$w\colon A\cup B\to\mathbb N_{\geq0}$を、$x\in A$のとき$w(x)=2u(x)$、$x\in B\setminus A$のとき$w(x)=2v(x)+1$と定める。偶数と奇数は相異なるので、$w(x)=w(y)$ならば$x$と$y$は同時に$A$に属するか同時に$B\setminus A$に属する。前者では$u(x)=u(y)$から$x=y$、後者では$v(x)=v(y)$から$x=y$である。したがって$w$は単射であり、$A\cup B$は高々可算である。

(1)を示す。$n=0$のとき$\bigcup_{i<0}X_i=\emptyset$は有限であるから高々可算である。$\bigcup_{i<n}X_i$が高々可算であるとすると、補題 1.3 (2)と定義 1.2の$S(n)=n\cup\{n\}$により