第IV章 演習問題 [16]

第3節で絶対性を証明したいろいろな式のうち, 定理3.9と定理3.11に挙げられているものについては, \(\mathrm{ZF}^{-}-\mathrm{P}-\mathrm{Inf}\) において \(\mathit\Delta_0\)-式との同値性が確立している(→演習問題[12]の解答). こうしたものについては, もとの \(\mathit\Delta_0\) 式に出現しない変数について無駄に量化して \(\mathit\Sigma_1\) 式と \(\mathit\Pi_1\) 式に書き替えるという自明な仕方で \(\vdash_{\mathrm{ZF}-\mathrm{P}}\mathit\Delta_1\) であることがわかる. 定理5.1にあらわれる式についても同様である.

補題3.10に対応する結果はつぎのようになるだろう:

補題 式 \(\phi(x_1,\ldots,x_n)\) が \(\vdash_{\mathrm{ZF}-\mathrm{P}}\mathit\Delta_1\) であり, 関数 \(G_i(y_1,\ldots,y_m)\) \((i=1,\ldots,n)\) がいずれも \(\vdash_{\mathrm{ZF}-\mathrm{P}}\mathit\Delta_1\) であるならば, \(\phi\) に \(G_i\) を代入した式 \[ \phi(G_1(y_1,\ldots,y_m),\ldots,G_n(y_1,\ldots,y_m)) \] もまた \(\vdash_{\mathrm{ZF}-\mathrm{P}}\mathit\Delta_1\) である.

【証明】 記法の簡略化のため \(m=n=1\) の場合をやるが, 他の場合もまったく同様. \(\mathrm{ZF}-\mathrm{P}\) のもとで \(\forall x(\phi\leftrightarrow\phi_\Sigma\leftrightarrow\phi_\Pi)\) が証明できるような \(\mathit\Sigma_1\) 式 \(\phi_\Sigma\) と \(\mathit\Pi_1\) 式 \(\phi_\Pi\) があったとする. また, \(\mathrm{ZF}-\mathrm{P}\) のもとで \(\forall x\forall y(x=G(y)\leftrightarrow\psi_\Sigma\leftrightarrow\psi_\Pi)\) が証明できるような \(\mathit\Sigma_1\) 式 \(\psi_\Sigma\) と \(\mathit\Pi_1\) 式 \(\psi_\Pi\) があったとする. ここで関数の定義に関する規約によって \[ \mathrm{ZF}-\mathrm{P}\vdash \forall y\exists !x\psi_\Sigma(y,x) \]となっているものとする. このとき, \[ \begin{align} \phi(G(y))\;\leftrightarrow\;&\exists x\big[\, \psi_\Sigma(y,x)\land \phi_\Sigma(x) \,\big]\\ \;\leftrightarrow\;&\forall x\big[\, (\neg\psi_\Sigma(y,x))\lor \phi_\Pi(x) \,\big] \tag{$\triangle$} \end{align} \]が \(\mathrm{ZF}-\mathrm{P}\) において証明可能である. \(\mathit\Sigma_1\) 式の否定 \(\neg\psi_\Sigma\) は \(\mathit\Pi_1\) 式に論理的に同値であるから, \((\triangle)\) は \(\phi(G(y))\) が \(\vdash_{\mathrm{ZF}-\mathrm{P}}\mathit\Delta_1\) であることを示している. (証明終)

つぎに第5節について. 定理5.1については上に述べたとおりである. それ以外に特筆すべきものについて述べよう.

定理5.3について 本文(定理5.3の証明)に述べられたとおり, \(x\) が有限集合であることは, ある関数 \(f\) が存在して云々, という式 \(\exists f\phi(x,f)\) で書ける. この \(\phi(x,f)\) は \(\mathit\Sigma_1\) 式(と \(\mathrm{ZF}-\mathrm{P}\) において同値)である. そこで, \(x\) が有限集合であることを意味する \(\exists f\phi(x,f)\) も \(\mathit\Sigma_1\) 式で書ける. つぎに, 定理5.3の証明の論法によって, 直積をつくる操作と対をつくる操作と和集合のもとで閉じていて \(x\) と \(\omega\) を含むような任意の推移的集合 \(M\) に対して \(\exists f\phi(x,f)\) が絶対的であることがわかる. そのような推移的集合の存在を示すには, まず \(M_0=\{x,\omega\}\) とし, \(\mathrm{tr\,cl}(M_{2n})\) を \(M_{2n+1}\), とし, \(M_{2n-1}\) の, 直積と対と和集合の演算のもとでの閉包を \(M_{2n}\) として, \(M=\bigcup_{n\in\omega}M_n\) とすればよい. この構成は \(\mathrm{ZF}-\mathrm{P}\) の範囲内で実行可能であるから, \(\exists f\phi(x,f)\) は 《\(x\) と \(\omega\) を含み推移的で直積と対と和集合のもとで閉じた任意の集合 \(M\) について \((\exists f\phi(x,f))^M\)》という \(\mathit\Pi_1\) 式と \(\mathrm{ZF}-\mathrm{P}\) において同値である. \(A^n\) や \(A^{<\omega}\) についても同様. (この論法は次の演習問題[17]でより一層拡張される.)

