第I章 演習問題 [7]

まずなにより, \(\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の範囲内で証明できるんですよね?

解答者: 藤田 博司 (公開日: 2011年5月27日)
2011年5月28日更新: 定義の番号の入れ忘れを修正.
2011年6月6日更新: 証明の方針の言い方を改める.

この解答に不具合を発見した方はぜひご指摘ください.

演習問題一覧に戻る