§E1.17超限帰納法と超限再帰

証明.(1)を示す。仮定のもとで、$\beta<\alpha$かつ$P(\beta)$が成り立たない順序数$\beta$が存在するとする。$P$を与える論理式に分出公理スキーマを適用して、部分集合

を作る。仮定により$S$は空でない。$S$は順序数$\alpha$の部分集合であるから、§E1.16 定義 2.1により最小元$\beta_0$をもつ。$\xi<\beta_0$を満たす順序数$\xi$を取る。$\xi\in\beta_0\in\alpha$であり$\alpha$は推移的であるから$\xi\in\alpha$である。$\beta_0$の最小性により$\xi\notin S$であるから$P(\xi)$が成り立つ。$\beta_0<\alpha$に仮定を適用すると$P(\beta_0)$が成り立ち、$\beta_0\in S$に反する。よって$S$は空であり、$\beta<\alpha$を満たすすべての$\beta$で$P(\beta)$が成り立つ。

(2)を示す。順序数$\beta$を任意に取る。順序数$\beta+1$に対する(1)の仮定は、いま仮定した条件の特別な場合である。$\beta<\beta+1$であるから(1)により$P(\beta)$が成り立つ。

(3)を示す。§E1.16 命題 4.2 (4)により、順序数はいずれも$0$、後続順序数、極限順序数のちょうど一つに当たる。したがって仮定の含意を三つの場合に分けて確かめれば、すべての$\beta$について確かめたことになる。$\beta=0$については$\xi<0$を満たす順序数が存在しないので、前提「$\xi<0$を満たすすべての$\xi$で$P(\xi)$が成り立つ」は空虚に成り立ち、含意は$P(0)$と同じ内容になる。▨

証明. 順序数$\beta\leq\alpha$と関数$g$について、$g$が$\beta$段の解であるとは、$g$の定義域が$\beta$であり、$\gamma<\beta$を満たすすべての順序数$\gamma$について$g(\gamma)=G(g|\gamma)$が成り立つことをいう。$\beta\leq\alpha$かつ$\gamma<\beta$ならば$\gamma<\alpha$であるから、$G(g|\gamma)$は定まっている。

順序数どうしは大小について比較可能である（§E1.16 命題 2.5 (2)）から、主張 2.1.1により、二つの段の解は共通の定義域で一致する。とくに、同じ定義域をもつ二つの段の解は等しい。

主張 2.1.2を$\beta=\alpha$に適用すると$\alpha$段の解$f$が得られ、これは定義域$\alpha$をもち$f(\beta)=G(f|\beta)$を満たす。主張 2.1.1により、そのような関数は一つしかない。以上が(1)である。

$f$は順序対の集合であるから集合である。その値域は、和集合の公理で作った$\bigcup\bigcup f$から、論理式「ある$\beta$について$(\beta,y)\in f$が成り立つ」によって分出公理スキーマで取り出すことができる。よって(2)が成り立つ。▨

証明.$\beta<\alpha$を満たす順序数$\beta$を定義域とする関数$g$を取る。$g$が意図した入力であるか否かのいずれか一方だけが成り立ち、前者では$G_0(g)$が、後者では$\varnothing$が、それぞれただ一つの集合である。よって$G$は規則としての条件を満たし、定理 2.1 (1)が$f$を与える。これが(1)である。

(2)の仮定のもとでは、$\beta<\alpha$を満たす各$\beta$について$f|\beta$が意図した入力であるから$G(f|\beta)=G_0(f|\beta)$であり、$f(\beta)=G_0(f|\beta)$を得る。▨

証明.$\beta<\alpha$を満たす順序数$\beta$を定義域とする関数$g$に対して、規則$G$を次で定める。$\beta=0$のとき$G(g)=a$、$\beta=\gamma+1$のとき$G(g)=H(\gamma,g(\gamma))$、$\beta$が極限順序数のとき$G(g)=L(\beta,g)$とする。§E1.16 命題 4.2 (4)により三つの場合は尽くしていて互いに排反であり、各場合の値はただ一つの集合であるから、$G$は規則としての条件を満たす。定理 2.1 (1)が与える関数を$f$とする。

