※このエントリの内容は古くなっています。より簡明な証明が
http://y-bonten.hatenablog.com/entry/2016/05/19/060644
にあります。
任意の集合\(x\)の各々に対し、ただひとつの集合\(G(x)\)を与える規則\(G\)が与えられている。規則\(G\)の実体は、\(\forall x\exists!y[G(x,y)]\)を満たす述語\(G(x,y)\)である。順序数\(\alpha\)ごとに、条件\(\psi_\alpha(f)\)を「\(f\)は\(\alpha\)を定義域とする関数であり、任意の\(\beta < \alpha\)（つまり\(\beta\in{\rm dom}f\)）について\(f(\beta)=G(f\upharpoonright_\beta)\)が成り立つ」と定義する。つまり、関数\(f\)にとって\(G\)は「\(\beta\)未満の『履歴』から\(\beta\)における値を算出する規則」である。
【定理】\(\psi_\alpha\)を満たすものは\(\alpha\)ごとに一意に存在する。
これを証明するために、まず以下の補題を用いて一意性を示す。
【補題A】\(\mu\)を順序数とし、\(f_\mu\)が\(\psi_\mu\)を満たしている。このとき、任意の\(\nu < \mu\)について\(f_\mu\upharpoonright_\nu\)は\(\psi_\nu\)を満たす。
（証明）\(f_\mu\upharpoonright_\nu\)は\(\nu\)を定義域とする関数である。任意の\(\beta < \nu\)をとると、\(f_\mu\upharpoonright_\nu(\beta)=f_\mu(\beta)\)、いっぽう\(G((f_\mu\upharpoonright_\nu)\upharpoonright_\beta)=G(f_\mu\upharpoonright_\beta)\)であり、両者は\(\psi_\mu(f_\mu)\)により等しい。■
【\(f_\alpha\)の一意性】\(\alpha\)を任意の順序数とする。\(\psi_\alpha\)を満たすものは、存在すれば一意である。
（証明）超限帰納法による。\(\gamma < \alpha\)なる任意の\(\gamma\)の各々に対し、\(\psi_\gamma\)を満たすものは高々ひとつしかないと仮定し、さらに\(\psi_\alpha(f_1),\psi_\alpha(f_2)\)を仮定して\(f_1=f_2\)を導く。任意の\(\beta < \alpha\)をとれば、補題Aにより\(f_1\upharpoonright_\beta\)と\(f_2\upharpoonright_\beta\)はともに\(\psi_\beta\)を満たすから、帰納法の仮定により両者は一致する。したがって\(f_1(\beta)=G(f_1\upharpoonright_\beta)=G(f_2\upharpoonright_\beta)=f_2(\beta)\)、これが任意の\(\beta < \alpha\)について成り立つことから\(f_1=f_2\)である。■
この一意性と補題Aから、下の補題Bを導いておき、存在性の証明に備える。
【補題B】\(\mu,\nu\)は\(\nu < \mu\)を満たす順序数であり、\(f_\mu,f_\nu\)はそれぞれ\(\psi_\mu,\psi_\nu\)を満たしている。このとき\(f_\mu
\upharpoonright_\nu=f_\nu\)、したがって\(f_\mu(\nu)=G(f_\nu)\)である。
（証明）補題Aにより\(f_\mu\upharpoonright_\nu\)は\(\psi_\nu\)を満たしているので、上で示した一意性から\(f_\nu\)に一致する。\(\psi_\mu(f_\mu)\)から\(f_\mu(\nu)=G(f_\mu
\upharpoonright_\nu)=G(f_\nu)\)。■
【\(f_\alpha\)の存在性】任意の順序数\(\alpha\)の各々に対し、\(\psi_\alpha\)を満たすものが存在する。
（証明）超限帰納法による。(ア)\(\psi_0(\varnothing)\)が成り立つ。(イ)後続順序数\(\alpha\)に対し、\(\alpha\)のひとつ前の順序数を\(\alpha^-\)とおいて\(\psi_{\alpha^-}(f_{\alpha^-})\)を仮定する。\(f=f_{\alpha^-}\cup\{\langle\alpha^-,G(f_{\alpha^-})\rangle\}\)とおくと、\(f\)は\(\alpha\)を定義域とする関数であり、\(f_{\alpha^-}=f\upharpoonright_{\alpha^-}\)となっているから、\(\psi_\alpha(f)\)が成り立っている。(ウ)極限順序数\(\alpha\)に対し、\(\gamma < \alpha\)なる任意の順序数\(\gamma\)の各々について\(f_\gamma\)が\(\psi_\gamma\)を満たすと仮定する。\(f=\displaystyle\bigcup_{\gamma < \alpha}f_\gamma\)は置換公理と和集合公理により集合をなすが、これが\(\psi_\alpha\)を満たすことを示す。任意の\(\beta < \alpha\)をとると、\(\gamma\leq\beta\)なる\(f_\gamma\)は\(\beta\)を定義域に持たず、\(\beta < \gamma\)なる\(f_\gamma\)については補題Bにより\(f_\gamma(\beta)=G(f_\beta)\)となり、\(\gamma\)の値によらない。したがって\(\langle\beta,y\rangle\in f\)を満たす\(y\)は\(G(f_\beta)\)に限られる。いっぽう\(\alpha\)に属さないものはどの\(f_\gamma\)の定義域にも属さない。以上により、\(f\)は\(\alpha\)を定義域とする関数である。すると\(f_\beta\subset f\)は\(f\)の制限となり、\(f(\beta)=G(f_\beta)=G(f\upharpoonright_\beta)\)が成り立つから、\(f\)は\(\psi_\alpha\)を満たしている。■
一意性・存在性がともに示されたので、任意の順序数の各々\(\alpha\)に対し、\(\psi_\alpha\)を満たす唯一のものを改めて\(f^*_\alpha\)と書くことにする。
【定理】順序数\(\alpha\)に対し\(G(f^*_\alpha)\)を与える規則を\(F\)とすれば、\(F(\alpha)=G(F\upharpoonright_\alpha)\)が成り立つ。ここで\(F\upharpoonright_\alpha\)とは\(\{\langle\gamma,F(\gamma)\rangle:\gamma < \alpha\}\)を意味し、これは置換公理により集合をなしている。
（証明）任意の順序数\(\alpha\)をとる。補題Bにより、任意の\(\gamma < \alpha\)について\(f^*_\alpha(\gamma)=G(f^*_\gamma)\)となるから、\(f^*_\alpha=F\upharpoonright_\alpha\)である。この両辺に\(G\)を作用させると\(F(\alpha)=G(F\upharpoonright_\alpha)\)を得る。■
