>>412
つづき

帰納法と同様に、整礎関係は超限再帰による対象の構成も保証する。(X, R) が集合的整礎関係で F が X の元 x と X の始切片 {y | y R x} 上の函数 g の組に対して対象 F(x, g) を割り当てる函数とすると、函数 G が一意的に存在して、任意の x ∈ X に対して
G(x)=F(x,G｜y|yRx)
が満たされる。つまり、X 上の函数 G を構成しようとするとき、G(x) を y R x なる y に対する値 G(y) を利用して定義することができる。

例として、整礎関係 (N, S) を考える。ここで N は自然数全体のなす集合で、S は後者函数 x → x + 1 のグラフとする。S 上の帰納法は通常の数学的帰納法であり、S 上の再帰は原始再帰を与える。順序関係 (N, <) からは完全帰納法 (complete induction) と累積帰納法 (course-of-values recursion) が得られる。 (N, <) が整礎関係であるという言明は整列原理としても知られる。

ほかにも重要な整礎帰納法の特別の場合がある。整礎関係として順序数全体のなす類上の通常の順序を考えれば、超限帰納法 (transfinite induction) と呼ばれる手法が得られるし、整礎集合として再帰的に定義されるデータ構造からなる集合をとれば、構造的帰納法 (structural induction) が考えられる。あるいは普遍類上の帰属関係を整礎関係に選べば∈-帰納法として知られる帰納法が定まる（詳細は各項に譲る）。

つづく