$0<\alpha$ならば$f(0)=G(f|0)$であり、$f|0$の定義域は$0$であるから$f(0)=a$である。$\beta+1<\alpha$ならば$f(\beta+1)=G(f|(\beta+1))$であり、$f|(\beta+1)$の定義域は後続順序数$\beta+1$であるから$f(\beta+1)=H(\beta,f(\beta))$である。$\lambda<\alpha$が極限順序数ならば$f(\lambda)=G(f|\lambda)=L(\lambda,f|\lambda)$である。

一意性を示す。定義域$\alpha$の関数$f'$が三つの等式を満たすとする。$\beta<\alpha$を取ると、$\beta$が$0$、後続順序数、極限順序数のいずれであるかに応じて、$f'(\beta)=G(f'|\beta)$が成り立つ。よって$f'$は定理 2.1 (1)の条件を満たし、$f'=f$である。▨

証明.(1)を示す。$f_{\alpha'}|\alpha$の定義域は$\alpha$である。$\beta<\alpha$を取ると$\beta<\alpha'$であり、$(f_{\alpha'}|\alpha)|\beta=f_{\alpha'}|\beta$であるから

である。よって$f_{\alpha'}|\alpha$は、定理 2.1 (1)が定義域$\alpha$について述べる条件を満たす。一意性から$f_{\alpha'}|\alpha=f_\alpha$である。

(2)を示す。$\beta<\alpha$かつ$\beta<\alpha'$とする。順序数どうしは大小について比較可能である（§E1.16 命題 2.5 (2)）から$\alpha\leq\alpha'$としてよく、(1)により$f_{\alpha'}(\beta)=(f_{\alpha'}|\alpha)(\beta)=f_\alpha(\beta)$である。よって値は$\alpha$の取り方に依存せず、$F(\beta)$と書くことができる。順序数$\alpha$と$\beta<\alpha$に対して$F(\beta)=f_\alpha(\beta)$であるから$F|\alpha=f_\alpha$である。最後に、順序数$\beta$に対して$\alpha=\beta+1$を取ると

である。▨

証明.(1)を示す。系 2.6 (2)により、順序数$\beta$について$\alpha+\beta=G_\alpha(F|\beta)$である。$F|\beta$の定義域は$\beta$であるから、$\beta$が$0$、後続順序数$\gamma+1$、極限順序数$\lambda$のそれぞれについて$G_\alpha$の定め方を読むと、$\alpha+0=\alpha$、$\alpha+(\gamma+1)=(\alpha+\gamma)\cup\{\alpha+\gamma\}=(\alpha+\gamma)+1$、$\alpha+\lambda=\bigcup\{\alpha+\gamma\mid\gamma<\lambda\}$を得る。

(2)を示す。$1$は$0$の後続であるから、いま示した第二の等式を$\beta=0$に適用すると$\alpha+1=(\alpha+0)+1$であり、第一の等式により$\alpha+0=\alpha$であるから$\alpha+1=\alpha\cup\{\alpha\}$である。▨

証明.$\alpha$を固定し、(1)を$\beta$に関する定理 1.1 (2)で示す。$\alpha$は任意に取ったので、すべての対$(\alpha,\beta)$について主張が従う。定理 1.1 (3)に従って三つの場合を確かめる。

$\beta=0$では命題 4.1 (1)により$\alpha+0=\alpha$が順序数である。

$\beta=\gamma+1$では、帰納の仮定により$\alpha+\gamma$が順序数であり、命題 4.1 (1)と§E1.16 命題 4.2 (1)によりその後続$(\alpha+\gamma)+1=\alpha+\beta$も順序数である。

$\beta$が極限順序数$\lambda$である場合、帰納の仮定により各$\alpha+\gamma$（$\gamma<\lambda$）は順序数である。定理 2.1 (2)により$A=\{\alpha+\gamma\mid\gamma<\lambda\}$は集合であり、順序数からなる。§E1.16 補題 4.4により$\bigcup A$は順序数であって$A$の最小上界である。命題 4.1 (1)により$\alpha+\lambda=\bigcup A$であるから、主張が成り立つ。

(2)と(3)を、$\alpha$を固定して$\beta$に関する同じ帰納法で同時に示す。性質を「$\alpha\cdot\beta$は順序数である」と定める。$\beta$を取り、$\gamma<\beta$を満たすすべての$\gamma$について$\alpha\cdot\gamma$が順序数であるとすると、$F'|\beta$の値はすべて順序数であるから$F'|\beta$は意図した入力であり、系 2.6 (2)により$\alpha\cdot\beta=G'_\alpha(F'|\beta)=G'_{0,\alpha}(F'|\beta)$である。

