>>411

つづき

つまり、X の元の無限列 x0, x1, x2, ... で、どんな n についても xn+1 R xn となるようなものはとれない。

順序集合論（英語版）では、半順序に対応する真の順序 (strict partial order) が整礎関係となるとき、その半順序を整礎（整礎半順序）と呼ぶ。全順序がこの意味で整礎であるとき、整列順序と呼ぶ。

集合 x が整礎的集合 (well-founded set) であることは、∈ が x の推移閉包上で整礎関係となることと同値である。ZF における公理のひとつである正則性の公理は、全ての集合が整礎であることを要請するものである。

関係 R が X 上で逆整礎 (converse well-founded) または上方整礎 (upwards well-founded) であるとは、R の逆関係 R^-1 が X 上の整礎関係であるときにいう。

帰納法と再帰
整礎関係が興味深い重要な理由は、それによって超限帰納法の一種が考えられることにある。すなわち (X, R) が整礎関係で P(x) が X の元に関する何らかの性質であるときに、 P(x) が X の「すべての」元に対して満たされることを示すには、以下を示せば十分である。

x を X の元とするとき、y R x なる全ての y に対して P(y) が真であるならば P(x) は必ず真である。つまり、
略
が成り立つ。 このような整礎帰納法 (well-founded induction) は、エミー・ネーターにちなんでネーター帰納法 (Noetherian induction) とも呼ばれることがある[4]。

つづく