帰納と再帰 - イガブロギュ

普通の数学における数学的帰納法や関数の再帰的定義は, その及ぶ範囲が自然数であることがほとんどです.
数学的帰納法は任意の自然数について述語が正しいことを証明する原理で, 再帰的定義は定義域が自然数全体の関数を再帰的に定義する場合によく用いられます.
集合論では, これらを順序数にまで拡張して考えます.

超眼帰納法(transfinite induction)
$C$ を順序数からなるクラスとし, 以下の3つの条件が満たされるとする.
(i) $0 \in C$
(ii) $\alpha \in C$ ならば $\alpha+1 \in C$
(iii) $\alpha$ が $0$ でない極限順序数で, 任意の $\beta < \alpha$ について $\beta \in C$ ならば $\alpha \in C$
このとき, $C$ は全ての順序数からなる.

証明
$\alpha \in C$ を任意に取ります.
$\alpha$ が $C$ における最小元でない場合, $\alpha \cap C$ における最小元を取り, これを改めて $\alpha$ とおきます( $\alpha \cap C$ は順序数, したがって整列順序なので最小元が存在するのです).
条件 (i) より, $\alpha \neq 0$ です.
$\alpha$ が後続順序数であるとすると, (ii) の対偶を取ることによって, その一つ前の順序数 $\beta$ について $\beta \notin C$ となりますが, これは $\alpha$ の最小性に反します.
$\alpha$ が $0$ でない極限順序数であるとすると, (iii) の対偶を取ることによって, $\beta < \alpha$ で $\beta \notin C$ となるものが存在することになりますが, これも $\alpha$ の最小性に反します.
以上により, $\alpha \notin C$ なる順序数 $\alpha$ は存在しないことが示されました.

クラスとは論理式の略記であると考えることができるので, 超眼帰納法は無限に多くの論理式についての主張だと考えることができます.
実際, 順序数のクラス $C$ を表す論理式は無数にあります.
というわけで, 超眼帰納法は, 定理というよりは定理図式(Schema)です.
実際に超眼帰納法を使うに当たっては, 次のような形が便利です.

超眼帰納法その2
$\rm{P}(\alpha)$ を順序数についての述語とし, 以下の3つの条件が満たされるとする.
(i) $\rm{P}(0)$ が成り立つ.
(ii) $\rm{P}(\alpha)$ が成り立つならば $\rm{P}(\alpha+1)$ が成り立つ.
(iii) $\alpha$ が $0$ でない極限順序数で, 任意の $\beta < \alpha$ について $\rm{P}(\beta)$ が成り立つならば $\rm{P}(\alpha)$ が成り立つ.
このとき, $\rm{P}(\alpha)$ は, 全ての順序数 $\alpha$ について成り立つ.

証明は, 上と全く同様なので省略します.
これも, 無限に多くの述語 $\rm{P}$ について考えているので, やはり定理図式です.
次の形のものも有用です.
証明は同様.

超眼帰納法その3
$\rm{P}(\alpha)$ を順序数についての述語とし, 以下の2つの条件が満たされるとする.
(i) $\rm{P}(0)$ が成り立つ.
(ii) 任意の $\beta < \alpha$ に対して $\rm{P}(\beta)$ が成り立つならば $\rm{P}(\alpha)$ が成り立つ.
このとき, $\rm{P}(\alpha)$ は, 全ての順序数 $\alpha$ について成り立つ.

ここから, いくつか用語を定義していきます.
定義域が自然数全体の集合 $N$ であるような関数を列(sequence)といいます.
また, $X$ における列とは, $N$ から $X$ への関数のことです.
列を
$\langle a_n : n < \omega \rangle$
などと書いたりもします.
有限列とは言わずもがな, 定義域が自然数である関数のことです.
関数の定義域を順序数に拡張したものを考えることもでき, これを超眼列(transfinite sequence)といい,
$\langle a_{\xi} : \xi < \alpha \rangle$
などと書いたりもします.
ここで, $\alpha$ は適当な順序数です.
$\alpha$ -列とか, 長さが $\alpha$ の列とか言ったりもします.
長さが $\alpha$ の列を拡張して列の $\alpha+1$ 番目の値が $x$ になるようにしたものを次のように書きます.
$s \frown x = sx = s \cup \{\alpha,x)\}$
超眼再帰は, 次のような定理です.

$G$ を $V$ を定義域とする関数(クラスの上で考えているので厳密には集合論の世界の中での関数とは異なります)とします.
このとき, $Ord$ を定義域とするユニークな関数 $F$ が存在して, 任意の $\alpha$ に対して
$F(\alpha) = G(\langle a_{\xi} : \xi < \alpha \rangle)$

証明
$F(\alpha) = x$ ということを, 次で定義します.
ある列 $\langle a_{\xi} : \xi < \alpha \rangle$ が存在して
(i) 任意の $\xi < \alpha$ について $a_{\xi} = G(\langle a_{\nu} : \nu < \xi \rangle)$
(ii) $x=G(\langle a_{\xi} : \xi < \alpha \rangle)$
まず, 任意の $\alpha$ に対して, (i) を満たす $\alpha$ -列が存在することが超眼帰納法により示されます.
(極限順序数の場合には置換の公理を使います)
次に, (i) を満たす $\alpha$ -列が一意に定まることも, 超眼帰納法により示されます.
よって, (ii) を満たす関数が一意に定まります.

この証明は, 細部をかなり省略しています.
近いうちに頑張って不備を埋めたいと思います.
最後にもう一つ, 言葉を定義しておきます.
$\alpha > 0$ を極限順序数とし, $\langle \gamma_{\xi} : \xi < \alpha \rangle$ を非減少列とします.
ここで非減少列とは $\xi < \nu$ ならば $\gamma_{\xi} \leq \gamma_{\nu}$ が成り立つ列のことです.
このとき, 列の極限(limit)を次のように定義します.
$\lim_{\xi \rightarrow \alpha}\gamma_{\xi} = \rm{sup}\{\gamma_{\xi} : \xi < \alpha\}$
次回は順序数の演算について書きたいのですが, 自分の超眼帰納法と超眼再帰の理解が不十分だと感じられるので, もう少し勉強して今回の内容を充実させてからにしたいと思います。