定理5.4について \(R\) が \(A\) を全順序づけするという式は次のように \(\mathit\Delta_0\) 式で書ける: \[ \begin{align} &\forall x\in A\big[\,\langle x,x\rangle\notin R\,\big]\\ \land\;&\forall x\in A\forall y\in A\big[\,x=y\lor \langle x,y\rangle\in A\lor \langle y,x\rangle\in A\,\big] \\ \land\;&\forall x\in A\forall y\in A\forall z\in A\big[\,\langle x,y\rangle\notin A\lor \langle y,z\rangle\notin A\lor \langle x,z\rangle\in A\,\big]. \end{align} \]この式を \(\phi_0\) としよう. すると, \(R\) が \(A\) を整列順序づけするという式は \[ \phi_0\land\forall X\big[\,X\neq0\land X\subset A\,\rightarrow\,\exists a\in X\forall x\in X(x=a\lor \langle a,x\rangle\in R)\,\big] \]と書けるから \(\mathit\Pi_1\) 式と同値である. また同じことを \[ \phi_0\land\exists\alpha\exists f\big[\,\alpha\in\mathbf{ON}\land f:A\to \alpha\land \forall x,y\in A(\langle x,y\rangle\in R\rightarrow f(x)<f(y))\,\big] \]とも書ける. ここで \(\mathbf{ON}\) は \(\mathrm{ZF}-\mathrm{P}\) のもとで\(\mathit\Delta_0\) で書けるクラスであるから, \([~~]\) 内は \(\mathit\Delta_0\) で書けており, 上の式は \(\mathit\Sigma_1\) 式と同値である. したがって, \(R\) が \(A\) を整列順序づけするという内容をあらわす式は \(\vdash_{\mathrm{ZF}-\mathrm{P}}\mathit\Delta_1\) である.

つぎに順序型 \(\mathrm{type}(A,R)\) について考えよう. \(R\) が \(A\) を整列順序づけすると仮定すると, 上で整列順序づけが \(\mathit\Sigma_1\) であることを示した式の \(\exists f\) 以下の部分が \(\mathrm{type}(A,R)\leq \alpha\) であることを示す \(\mathit\Sigma_1\) 式になっている. また, 関数の定義域と終域を入れかえて \[ \exists g\Big[\,g:\alpha\to A\land \forall \xi,\eta\in\alpha\big(\,\xi<\eta\rightarrow\langle g(\xi),g(\eta)\rangle\in R\,\big)\Big] \]と書けば, \(\mathrm{type}(A,R)\geq\alpha\) を意味する \(\mathit\Sigma_1\) 式が得られる. そこで, \(\alpha=\mathrm{type}(A,R)\) は \(\mathit\Sigma_1\) で書けることがわかる. あとは \(R\) が \(A\) を整列順序づけすることが \(\vdash_{\mathrm{ZF}-\mathrm{P}}\mathit\Delta_1\) であることと, \(\mathrm{ZF}-\mathrm{P}\) においてすべての整列順序が順序型をもつことを利用して, \[ \alpha=\mathrm{type}(A,R)\;\leftrightarrow\; \forall\beta\Big[\,(R\text{ wellorders }A)\land\big(\,\beta\neq\mathrm{type}(A,R)\lor\beta=\alpha\,\big)\,\Big] \]が言えるので, \(\alpha=\mathrm{type}(A,R)\) が \(\mathit\Pi_1\) でも書けることがわかる.

