Cantor標準形

2 の積：$\alpha>0$ とし、$\beta<\gamma$ ならば $\alpha\beta<\alpha\gamma$ を $\gamma$ についての帰納法で示す。$\gamma=\delta+1$ なら $\beta\le\delta$ で、帰納法の仮定（または $\beta=\delta$）から $\alpha\beta\le\alpha\delta<\alpha\delta+\alpha=\alpha\gamma$（和の狭義単調性と $\alpha>0$）。$\gamma$ が極限なら $\beta+1<\gamma$ なので $\alpha\beta<\alpha\beta+\alpha=\alpha(\beta+1)\le\sup_{\delta<\gamma}\alpha\delta=\alpha\gamma$。

2 の冪：まず $\alpha>0$ ならすべての $\delta$ で $\alpha^\delta>0$（帰納法。後続の段は積の狭義単調性から $\alpha^\delta\alpha>\alpha^\delta\cdot0=0$、極限の段は $\alpha^\delta\ge\alpha^0=1$）。$\alpha>1$ とし、$\gamma=\delta+1$ なら $\alpha^\delta=\alpha^\delta\cdot1<\alpha^\delta\cdot\alpha=\alpha^\gamma$ と帰納法の仮定から $\alpha^\beta<\alpha^\gamma$。極限の段は積の場合と同じ。

3：$\alpha=1$ なら両辺とも $1$ なので、$\alpha>1$ とする（$\alpha=0$ では $0^{1+\omega}=0^\omega=\sup\{1,0,0,\dots\}=1$ だが $0^1\cdot0^\omega=0$ となり、等式は成り立たない）。$\gamma=0$ では両辺 $\alpha^\beta$。$\gamma=\delta+1$ なら $\alpha^{\beta+\delta+1}=\alpha^{\beta+\delta}\alpha=\alpha^\beta\alpha^\delta\alpha=\alpha^\beta\alpha^{\delta+1}$（積の結合法則）。$\gamma$ が極限なら $\beta+\gamma=\sup_{\delta<\gamma}(\beta+\delta)$ も極限で、$\{\beta+\delta\mid\delta<\gamma\}$ は $\beta+\gamma$ 未満の順序数の中で共終だから、$\alpha^{\beta+\gamma}=\sup_{\delta<\gamma}\alpha^{\beta+\delta}=\sup_{\delta<\gamma}\alpha^\beta\alpha^\delta=\alpha^\beta\cdot\sup_{\delta<\gamma}\alpha^\delta=\alpha^\beta\alpha^\gamma$。3 番目の等号は積の第 2 引数についての連続性（$\{\alpha^\delta\mid\delta<\gamma\}$ は極限順序数 $\alpha^\gamma$ の中で共終で、$\alpha^\beta\cdot x$ は $x$ について単調）による。

4：$f(\beta)<\beta$ となる最小の $\beta$ があったとすると、$\beta':=f(\beta)<\beta$ について $f(\beta')< f(\beta)=\beta'$ となり最小性に反する。$\alpha^\beta$ は 2 により $\beta$ について狭義単調増加である。$\square$

存在。$\alpha\ge1$ なので $\alpha\cdot(\gamma+1)\ge\gamma+1>\gamma$（lem-cnf-laws の 4）。よって $\alpha\cdot\delta'>\gamma$ となる最小の $\delta'$ がある。$\alpha\cdot0=0\le\gamma$ なので $\delta'\neq0$ である。$\delta'$ が極限なら $\alpha\cdot\delta'=\sup_{\delta<\delta'}\alpha\cdot\delta\le\gamma$ となり矛盾するので、$\delta'=\delta+1$ と書ける。このとき $\alpha\cdot\delta\le\gamma<\alpha\cdot\delta+\alpha$ であり、lem-cnf-laws の 1 から $\alpha\cdot\delta+\rho=\gamma$ となる $\rho$ がとれる。和の狭義単調性から $\rho<\alpha$ である。

一意性。$\alpha\delta+\rho=\alpha\delta'+\rho'$、$\rho,\rho'<\alpha$、$\delta<\delta'$ とすると、$\alpha\delta'\ge\alpha(\delta+1)=\alpha\delta+\alpha>\alpha\delta+\rho$ なので $\alpha\delta'+\rho'\ge\alpha\delta'>\alpha\delta+\rho$ となり矛盾する。よって $\delta=\delta'$ で、和の左からの簡約（狭義単調性）により $\rho=\rho'$ である。$\square$

