§E1.19Cantor の定理

証明.(1)$f\colon A\to\mathcal P(A)$を写像とし、

とおく。「集合の存在原理」の§E1.13 定義 2.1により$D$は$A$の部分集合であり、$D\in\mathcal P(A)$である。$D=f(b)$を満たす$b\in A$が存在すると仮定する。$b\in D$とすると、$D$の定義から$b\notin f(b)$であり、$f(b)=D$であるから$b\notin D$となって矛盾する。$b\notin D$とすると、$b\in A$であるから$D$の定義により$b\in f(b)=D$となって矛盾する。したがって$D$は$f$の像に属さず、$f$は全射ではない。

(2)写像$a\mapsto\{a\}$は$A$から$\mathcal P(A)$への単射であるから、§E1.18 定義 1.1により$|A|\leq|\mathcal P(A)|$である。$|\mathcal P(A)|\leq|A|$が成り立つと仮定すると、単射$g\colon\mathcal P(A)\to A$が存在する。$a\in A$に対して、$g(S)=a$を満たす$S\in\mathcal P(A)$が存在する場合にはその$S$を、存在しない場合には$\emptyset$を値とする対応を$h$とする。$g$は単射であるから第一の場合の$S$は一意であり、$\emptyset\in\mathcal P(A)$であるから第二の場合の値も$\mathcal P(A)$に属する。よって$h$は写像$A\to\mathcal P(A)$である。任意の$S\in\mathcal P(A)$について$h(g(S))=S$であるから$h$は全射であり、(1)に反する。したがって$|\mathcal P(A)|\leq|A|$は成り立たず、§E1.18 定義 1.1が定める狭義比較により$|A|<|\mathcal P(A)|$である。▨

証明. 二進列$x$に対して$\sigma(x)=\{n\in\mathbb Z_{\geq0}\mid x_n=1\}$とおく。§E1.13 定義 2.1により$\sigma(x)$は$\mathbb Z_{\geq0}$の部分集合であり、$\sigma$は写像$\{0,1\}^{\mathbb Z_{\geq0}}\to\mathcal P(\mathbb Z_{\geq0})$である。$S\subseteq\mathbb Z_{\geq0}$と$n\in\mathbb Z_{\geq0}$に対して、$n\in\sigma(\chi_S)$は$(\chi_S)_n=1$と同値であり、指示関数の定義によりこれは$n\in S$と同値である。よって$\sigma(\chi_S)=S$である。逆に二進列$x$と$n$に対して、$n\in\sigma(x)$ならば$(\chi_{\sigma(x)})_n=1=x_n$であり、$n\notin\sigma(x)$ならば$x_n\neq1$すなわち$x_n=0$であって$(\chi_{\sigma(x)})_n=0=x_n$である。よって$\chi_{\sigma(x)}=x$である。二つの合成がいずれも恒等写像であるから、$S\mapsto\chi_S$は全単射であり、$\sigma$がその逆写像である。▨

証明.(1)$N=0$では両辺がともに$1$である。$\left(\frac1b\right)^{N}=\frac1{b^{N}}$を仮定すると、冪の再帰と

から$\left(\frac1b\right)^{N+1}=\frac1{b^{N+1}}$である。

(2)$N$についての帰納法で$(1-r)\sum_{n=0}^{N}r^{n}=1-r^{N+1}$を示す。$N=0$では$r^{0}=1$であるから左辺は$1-r$であり、右辺は$1-r^{1}=1-r$である。$N$で等式が成り立つとすると、

である。$r\neq1$から$1-r\neq0$であり、両辺を$1-r$で割ると主張の等式を得る。

(3)(1)により$\frac1{3^{n}}=\left(\frac13\right)^{n}$であるから、(2)を$r=\frac13$に適用して

を得る。▨

証明.$N=0$のとき和$\sum_{n=0}^{0}\dfrac{x_n}{3^{n+1}}$は$n=0$の項だけからなるので、$s_0(x)=\dfrac{x_0}{3}$である。また有限和は上端を一つ増やすごとに新しい項を加えて定まるから、

である。▨

証明.(1)補題 2.5と$x_{N+1}\geq0$、$3^{N+2}>0$から$s_{N+1}(x)-s_N(x)=\dfrac{x_{N+1}}{3^{N+2}}\geq0$である。$N$から$M$まで有限回この不等式を重ねると$s_N(x)\leq s_M(x)$を得る。

(2)各項$\dfrac{x_n}{3^{n+1}}$は非負であるから$0\leq s_N(x)$である。また$x_n\leq1$であるから

であり、最後の等号は補題 2.3 (3)による。$3^{N+1}>0$から$\dfrac1{3^{N+1}}>0$であり、右端の狭義不等式が従う。

(3)$n_0<N$とすると、$x_n\leq1$と補題 2.3 (3)により

であり、右辺は$\dfrac12\left(\dfrac1{3^{n_0+1}}-\dfrac1{3^{N+1}}\right)$に等しい。$\dfrac1{3^{N+1}}>0$から、これは$\dfrac12\cdot\dfrac1{3^{n_0+1}}$より小さい。▨

証明.$s_0(x)$はこの集合に属するので、この集合は空でない。命題 2.6 (2)により各$s_N(x)$は$\dfrac12$より小さいから、$\dfrac12$はこの集合の上界である。「完備順序体の一意性」の§E1.15 定義 1.1は、上に有界で空でない任意の部分集合が上限をもつことを完備順序体の性質として定め、「実数体の構成」の§E1.14 定理 3.1は$\mathbb R$がこの性質をもつことを与える。したがってこの集合の上限が$\mathbb R$に存在する。命題 2.6 (2)により$0\leq s_0(x)$であるから上限は$0$以上であり、$\dfrac12$が上界であるから上限は$\dfrac12$以下である。▨

