■

[集合論]InductionとRecursion

　タイトルは和訳では、『帰納と再帰』となるだろうか。最近読んでいたどれかの本で（Jech本ではなかった気がする）数学書でもこの２つの用語がごっちゃになってることがあるとの指摘があった。前回の私の記事でも、『関数を帰納的に定義する』というようなことをいっちゃってたような気がするが、正しくは『関数を再帰的に定義する』である。ややこしいのは『帰納的定義』というのもあって、単純なオブジェクトから複雑なオブジェクト作る手順が
① なんちゃらはオブジェクトである。
② オブジェクトとオブジェクトを一定の手順で組み合わせるとオブジェクトができる。
③ オブジェクトはすべてこれらの操作のみで作られる。
というやつである。帰納的に定義されたオブジェクトの集まり（クラス）に対しては、オブジェクトのある性質について、その帰納的定義の構造に基づく帰納法により全てのオブジェクトでその性質が成り立つといった証明ができる。しかし、一旦、帰納的定義を忘れて、考えているオブジェクトのクラスが先に存在したとしよう。

帰納法：
オブジェクトのある性質Rについて、

① なんちゃらは性質Rを持つ。
② 性質Rを持つオブジェクトを一定の手順で組み合わせると性質Rを持つオブジェクトができる。
ならば、すべてのオブジェクトが性質Rを持つ。

といった形の論法が帰納法である。次に見る順序数のように帰納法は成り立つが、オブジェクトが必ずしも帰納的に定義されているわけではない場合がある。

定理（超限帰納法 Transfinite Induction; たとえば Jech本p.21のTheorem 2.14）
　Cを順序数のクラスとする。Cが次の3つの条件を満たすと、それは順序数全体と一致する。

(i) 0\in C
(ii) \alpha \in C\ \Rightarrow \ \alpha+1 \in C
(iii) \alphaが0でない極限順序数であるとき、\forall\beta < \alpha;\ \beta \in C \Rightarrow \alpha \in C

ちなみにこの手順を逆にして、順序数を帰納的に定義したようなテキストは見たことない。順序数の定義としては、推移的かつ\inに関する整列集合という定義以外は知らない（このフォン・ノイマン流定義を最初見たときは、なんじゃこれはと思ったが、今となっては良くできた定義であると思う。フォン・ノイマンすげえ）。手順が逆にできない理由は、(iii)で極限順序数\alphaなるものの存在が先にある点で、\alpha=\cup_{\beta < \alpha}\betaを知っているとしても、この右辺の和集合の条件に\alphaが出てきてしまっている。ここを仮に『これまでの過程で作ったすべての順序数』としてみても、『これまでの過程で作ったすべての順序数』の集まりが集合になっている保証がなければその和も集合になっている保証はない。恐らくそれをいちいち確かめなければならない点で帰納的定義が躓くのだろうと思う。

ところで、上の定理の証明はJech本ではまさかの一行証明である。

＜証明＞ そうでなければ、\alphaを\alpha \notin Cなる最小の順序数として、(i),(ii),(iii)を適用せよ。

まあ、無論、Jech本では証明の前に準備はあるのだが、\alphaは0か\alpha=\beta+1となる\betaがあるか、極限順序数なので(i),(ii),(iii)を適用すると\alpha\in Cとなって矛盾するという論法である。任意の順序数のクラスCに最小元があるというのがミソで、実際 \alpha=\cap Cとなっていて、それはいつでも集合（かつ順序数）であるということが事前に証明されているので抜かりはない。


さて、前回に関数の再帰的定義は集合論としても正しいという一例を証明してみたが、実は今回の記事はその続きでもある。底本はJech本だが、テキストではTransfinite Recursion の証明は 1/3ページぐらいしか証明がなく、ギャップを埋めてみようという魂胆である。それに Transfinite Recursion の定式の意味の理解にかなり苦しんだのでそのノートという意図もある。

さて、記号の準備から始める。集合に値を取るOrd上の関数クラスを考えたいので、それを