lem-cnf-laws の 4 より $\beta^{\gamma+1}\ge\gamma+1>\gamma$ なので、$\beta^{\varepsilon'}>\gamma$ となる最小の $\varepsilon'$ がある。$\beta^0=1\le\gamma$ より $\varepsilon'\ne0$ であり、$\varepsilon'$ が極限なら $\beta^{\varepsilon'}=\sup_{\varepsilon<\varepsilon'}\beta^\varepsilon\le\gamma$ となって矛盾する。よって $\varepsilon'=\varepsilon+1$ で、$\varepsilon$ が求める最大の指数である（$\beta^\eta$ は $\eta$ について狭義単調）。$\square$

$n$ についての帰納法で示す。$n=1$ なら $\gamma=\beta^{\varepsilon_1}\delta_1$ で、積の狭義単調性から $\gamma<\beta^{\varepsilon_1}(\delta_1+1)$ である。$n\ge2$ のとき、残りの和 $\tau:=\beta^{\varepsilon_2}\delta_2+\cdots+\beta^{\varepsilon_n}\delta_n$ は展開なので、帰納法の仮定から $\tau<\beta^{\varepsilon_2+1}\le\beta^{\varepsilon_1}$（$\varepsilon_2+1\le\varepsilon_1$）である。和の結合法則から $\gamma=\beta^{\varepsilon_1}\delta_1+\tau$ で、$$\beta^{\varepsilon_1}\delta_1\le\beta^{\varepsilon_1}\delta_1+\tau<\beta^{\varepsilon_1}\delta_1+\beta^{\varepsilon_1}=\beta^{\varepsilon_1}(\delta_1+1)$$である（左分配法則）。最後に $\delta_1<\beta$ より $\delta_1+1\le\beta$ なので、積の単調性から $\beta^{\varepsilon_1}(\delta_1+1)\le\beta^{\varepsilon_1}\beta=\beta^{\varepsilon_1+1}$ である。$\square$

共通の始めの部分の和を $\pi$ とし、残りを $\tau,\tau'$ とすると、和の結合法則から $\gamma=\pi+\tau$、$\gamma'=\pi+\tau'$ である。和の左からの狭義単調性により、$\gamma<\gamma'$ と $\tau<\tau'$ は同値である。1 の場合は $\tau=0<\tau'$ である。2 の場合、$\varepsilon_i<\varepsilon'_i$ なら lem-cnf-bound から $\tau<\beta^{\varepsilon_i+1}\le\beta^{\varepsilon'_i}\le\tau'$、$\varepsilon_i=\varepsilon'_i$ かつ $\delta_i<\delta'_i$ なら $\tau<\beta^{\varepsilon_i}(\delta_i+1)\le\beta^{\varepsilon_i}\delta'_i\le\tau'$ である。逆に、1・2 のどちらでもなければ、二つの列を入れ替えた 1・2 のどちらかが成り立つ（thm-cnf-main より $\gamma\ne\gamma'$ なら列は異なる）ので $\gamma'<\gamma$ または $\gamma=\gamma'$ である。$\square$