定理5.5について 証明を見ればわかるとおり, \(\alpha+1\) と \(\alpha-1\) は \(\mathit\Delta_0\) 式で表現できる. つぎに, \(\alpha+\beta\) は集合 \((\{0\}\times\alpha)\cup(\{1\}\times\beta)\) 上の辞書式順序づけの順序型, \(\alpha\cdot\beta\) は \(\beta\times\alpha\) の辞書式順序づけの順序型である. いま順序 \(\langle A_0,R_0\rangle\) と \(\langle A_1,R_1\rangle\) の直積 \(A_0\times A_1\) 上の辞書式順序づけは, \[ \langle a_0,a_1\rangle <_{\mathrm{lex}} \langle b_0,b_1\rangle \;\leftrightarrow\; \langle a_0,b_0\rangle\in R_0 \lor \big(\,a_0=b_0\land \langle a_1,b_1\rangle\in R_1\,\big) \]である. したがって \(R_0\) と \(R_1\) が \(\mathit\Delta_0\) であればこれも \(\mathit\Delta_0\) で書ける. また, 演習問題[12]と定理3.9により, 二つの集合の直積や和集合をつくる演算はいずれも(\(\mathrm{ZF}^{-}-\mathrm{P}-\mathrm{Inf}\) のもとで) \(\mathit\Delta_0\) で書ける. さて, \(\mathit\Delta_0\) 式で定義された演算の合成は必ずしも \(\mathit\Delta_0\) ではない(→演習問題[13])が, 上で述べたとおりそれらは \(\vdash_{\mathrm{ZF}-\mathrm{P}}\mathit\Delta_1\) にはなる. そこで, \[ \begin{gather} \alpha+\beta = \mathrm{type}((\{0\}\times\alpha)\cup(\{1\}\times\beta), {<}_{\mathrm{lex}}), \\ \alpha\cdot\beta = \mathrm{type}(\beta\times\alpha,{<}_{\mathrm{lex}}) \end{gather} \]によって定まる \(\alpha+\beta\) と \(\alpha\cdot\beta\) も \(\vdash_{\mathrm{ZF}-\mathrm{P}}\mathit\Delta_1\) である.

**注意** これ以降の議論では, \(\mathrm{ZF}-\mathrm{P}\) では済まず, 第III章演習問題[18]で導入された公理図式 \(\mathrm{AR}^*\) を必要とする. すなわち, 定理5.6と定理5.7で証明された絶対性を, それらの式が \(\vdash_{\mathrm{ZF}^*-\mathrm{P}}\mathit\Delta_1\) であるという主張へと精密化する. もちろん, 本来はそれらが \(\vdash_{\mathrm{ZF}-\mathrm{P}}\mathit\Delta_1\) であることが求められているが, そのことが可能であるかどうか, いまのところ解答者にはわからない.

定理5.6について ここでは, \(\vdash_{\mathrm{ZF}^*-\mathrm{P}}\mathit\Delta_1\) であるようなクラスの全体が関係 \(\in\) に関する超限再帰的定義のもとで閉じているというメタ定理を証明する. つまり, 関数 \(\mathbf{F}:\mathbf{V}\times\mathbf{V}\to\mathbf{V}\) が \(\vdash_{\mathrm{ZF}^*-\mathrm{P}}\mathit\Delta_1\) であるという仮定のもとで, 超限再帰的定義 \[ \mathbf{G}(x)=\mathbf{F}(x,\mathbf{G}\restriction x) \]によって定まる関数 \(\mathbf{G}:\mathbf{V}\to\mathbf{V}\) もやはり \(\vdash_{\mathrm{ZF}^*-\mathrm{P}}\mathit\Delta_1\) であることを証明する. そのために第III章定理5.3の証明を分析する必要がある. あとで次の補題が必要になる

式 \(\phi(g,d)\) を, 関数 \(g\) は \(d\)-近似である, という意味をもつ式とする. すなわち, \(d\) は推移的集合であり, \(g\) は関数であってその定義域は \(d\) であり, しかも \[ \forall x\in d\Big[\;g(x)=\mathbf{F}(x,g\restriction x)\;\Big]\tag{1} \]となる, ということを意味する式だとする. ここで \(g\restriction x\) は \[ y=g\restriction x\;\leftrightarrow\; \forall z\in x\forall w\in g\big(\,z=(w)_0\,\rightarrow\,w\in y\,\big) \land \forall w\in y\exists z\in x\big(\,z=(w)_0\land w\in g\,\big) \]( \((w)_0\) については演習問題[12]の解答を見なさい.) と \(\mathit\Delta_0\) 式で書ける.