< a_\alpha\ :\ \alpha \in Ord >

と書こう。これを列(sequence)と呼ぶ。無論これの実体は \{(\alpha, a_\alpha) | \alpha \in Ord \}というペアのクラスだが、Ordがもともと集合でないので、これも真のクラスである。ただ、ある順序数\thetaでちょんぎった
< a_\alpha\ :\ \alpha < \theta >

なるものは集合になっていて、これを \theta-列と呼ぼう。\theta-列が集合になるのは、\{\alpha | \alpha \in \theta\}は集合なので、置換公理からその像 \{a_\alpha | \alpha \in \theta \}も集合で、
< a_\alpha\ :\ \alpha < \theta >=\{ (\alpha,y) \in \theta \times \{a_\alpha | \alpha \in \theta \}| \alpha \in \theta \wedge y=a_\alpha \}
から分出公理により集合となる。ただし、『集合に値を取る』というのが特定の集合内に値を取るということではなくて、集合全部を動く可能性も含むので \thetaを固定したとしても、\theta-列の全体は真のクラスとなってしまう。ちょっと風呂敷広げすぎとは思う。さて、ここでGを、\thetaがすべてのOrgを動くときの全ての\theta-列のクラス上で定義された、集合に値を取る任意の関数クラスとしよう（さらに風呂敷が広がったわけである）。


定理 (超限再帰法 Transfinite Recursion)
　(先に述べたような)任意のGに対して、Org上の関数クラス Fで、任意の順序数 \alphaに対して、

F(\alpha)=G(F \upharpoonright \alpha)

が成立するものが唯一存在する。

（Fは列であり、F \upharpoonright \alphaは列Fを\alphaでちょん切った \alpha-列を指す記号である。）

風呂敷を広げまくった割にはこじんまりとした定理であるが、これのどこがRecursionなのか最初はピンとはこなかった。しかし、ちょっと最初の方を具体的に計算してみるとその意味がわかってくる。F=< a_\alpha\ :\ \alpha \in Ord > として、F(\alpha)=a_\alphaという列としての表記も併用しよう。

・まず、\alpha=0からスタートである。Fがなんであれ F \upharpoonright 0 = 0なので、結局 a_0=F(0)=G(0)である。

・\alpha=1のとき、もうa_0は決まってしまっているので、a_1=F(1)=G( < a_0 > )。

・\alpha=2のとき、もうa_0,a_1は決まってしまっていて、a_2=F(2)=G( < a_0,a_1 > )。

とまあ、以下FがGで決まってしまうのが見て取れるだろう。しかもすべての\alpha-列の上での関数クラスとしているため、引数の数でG_nと分けて書けば、F(n)=G_n(G_0,G_1(G_0),G_2(G_0,G_1(G_0)),\cdots ),\cdots,G_{n-1}(G_0,\cdots)) といったようにその時点より前に計算したすべての値をパラメータに使う最も一般的な再帰的定義を表現していることがわかるだろう（しかもそのTransfinite版である）。

＜証明＞
　任意の順序数 \alphaに対して、F(\alpha)を定義したい。\xi < \alphaなるすべての順序数 \xiに対して、F(\xi)が定義されていて、F(\xi)=G(F\upharpoonright \xi)が成立しているとしよう。このとき、F(\alpha)=G(F\upharpoonright \alpha)と定義すればよいだろう。しかし、この定義のありようはTransfinite Recursionそのものなので、これを素直に認めてしまったら証明にならない。アヤシイのは『F(\xi)が定義されていて』の部分である。Jech本の証明ではこれを\alphaごとにつどつど、つぎの条件を満たす\alpha-列の存在に置き換える。

条件：(\forall \xi < \alpha)a_\xi=G( < a_\eta:\eta < \xi \ > )

