まずなにより, \(\triangleleft\) が \(F(\alpha,\beta)\) を整列順序づけすることを証明しないといけない.
定義から \(f\not\!\triangleleft f\) と \(f=g\lor f\triangleleft g\lor g\triangleleft f\) は明らかだろう. 推移律を示すため, \(f\triangleleft g\land g\triangleleft h\) だったと仮定しよう. \(f(\xi)\neq g(\xi)\) となる最大の \(\xi\) を \(\xi_{f,g}\) と書こう. \(\xi_{g,h}\) と \(\xi_{f,h}\) も同様に定義する. もしも \(\xi_{f,g}=\xi_{g,h}\) なら \(\xi_{f,h}=\xi_{f,g}\) で
\[
f(\xi_{f,h})=f(\xi_{f,g})<g(\xi_{f,g})=g(\xi_{g,h})<h(\xi_{g,h})=h(\xi_{f,h})
\]
だから \(f\triangleleft h\) である. \(\xi_{f,g}<\xi_{g,h}\) のときは \(\xi_{f,h}=\xi_{g,h}>\xi_{f,g}\) となり,
\[
f(\xi_{f,h})=f(\xi_{g,h})=g(\xi_{g,h})<h(\xi_{g,h})=h(\xi_{f,h})
\]
だから, やはり \(f\triangleleft h\) である. \(\xi_{f,g}>\xi_{g,h}\) のときも同様にして \(f\triangleleft h\) がわかる.
以上のことからひとまず \(\triangleleft\) が全順序づけであることはわかった. 整列順序づけであることを示すために, \(F(\alpha,\beta)\) に \(\triangleleft\)-無限降下列
\[
\cdots \triangleleft f_{n+1}\triangleleft f_n\triangleleft\cdots
\triangleleft f_1\triangleleft f_0 \tag{0}
\]
が存在しないことを, \(\beta\) に関する超限帰納法で示そう. 帰納法の仮定として \(\beta\) より小さいすべての順序数 \(\beta'\) について \(\triangleleft\) が \(F(\alpha,\beta')\) を整列順序づけするものと仮定する. その一方で \(F(\alpha,\beta)\) に無限降下列(0)が存在したと仮定し, 矛盾に導かれることを示そう.
各番号 \(n\) ごとに, \(f_n(\eta)\neq0\) をみたす最大の \(\eta\) を \(\eta_n\) と書くことにする. \(k>n\) のとき \(f_k\triangleleft f_n\) であることから,
\[
\forall \xi>\eta_n\forall k>n\big(f_k(\xi)=0\big)
\]
である. このことから
\[
\eta_0\geq \eta_1\geq \cdots \geq \eta_n\geq \cdots
\]
となることがわかる. そこで, \(\beta'=\min\{\,\eta_n\,:\,n\in\omega\,\}\) とおけばある番号 \(m\) について
\[
\eta_m=\eta_{m+1}=\eta_{m+2}=\cdots=\beta'
\]
となる. いま \(g_n=f_{m+n}\restriction \beta'\) とおくと, \(\langle g_n\,:\,n\in\omega\rangle\) は集合 \(F(\alpha,\beta')\) における \(\triangleleft\)-無限降下列となっている. ところが \(\beta'<\beta\) であるから, これは帰納法の仮定と矛盾することになる.
こうして \(\langle F(\alpha,\beta),\,\triangleleft\rangle\) が整列順序であることがわかった. いまその順序型を
\[
\alpha\mathbin{\uparrow}\beta
=\mathrm{type}\Big(\big\langle F(\alpha,\beta),\;\triangleleft\big\rangle\Big)
\]
と書いたとしよう. \(F(\alpha,0)\) が空な関数ただ一つからなる集合であることから \(\alpha\mathbin{\uparrow}0=1\) は明らかなので, \(\alpha\mathbin{\uparrow}\beta\) が \(\alpha^\beta\) と一致することを示すために, あとは, 等式
\[
\alpha\mathbin{\uparrow}(\beta+1)=(\alpha\mathbin{\uparrow}\beta)\cdot\alpha\tag{1}
\]
と, 極限順序数 \(\delta\) についての等式
\[
\alpha\mathbin{\uparrow}\delta=\sup_{\beta<\delta}\,\alpha\mathbin{\uparrow}\beta
\tag{2}
\]
を示せばよい. というのも, 超限再帰の定める関数は一意的だから.
(1)の証明: 順序数の積の定義 (→定義7.19) によれば, \((\alpha\uparrow\beta)\cdot\alpha\) は直積集合 \(\alpha\times F(\alpha,\beta)\) に辞書式に順序づけした整列順序の順序型と一致する. いまこの集合の要素 \(\langle \gamma, f\rangle\) \((\gamma<\alpha,~f\in F(\alpha,\beta))\) にに対し, \(g_{\gamma,f}:\beta+1\to\alpha\) を
\[
g_{\gamma,f}(\xi)=\begin{cases}
\gamma\;,&(\xi=\beta),\\
f(\xi)\;,&(\xi<\beta)
\end{cases}
\]
によって定めよう. すると \(g_{\gamma,f}\in F(\alpha,\beta+1)\) であり
\[
\begin{align}
\langle \gamma_0,f_0\rangle<\langle\gamma_1,f_1\rangle
& \leftrightarrow
\gamma_0<\gamma_1\lor(\gamma_0=\gamma_1\land f_0\triangleleft f_1) \\
& \leftrightarrow
g_{\gamma_0}(\beta)<g_{\gamma_1}(\beta)\lor
\big(\,g_{\gamma_0}(\beta)=g_{\gamma_1}(\beta)
\land (g_{\gamma_0}\restriction \beta)
\;\triangleleft\; (g_{\gamma_1}\restriction \beta)\,\big) \\
& \leftrightarrow
g_{\gamma_0}\triangleleft g_{\gamma_1}
\end{align}
\]
であるから, 対応 \(\langle \gamma,f\rangle\mapsto g_{\gamma,f}\) は \(\alpha\times F(\alpha,\beta)\) から \(F(\alpha,\beta+1)\) への順序保存写像になっている. いっぽう, \(F(\alpha,\beta+1)\) の任意の要素 \(g\) に \(\langle g(\beta),g\restriction\beta\rangle\) を対応させれば, これが対応 \(\langle \gamma,f\rangle\mapsto g_{\gamma,f}\) の逆対応になっている. したがって, この対応は \(\alpha\times F(\alpha,\beta)\) の \(F(\alpha,\beta+1)\) の上への順序同型写像であり, \((\alpha\uparrow\beta)\cdot\alpha=\alpha\uparrow(\beta+1)\) となる.
(2)の証明: \(\delta\) を任意の極限順序数とする. \(\beta<\delta\) のとき \(f_\beta:\delta\to\alpha\) を
\[
f_\beta(\xi)=\begin{cases}
0\;,& \xi\neq \beta,\\
1\;,& \xi=\beta,
\end{cases}\tag{3}
\]
と定めよう. あきらかに \(f_\beta\in F(\alpha,\delta\) である. \(F(\alpha,\beta)\) の要素 \(g\) に対して, \(\bar g\) を, \(\xi<\beta\) において \(g\) と一致し \(\beta\leq\xi<\delta\) のとき値ゼロを返すように定めた \(g\) の拡張としよう. すると対応 \(g\mapsto \bar g\) は \(F(\alpha,\beta)\) と \(F(\alpha,\delta)\) の \(f_\beta\) における切片との順序同型を与える. このことから
すべての \(\beta<\delta\) について \(\alpha\uparrow\beta<\alpha\uparrow\delta\) とわかる. こうしてまず
\[
\sup_{\beta<\delta}\;\alpha\uparrow\beta \leq \alpha\uparrow\delta
\]
がわかった.
逆向きの不等式を示すために \(F(\alpha,\delta)\) の要素 \(f\) を任意に固定する. \(f(\eta)\neq0\) となる最大の \(\eta\) を考えると, \(\delta\) が極限順序数であることから \(\eta+1<\delta\) であり, (3)式のように \(f_{\eta+1}\) を定めれば \(f\triangleleft f_{\eta+1}\) となる. そこで, \(f\) の順序数 \(\|f\|\) は \(\|f_{\eta+1}\|\) 未満であるが, 前段で示した同型対応により \(\|f_{\eta+1}\|=\alpha\uparrow(\eta+1)\) であって,
\[
\|f\|<\alpha\uparrow(\eta+1)\leq\sup_{\beta<\delta}\;\alpha\uparrow\beta
\]
となることがわかる. \(F(\alpha,\delta)\) の任意の要素 \(f\) についてこれが成立することから,
\[
\alpha\uparrow\delta\leq\sup_{\beta<\delta}\;\alpha\uparrow\beta
\]
であることがわかる.
この整列性の証明は従属選択原理DCに依存しているんだけど, 本当はZFの範囲内で証明できるんですよね?
この解答に不具合を発見した方はぜひご指摘ください.