$\varepsilon<\varepsilon'$ なので $\varepsilon+\eta=\varepsilon'$ となる $\eta\ge1$ があり、$1+\eta''=\eta$ となる $\eta''$ をとると、lem-cnf-laws の 3 から $\omega^{\varepsilon'}=\omega^\varepsilon\cdot\omega^\eta$、$\omega^\eta=\omega\cdot\omega^{\eta''}$ である。$\zeta:=\omega^{\eta''}\ge1$ として $1+\zeta''=\zeta$ とすると $\omega\zeta=\omega+\omega\zeta''$（左分配法則）であり、$k+\omega=\sup_n(k+n)=\omega$ なので$$k+\omega^\eta=k+\omega+\omega\zeta''=\omega+\omega\zeta''=\omega^\eta .$$よって $\omega^\varepsilon k+\omega^{\varepsilon'}=\omega^\varepsilon k+\omega^\varepsilon\omega^\eta=\omega^\varepsilon(k+\omega^\eta)=\omega^\varepsilon\omega^\eta=\omega^{\varepsilon'}$ である。

和の公式：$\alpha'=\omega^{\beta'_1}k'_1+\sigma$ とし、$i>r$ の項 $\omega^{\beta_i}k_i$（$\beta_i<\beta'_1$）を右から順に $\omega^{\beta'_1}$ に吸収させる。和の結合法則により $\omega^{\beta_i}k_i+\omega^{\beta'_1}k'_1=(\omega^{\beta_i}k_i+\omega^{\beta'_1})+\omega^{\beta'_1}(k'_1-1)=\omega^{\beta'_1}k'_1$ なので、$i>r$ の項はすべて消える。$\beta_r=\beta'_1$ なら $\omega^{\beta'_1}k_r+\omega^{\beta'_1}k'_1=\omega^{\beta'_1}(k_r+k'_1)$（左分配法則）である。指数は狭義に減少しているので、右辺は標準形である。$\square$

1：$\beta_1=\alpha$ なら $\alpha\le\omega^\alpha=\omega^{\beta_1}\le\alpha$ より $\omega^\alpha=\alpha$。逆に $\omega^\alpha=\alpha$ なら $\alpha=\omega^\alpha\cdot1$ が標準形であり、一意性から $\beta_1=\alpha$ である。

2：$\varepsilon_0$ は狭義増加列 $\tau_n$ の上限なので極限順序数であり、冪の連続性から $\omega^{\varepsilon_0}=\sup_n\omega^{\tau_n}=\sup_n\tau_{n+1}=\varepsilon_0$ である。$\varepsilon$ を任意の $\varepsilon$ 数とする。自然数 $m$ について $\omega^m\ne m$（$m=0$ なら $\omega^0=1$、$m\ge1$ なら $\omega^m\ge\omega>m$）なので $\varepsilon\ge\omega=\tau_0$ であり、$\tau_n\le\varepsilon$ なら $\tau_{n+1}=\omega^{\tau_n}\le\omega^\varepsilon=\varepsilon$ である。よって $\varepsilon_0\le\varepsilon$。後半は 1 と $\beta_1\le\alpha$ から、指数はすべて $\beta_1$ 以下だからである。

3：すべての $\gamma$ について $\lvert\omega^\gamma\rvert\le\max(\aleph_0,\lvert\gamma\rvert)$ であることを $\gamma$ についての帰納法で示す。$\omega^0=1$ である。$\omega^{\gamma+1}=\omega^\gamma\cdot\omega$ は $\omega\times\omega^\gamma$ の辞書式順序の順序型なので（順序数 の記事の定義「順序数の算術」）、濃度は $\aleph_0\cdot\lvert\omega^\gamma\rvert\le\max(\aleph_0,\lvert\gamma\rvert)$ である。極限 $\gamma$ では $\omega^\gamma=\bigcup_{\delta<\gamma}\omega^\delta$ は、濃度 $\max(\aleph_0,\lvert\gamma\rvert)$ 以下の集合 $\lvert\gamma\rvert$ 個の和集合なので、濃度は $\max(\aleph_0,\lvert\gamma\rvert)$ 以下である（Kun80 Ch. I の Lemma 10.21、p. 30）。さて $\gamma<\kappa$ なら $\lvert\gamma\rvert<\kappa$ で、$\kappa$ は非可算なので $\lvert\omega^\gamma\rvert<\kappa$ であり、$\kappa$ は基数だから $\omega^\gamma<\kappa$ である。よって $\omega^\kappa=\sup_{\gamma<\kappa}\omega^\gamma\le\kappa$ であり、lem-cnf-laws の 4 と合わせて $\omega^\kappa=\kappa$ である。$\square$

段 1：$o_b$ は狭義単調増加。$m< m'$ ならば $o_b(m)< o_b(m')$ であることを $m'$ についての強い帰納法で示す。指数 $e< m'$ については帰納法の仮定から $o_b$ は狭義単調なので、$o_b(m)$・$o_b(m')$ の表示の指数は狭義に減少し、係数は $b$ 未満の正の自然数であるから、どちらも Cantor 標準形である。自然数の演算は順序数の演算と一致するので、$m$ と $m'$ の底 $b$ の展開に thm-cnf-compare を当てられる。初めて異なる位置で、指数が $e< e'$ なら $o_b(e)< o_b(e')$、指数が等しく係数が $c< c'$ なら同じ係数の不等式が、$o_b(m)$ と $o_b(m')$ の標準形の同じ位置に現れる。もう一度 thm-cnf-compare を当てて $o_b(m)< o_b(m')$ を得る。

段 2：$o_{b+1}(B_b(m))=o_b(m)$。$m$ についての強い帰納法で示す。$m=\sum b^{e_i}c_i$ とすると、帰納法の仮定から $o_{b+1}(B_b(e_i))=o_b(e_i)$ で、段 1 よりこれは $i$ について狭義減少する。$o_{b+1}$ は（段 1 により）単調なので $B_b(e_1)>\cdots>B_b(e_r)$ であり、係数は $c_i< b< b+1$ である。したがって $B_b(m)=\sum(b+1)^{B_b(e_i)}c_i$ は底 $b+1$ の展開そのものであり、$o_{b+1}(B_b(m))=\sum\omega^{o_{b+1}(B_b(e_i))}c_i=\sum\omega^{o_b(e_i)}c_i=o_b(m)$ である。

段 3：順序数の降下列。$\alpha_k:=o_{k+2}(G_k)$ とおく。$G_k>0$ なら、段 1・段 2 から$$\alpha_{k+1}=o_{k+3}\bigl(B_{k+2}(G_k)-1\bigr)< o_{k+3}\bigl(B_{k+2}(G_k)\bigr)=o_{k+2}(G_k)=\alpha_k$$である。順序数の狭義減少列は有限の長さしかもたないので、ある $k$ で $G_k=0$ となる。$\square$