ここで式(1)が \(\mathit\Sigma_1\) 式と同値であることを示そう. 関数 \(\mathbf{F}\) が \(\vdash_{\mathrm{ZF}^*-\mathrm{P}}\mathit\Delta_1\) であるという仮定により, 式 \(g(x)=\mathbf{F}(x,g\restriction x)\) は \(\mathit\Sigma_1\) で書ける. そこで \(\mathit\Delta_0\) 式 \(\theta\) を \[ \forall x\forall g\Big[\;g(x)=\mathbf{F}(x,g\restriction x)\;\leftrightarrow\; \exists w_1\cdots\exists w_n\,\theta(x,g,w_1,\ldots,w_n)\;\Big] \]となるようにとろう. ここで集合 \(w=\{w_1,\ldots,w_n\}\) を考えることにより, \[ \exists w_1\cdots\exists w_n\,\theta(x,g,w_1,\ldots,w_n)\;\leftrightarrow\; \exists w\exists w_1\in w\cdots \exists w_n\in w\,\theta(x,g,w_1,\ldots,w_n) \]という同値性がわかるから, 最初から有界でない量化は高々一つだけで, もともと \[ g(x)=\mathbf{F}(x,g\restriction x)\;\leftrightarrow\; \exists w\,\theta(x,g,w) \]となっているものと仮定して差し支えない. このとき式(1)は \[ \forall x\in d\,\exists w\,\theta(x,g,w) \]となる. 第III章演習問題[18]の公理図式 (いわゆる収集公理) \[ \forall x\in d\,\exists w\,\theta(x,g,w)\;\rightarrow\;\exists y\,\forall x\in d\,\exists w\in y\,\theta(x,g,w)\tag{AR*} \] によって, この式は \[ \exists y\,\forall x\in d\,\exists w\in y\,\theta(x,g,w) \]と同値である. いいかえれば, 式(1)はこの \(\mathit\Sigma_1\) 式と同値である.

さて, (1)が \(\mathit\Sigma_1\) で書けることがわかったので, 結果として \(\phi(g,d)\) も \(\mathit\Sigma_1\) 式であるとして差し支えない. 再帰的に定義された関数 \(\mathbf{G}(x)\) については \(d\) 近似 \(g\) の存在と一意性(→第III章定理5.6)によって \[ \begin{align} y=\mathbf{G}(x)\;\leftrightarrow\;& \exists g\exists d\Big[\,x\in d\land \phi(x,d)\land y=g(x)\,\Big]\\ \;\leftrightarrow\;& \forall g\forall d\Big[\,x\in d\land \phi(x,d)\,\rightarrow\, y=g(x)\,\Big] \end{align} \]となる. このことから \(\mathbf{G}\) が \(\vdash_{\mathrm{ZF}^*-\mathrm{P}}\mathit\Delta_1\) であることがわかる. 第III章定理5.6は \(\mathrm{ZF}^{-}-\mathrm{P}\) で証明されていたが, ここでは関係 \(\in\) が整礎的であることと, 収集の公理図式 \(\mathrm{AR}^*\) を利用するので \(\mathrm{ZF}^*-\mathrm{P}\) が必要である. いっぽう \(\mathbf{G}\) の定義域は \(\mathit\Sigma_1\) 式で定義される推移的クラス \(\mathbf{A}\) に置き換えることができる. そのためには \(\phi(g,d)\) に \(d\subset\mathbf{A}\) という条項を追加すればよい.

定理5.7について これらの演算はいずれも, 整礎的関係 \(\in\) に関する超限再帰的定義で得られる. つまり, \[ \begin{gather} \alpha^\beta = \bigcup\{\,\alpha^\gamma\cdot \alpha\,:\,\gamma<\beta\,\},\\ \mathrm{rank}(x)=\bigcup\{\,\mathrm{rank}(y)+1\,:\,y\in x\,\},\\ \mathrm{tr\,cl}(x)=x\cup \bigcup\{\,\mathrm{tr\,cl}(y)\,:\,y\in x\,\} \end{gather} \]となっている. これらの再帰的定義の右辺はいずれも \(\mathit\Delta_0\) 式で定義可能な演算の組合せで得られるので \(\vdash_{\mathrm{ZF}^*-\mathrm{P}}\mathit\Delta_1\) である. したがって定理5.6について上に述べたところにより, 順序数の冪 \(\alpha^\beta\) も階数 \(\mathrm{rank}(x)\) も推移閉包 \(\mathrm{tr\,cl}(x)\) も \(\vdash_{\mathrm{ZF}^*-\mathrm{P}}\mathit\Delta_1\) である.

冪集合の公理を含む \(\mathrm{ZF}\) においては \(\mathrm{AR}^*\) は置換公理 \(\mathrm{AR}\) に置き換えることができますが, 超限再帰的定義についての上記の議論が \(\mathrm{ZF}-\mathrm{P}\) でできるかどうかが気になるところです.

解答者: 藤田 博司 (公開日: 2011年6月24日)
2011年6月26日更新: ARのことを間違えてAFと書いていたのを修正

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

演習問題一覧に戻る