※このエントリの内容は古くなっています。より簡明な証明が
関数の超限再帰的定義・改の改 - y_bonten's blog
にあります。
前エントリの\(\psi_\alpha(f)\)における\(f\)の定義域を「\(\alpha\)未満」から「\(\alpha\)以下」に変更し、証明を簡素化したものを示す。
任意の集合\(x\)の各々に対し、ただひとつの集合\(G(x)\)を与える規則\(G\)が与えられている*1。順序数\(\alpha\)ごとに、条件\(\psi_\alpha(f)\)を「\(f\)は『\(\alpha\)以下の順序数全体』を定義域とする関数であり、任意の\(\beta\in{\rm dom}f\)について\(f(\beta)=G(f\upharpoonright_{ < \beta})\)が成り立つ」と定義する。
【補題】\(\mu,\nu\)は\(\nu\leq\mu\)を満たす順序数であり、\(f_\mu,f_\nu\)はそれぞれ\(\psi_\mu,\psi_\nu\)を満たしている。\(\psi_\nu\)を満たすものが\(f_\nu\)のほかに存在しないとき、\(f_\mu(\nu)=f_\nu(\nu)\)である。
（証明）\(f_\mu\upharpoonright_{\leq\nu}\)は\(\psi_\nu\)を満たしているので\(f_\nu\)に一致する。すると\(f_\mu(\nu)=f_\mu\upharpoonright_{\leq\nu}(\nu)=f_{\nu}(\nu)\)となる。■
【定理】\(\psi_\alpha\)を満たすものは\(\alpha\)ごとに一意に存在する。
（証明）超限帰納法による。\(\gamma < \alpha\)なる任意の\(\gamma\)の各々に対し、\(f_\gamma\)は\(\psi_\gamma\)を満たす唯一のものであると仮定する。\(\displaystyle h=\bigcup_{\gamma < \alpha}f_\gamma\)とおけば、これは置換公理と和集合公理により集合をなす。さらに\(f=h\cup\{\langle\alpha,G(h)\rangle\}\)を作り、これが\(\psi_\alpha\)を満たすことを示す。補題により、\(f\)は「\(\alpha\)以下の順序数全体」を定義域とする関数になっており、\(\beta < \alpha\)における\(f(\beta)\)の値は\(f_\beta(\beta)\)となることが分かる。これは\(f_\beta\)が\(\psi_\beta\)を満たすことから\(G(f_\beta\upharpoonright_{ < \beta})\)に等しく、さらに\(f_\beta=f\upharpoonright_{\leq\beta}\)となっていることから\(G(f\upharpoonright_{ < \beta})\)と書き直せる。また\(\beta=\alpha\)のときの\(f(\beta)\)の値は\(G(h)\)であるが、これも\(h=f\upharpoonright_{ < \alpha}\)により\(G(f\upharpoonright_{ < \alpha})\)と書き直せる。以上により、\(f\)は\(\psi_\alpha\)を満たす。
次に一意性を示すため、\(\psi_\alpha(f')\)を仮定して\(f'=f\)を導く。任意の\(\gamma < \alpha\)をとれば、\(f'\upharpoonright_{\leq\gamma}\)と\(f\upharpoonright_{\leq\gamma}\)はともに\(\psi_\gamma\)を満たすから、帰納法の仮定により両者は一致し、特に\(f'(\gamma)=f(\gamma)\)となる。これが任意の\(\gamma < \alpha\)について成り立つことから\(f'\upharpoonright_{ < \alpha}=f\upharpoonright_{ < \alpha}\)である。両辺に\(G\)を施せば\(f'(\alpha)=f(\alpha)\)も言えるから、\(f'=f\)である。■
任意の順序数の各々\(\alpha\)に対し、\(\psi_\alpha\)を満たす唯一のものを改めて\(f^*_\alpha\)と書くことにする。
【定理】順序数\(\alpha\)に対し\(f^*_\alpha(\alpha)\)を与える規則を\(F\)とすれば、\(F(\alpha)=G(F\upharpoonright_{ < \alpha})\)が成り立つ。ここで\(F\upharpoonright_{ < \alpha}\)とは\(\{\langle\gamma,F(\gamma)\rangle:\gamma < \alpha\}\)を意味し、これは置換公理により集合をなしている。
（証明）任意の順序数\(\alpha\)をとる。補題により、任意の\(\gamma < \alpha\)について\(f^*_\alpha(\gamma)=f^*_\gamma(\gamma)=F(\gamma)\)となる、つまり\(f^*_\alpha\upharpoonright_{ < \alpha}=F\upharpoonright_{ < \alpha}\)である。したがって\(F(\alpha)=f^*_\alpha(\alpha)=G(f^*_\alpha\upharpoonright_{ < \alpha})=G(F\upharpoonright_{ < \alpha})\)となる。■
*1:規則\(G\)の実体は、\(\forall x\exists!y[G(x,y)]\)を満たす述語\(G(x,y)\)である。