証明.(1)二進列$x$、$y$を$x\neq y$となるように取る。集合$\{n\in\mathbb Z_{\geq0}\mid x_n\neq y_n\}$は空でないので最小元$n_0$をもつ。$x_{n_0}$と$y_{n_0}$は$\{0,1\}$の相異なる元であるから、必要なら$x$と$y$を入れ替えて、$x_{n_0}=1$かつ$y_{n_0}=0$としてよい。

$t=s_{n_0}(y)$とおく。$n_0=0$の場合には$t=\dfrac{y_0}{3}=0$かつ$s_0(x)=\dfrac{x_0}{3}=\dfrac13$である。$n_0>0$の場合には、$n<n_0$で$x_n=y_n$であることと補題 2.5から$s_{n_0-1}(x)=s_{n_0-1}(y)$であり、同じ補題 2.5から$t=s_{n_0-1}(y)+\dfrac{y_{n_0}}{3^{n_0+1}}=s_{n_0-1}(y)$かつ$s_{n_0}(x)=s_{n_0-1}(x)+\dfrac1{3^{n_0+1}}$である。いずれの場合も

が成り立つ。上限は上界であるから$\varphi(x)\geq s_{n_0}(x)=t+\dfrac1{3^{n_0+1}}$である。

次に、$t+\dfrac12\cdot\dfrac1{3^{n_0+1}}$が$\{s_N(y)\mid N\in\mathbb Z_{\geq0}\}$の上界であることを示す。$N\leq n_0$の場合には命題 2.6 (1)により$s_N(y)\leq s_{n_0}(y)=t$である。$N>n_0$の場合には命題 2.6 (3)により

である。いずれの場合も$s_N(y)\leq t+\dfrac12\cdot\dfrac1{3^{n_0+1}}$であるから、上限が最小の上界であることにより

となる。中央の狭義不等式は$\dfrac1{3^{n_0+1}}>0$による。よって$\varphi(x)\neq\varphi(y)$であり、$\varphi$は単射である。

(2)補題 2.2により$S\mapsto\chi_S$は$\mathcal P(\mathbb Z_{\geq0})$から$\{0,1\}^{\mathbb Z_{\geq0}}$への全単射である。$\varphi(\chi_S)=\varphi(\chi_{S'})$とすると、$\varphi$の単射性から$\chi_S=\chi_{S'}$であり、$S\mapsto\chi_S$の単射性から$S=S'$である。よって$S\mapsto\varphi(\chi_S)$は$\mathcal P(\mathbb Z_{\geq0})$の全体で定義された単射である。▨

証明.(1)$N=0$では$b^{0}=1$かつ$0+1=1$であるから等号が成り立つ。$0<b$と冪の再帰から$0<b^{N}$が帰納法で従う。$N+1\leq b^{N}$を仮定すると、$2\leq b$と$0<b^{N}$から

である。したがってすべての非負整数について主張が成り立つ。

(2)§E1.14 定理 3.6により$\mathbb R$における自然数の像は上に有界でないから、$\dfrac1\varepsilon$はその上界ではなく、$\dfrac1\varepsilon<m$を満たす自然数$m$が存在する。$N=m$とおくと(1)を$N+1$に適用して$N+2\leq b^{N+1}$を得る。$m<N+2$であるから$\dfrac1\varepsilon<b^{N+1}$であり、両辺が正であるから$\dfrac1{b^{N+1}}<\varepsilon$である。▨

証明.$\mathbb R$が高々可算であると仮定する。「等濃度と可算性」の§E1.18 定理 3.3 (1)により単射$j\colon\mathbb R\to\mathbb Z_{\geq0}$が存在する。定理 2.9 (2)は$\mathcal P(\mathbb Z_{\geq0})$の全体で定義された単射$S\mapsto\varphi(\chi_S)$を与えるので、これに$j$を続けて合成した写像は単射$\mathcal P(\mathbb Z_{\geq0})\to\mathbb Z_{\geq0}$である。$\emptyset\in\mathcal P(\mathbb Z_{\geq0})$であるから$\mathcal P(\mathbb Z_{\geq0})$は空でなく、§E1.18 補題 3.2 (1)により全射$\mathbb Z_{\geq0}\to\mathcal P(\mathbb Z_{\geq0})$が存在する。これは定理 1.1 (1)に反する。したがって$\mathbb R$は高々可算でない。

$\mathbb Z_{\geq0}$から$\mathbb R$への全射が存在すると仮定する。$0\in\mathbb R$であるから$\mathbb R$は空でなく、§E1.18 補題 3.2 (2)により単射$\mathbb R\to\mathbb Z_{\geq0}$が存在する。すると§E1.18 定義 1.2により$\mathbb R$は高々可算となり、前段に反する。$\mathbb R$が非可算であることは、§E1.18 定義 1.2により高々可算でないことにほかならない。▨

証明. 代数的数の全体を$\mathcal A$と書く。「等濃度と可算性」の§E1.18 定理 7.6により$\mathcal A$は可算であるから、§E1.18 定義 1.2により全単射$\mathbb Z_{\geq0}\to\mathcal A$が存在し、その逆写像は単射$k\colon\mathcal A\to\mathbb Z_{\geq0}$である。

すべての実数が代数的数であると仮定する。§E1.14 命題 4.2の埋め込み$a\mapsto(a,0)$は単射であり、この仮定は各実数の像が$\mathcal A$に属することをいう。したがって、実数$a$にその像の$k$による値を対応させる写像は単射$\mathbb R\to\mathbb Z_{\geq0}$である。すると§E1.18 定義 1.2により$\mathbb R$は高々可算となり、定理 3.3に反する。よって代数的数でない実数が存在し、定義 4.1によりそれは超越数である。▨