$\beta=0$では$\alpha\cdot0=0$が順序数である。

$\beta=\gamma+1$では$\alpha\cdot\beta=(\alpha\cdot\gamma)+\alpha$であり、いま示した(1)を第一引数$\alpha\cdot\gamma$と第二引数$\alpha$に適用すると、これは順序数である。

$\beta$が極限順序数$\lambda$である場合は$\alpha\cdot\lambda=\bigcup\{\alpha\cdot\gamma\mid\gamma<\lambda\}$であり、和の場合と同じ議論により、$\alpha\cdot\lambda$は$\{\alpha\cdot\gamma\mid\gamma<\lambda\}$の最小上界である順序数である。

以上により、すべての順序数$\beta$について$\alpha\cdot\beta$は順序数である。したがって$F'|\beta$はどれも意図した入力であり、上の三つの場合で読んだ等式がそのまま(3)の三つの等式である。▨

証明.$\varphi\colon W\to\operatorname{ot}(W)$を順序同型とし、$\gamma<\lambda$を取る。$W_\gamma=W$の場合は$\varphi(W_\gamma)=\operatorname{ot}(W_\gamma)=\operatorname{ot}(W)$である。$W_\gamma$が$W$の真の始切片である場合は、§E1.16 補題 1.3により$W_\gamma=W_{<a}$を満たす$a\in W$があり、§E1.16 系 3.3により$\operatorname{ot}(W_\gamma)=\varphi(a)\in\operatorname{ot}(W)$である。$\varphi$は順序同型であるから$\varphi(W_\gamma)=\{\zeta\in\operatorname{ot}(W)\mid\zeta<\varphi(a)\}$であり、§E1.16 命題 2.3 (3)によりこれは$\varphi(a)$に等しい。いずれの場合も$\operatorname{ot}(W_\gamma)=\varphi(W_\gamma)$であり、$\operatorname{ot}(W_\gamma)$は順序数であって$\operatorname{ot}(W_\gamma)\leq\operatorname{ot}(W)$である。よって$B=\{\operatorname{ot}(W_\gamma)\mid\gamma<\lambda\}$は$\operatorname{ot}(W)+1$の部分集合であり、§E1.13 定義 2.1により集合である。

$\operatorname{ot}(W)$が$B$の上界であることは既に示した。$B$の上界$\delta$を任意に取る。$\zeta<\operatorname{ot}(W)$とすると$\zeta=\varphi(w)$を満たす$w\in W$があり、仮定により$w\in W_\gamma$を満たす$\gamma<\lambda$がある。よって$\zeta\in\varphi(W_\gamma)=\operatorname{ot}(W_\gamma)$、すなわち$\zeta<\operatorname{ot}(W_\gamma)\leq\delta$である。したがって$\operatorname{ot}(W)\subseteq\delta$、すなわち$\operatorname{ot}(W)\leq\delta$である。以上により$\operatorname{ot}(W)$は$B$の最小上界である。▨

証明.$\alpha$を固定し、(1)を$\beta$に関する定理 1.1 (2)で示す。$\alpha$は任意に取ったので、すべての対$(\alpha,\beta)$について主張が従う。

$\beta=0$の場合、$S(\alpha,0)=\{0\}\times\alpha$であり、$\xi\mapsto(0,\xi)$は$\alpha$からの順序同型であるから、命題 4.1 (1)により$\operatorname{ot}(S(\alpha,0))=\alpha=\alpha+0$である。

