帰納法と再帰
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/05/14 21:22 UTC 版)
整礎関係が興味深い重要な理由は、それによって超限帰納法の一種が考えられることにある。すなわち (X, R) が整礎関係で P(x) が X の元に関する何らかの性質であるときに、 P(x) が X の「すべての」元に対して満たされることを示すには、以下を示せば十分である。 x を X の元とするとき、y R x なる全ての y に対して P(y) が真であるならば P(x) は必ず真である。つまり、 ( ∀ x ∈ X ) [ ( ( ∀ y ∈ X ) ( ( y R x ) → P ( y ) ) ) → P ( x ) ] → ( ∀ x ∈ X ) ( P ( x ) ) {\displaystyle (\forall x\in X)\,[((\forall y\in X)\,((y\,R\,x)\to P(y)))\to P(x)]\to (\forall x\in X)\,(P(x))} が成り立つ。 このような整礎帰納法 (well-founded induction) は、エミー・ネーターにちなんでネーター帰納法 (Noetherian induction) とも呼ばれることがある。 帰納法と同様に、整礎関係は超限再帰による対象の構成も保証する。(X, R) が集合的整礎関係で F が X の元 x と X の始切片 {y | y R x} 上の函数 g の組に対して対象 F(x, g) を割り当てる函数とすると、函数 G が一意的に存在して、任意の x ∈ X に対して G ( x ) = F ( x , G | { y ∣ y R x } ) {\displaystyle G(x)=F(x,G\vert _{\{y\mid 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) が考えられる。あるいは普遍類上の帰属関係を整礎関係に選べば∈-帰納法として知られる帰納法が定まる（詳細は各項に譲る）。
※この「帰納法と再帰」の解説は、「整礎関係」の解説の一部です。
「帰納法と再帰」を含む「整礎関係」の記事については、「整礎関係」の概要を参照ください。
- 帰納法と再帰のページへのリンク