この条件を満たす\alpha-列sが唯一存在する（証明はのちほど）が、このとき、F(\alpha)=G(s)と定義するのである。この構成だとF:=\{(\alpha,F(\alpha))| \alpha \in Ord\}が論理式で閉じた形で表現できるため、Fは関数クラスとなる。また、\alphaに対して、\alpha-列 < F(\xi):\xi < \alpha > = F \upharpoonright \alphaが、(\forall \xi < \alpha)F(\xi)=G( < F(\eta):\eta < \xi \ > )を満たすつまり、先の条件を満たす\alpha-列になっていることが証明できるので、Fが定理の条件を満たしていることがわかる。
(この最後のステートメントを念のため証明しておこう。超限帰納法と同じ論法である。\xi=0の時は F(0)=G(0)なので成立している。先の条件を満たさない最小の順序数を\xi_0 < \alphaとしよう。\xi < \xi_0に対しては、\xi_0-列 F\upharpoonright \xiが先の条件を満たすため、F(\xi_0)の定義に使う唯一の\xi_0-列に一致するので、 F(\xi_0)=G(F\upharpoonright \xi_0)となるが、これは\xi_0が条件をみたすことになり、矛盾である。)
　残した\alpha-列の存在と唯一性を証明しよう。ただ、唯一性については上の証明とほぼ同じなので、存在だけを示そう。\alphaに対する超限帰納法を使う。条件をみたす\alpha-列が存在する順序数の全体のクラスをCとしよう。
(i) \alpha=0の時、a_0:=G(0)とすればよいので 0 \in C。
(ii) \alpha \in Cのとき、\xi < \alpha+1とは、\xi < \alphaか\xi = \alphaなので、\xi < \alphaの時は条件は仮定\alpha \in Cから成立しており、a_{\alpha}:=G( < a_\eta:\eta < \alpha \ > )とすれば\xi = \alphaでも条件が成立するので、 \alpha+1 \in C。
(iii)\alpha \in Cが0でない極限順序数のとき、\forall\beta < \alphaに対して \beta \in Cとしよう。各々の\betaに対する条件は (\forall \xi < \beta)a_\xi=G( < a_\eta:\eta < \xi \ > )となる。右辺の数列は\betaごとに違ってもいいのだが、実際は定義されているところではすべて一致している（これも超限帰納法による）。そこで F_\beta := \{(\xi,a_\xi) | \xi < \beta \}と書いて、F_\alpha := \cup_{\beta < \alpha} F_\beta を作ると F_\alphaは\alpha-列を定義することがわかる（Jech本では、この和を作るときのインデックスが順序数\alphaなので、和は集合になるとの注意がある）。しかも、 \forall\xi < \alphaに対して、\beta := \xi+1 < \alpha なので(∵ \alphaが極限順序数だったから)、\betaに対する超限帰納法の仮定から、a_\xi=G( < a_\eta:\eta < \xi \ > )が成立しているが、右辺のGの中は < F_\alpha(\eta):\eta < \xi \ > に等しいので、条件が成立している。よって \alpha \in C
よって、超限帰納法より C=Ordとなる。□


　前回の記事で気にしていたのは、再帰的に定義された関数は本当に（集合としての）関数か？という点にあったのだが、今回の超限再帰法の定理では、Ord上の関数クラスの存在しか主張してない点で、もう一押しが必要である。とはいえ、\omegaまでの話を考えればいいだろう。Gが、\omega-列上にしか定義されていないとき、\omegaに等しいか大きい順序数\alphaに対する\alpha-列には、 0と拡張しておけば、今回の超限再帰法の定理が使えて、それに対応する関数クラスFが存在する。そこで F \upharpoonright \omegaが関数か？が問題となるが、これは置換公理からほぼ自明となっている...のでまあ、Fが関数クラスとして定義されうるという点が本質ということなのだろうが、なんか肩透かし感はある。

（蛇足編）
　本記事を書くにあたって、何か証明のヒントは無いかとKunen本（集合論 独立性証明への案内 日本評論社）も調べてみたところ、Jech本の証明と同じ筋でした。こっちのがもう少し筋を明確に書いてますね。Kunen本の原著の初版が1983年なのでこっちのが断然前ですな。しかし、そこの続きにも超限帰納法を使えとだけ...