$\beta=\gamma+1$の場合、$S(\alpha,\gamma+1)=S(\alpha,\gamma)\cup\{(1,\gamma)\}$であり、$(1,\gamma)$は最大元、$S(\alpha,\gamma)$は始切片である。帰納の仮定により順序同型$\psi\colon S(\alpha,\gamma)\to\alpha+\gamma$がある。$\alpha+\gamma$は$(\alpha+\gamma)+1=(\alpha+\gamma)\cup\{\alpha+\gamma\}$の最大元であり、§E1.16 命題 2.3 (2)により$\alpha+\gamma\notin\alpha+\gamma$であるから、$\psi$に$(1,\gamma)\mapsto\alpha+\gamma$を付け加えると、$S(\alpha,\gamma+1)$から$(\alpha+\gamma)+1$への順序同型を得る。命題 4.1 (1)により$\operatorname{ot}(S(\alpha,\gamma+1))=(\alpha+\gamma)+1=\alpha+(\gamma+1)$である。

$\beta$が極限順序数$\lambda$の場合、$\gamma<\lambda$に対して$S(\alpha,\gamma)$は$S(\alpha,\lambda)$の始切片であり、$\gamma\leq\delta<\lambda$ならば$S(\alpha,\gamma)\subseteq S(\alpha,\delta)$である。§E1.16 命題 4.5 (2)により$\lambda=\bigcup\lambda=\bigcup_{\gamma<\lambda}\gamma$であるから$S(\alpha,\lambda)=\bigcup_{\gamma<\lambda}S(\alpha,\gamma)$である。補題 4.3により$\operatorname{ot}(S(\alpha,\lambda))$は$\{\operatorname{ot}(S(\alpha,\gamma))\mid\gamma<\lambda\}$の最小上界であり、帰納の仮定によりこの集合は$\{\alpha+\gamma\mid\gamma<\lambda\}$である。命題 4.2 (1)によりその最小上界は$\alpha+\lambda$であり、最小上界は一つしかないから$\operatorname{ot}(S(\alpha,\lambda))=\alpha+\lambda$である。

(2)も、$\alpha$を固定して$\beta$に関する同じ帰納法で示す。

$\beta=0$の場合、$0\times\alpha=\varnothing$であるから、命題 4.2 (3)により$\operatorname{ot}(0\times\alpha)=0=\alpha\cdot0$である。

$\beta=\gamma+1$の場合、$(\gamma+1)\times\alpha=(\gamma\times\alpha)\cup(\{\gamma\}\times\alpha)$であり、$\gamma\times\alpha$は始切片である。帰納の仮定により順序同型$\chi\colon\gamma\times\alpha\to\alpha\cdot\gamma$がある。写像

は$(\gamma+1)\times\alpha$から$S(\alpha\cdot\gamma,\alpha)$への全単射である。第一成分がともに$\gamma$より小さい二元の比較は$\chi$が順序同型であることから移り、第一成分がともに$\gamma$である二元の比較は第二成分の比較であって$(1,\cdot)$どうしの比較に移り、第一成分が$\gamma$より小さい元と$\gamma$である元の比較は前者が小さいことであって$(0,\cdot)$と$(1,\cdot)$の比較に移る。よって順序を保ち反映する。したがって(1)と命題 4.2 (3)により

である。

$\beta$が極限順序数$\lambda$の場合、$\gamma<\lambda$に対して$\gamma\times\alpha$は$\lambda\times\alpha$の始切片であり、$\gamma\leq\delta<\lambda$ならば$\gamma\times\alpha\subseteq\delta\times\alpha$である。§E1.16 命題 4.5 (2)により$\lambda\times\alpha=\bigcup_{\gamma<\lambda}(\gamma\times\alpha)$である。補題 4.3と帰納の仮定により$\operatorname{ot}(\lambda\times\alpha)$は$\{\alpha\cdot\gamma\mid\gamma<\lambda\}$の最小上界であり、命題 4.2 (2)によりこれは$\alpha\cdot\lambda$である。▨