根拠のある関係

数学において、二項関係 Rが集合または、より一般的にはクラスX上でwell-founded (またはwell-foundedあるいはfoundational ^[1] ) であるとは、すべての空でない部分集合S ⊆ XがRに関して極小元を持つ場合、つまり、すべてのs ∈ Sに対してs R m を持たないようなm ∈ Sが存在する場合です。言い換えると、関係が well-founded であるとは次のようになります。 一部の著者は、 Rが集合的である という追加の条件、つまり、任意の元よりも小さい元が集合を形成するという条件を含めています。 $${\displaystyle (\forall S\subseteq X)\;[S\neq \varnothing \implies (\exists m\in S)(\forall s\in S)\lnot (s\mathrel {R} m)].}$$

同様に、従属選択公理を仮定すると、関係が無限下降連鎖を含まないとき、その関係は整根拠関係であり_{、これは、任意の自然数nに対してxn} + _1Rxnとなる_{ようなXの}要素の無限シーケンスx0、x1、x2、...が存在しないときに証明できます。^{[2] [3]}

順序理論では、対応する厳密な順序が整列関係である場合、部分順序は整列していると呼ばれます。順序が全順序である場合、それは整列していると呼ばれます。

集合論において、集合x は、集合の帰属関係がxの推移閉包上で整基礎である場合に、整基礎集合と呼ばれる。ツェルメロ-フランケル集合論の公理の 1 つである正則性公理は、すべての集合が整基礎であることを主張する。

逆関係R ⁻¹がX上で整基盤である場合、関係RはX上で逆整基盤、上方整基盤、またはノイザン関係と呼ばれます。この場合、Rは昇順連鎖条件を満たすとも言われます。書き換えシステムのコンテキストでは、ノイザン関係は終了関係とも呼ばれます。

整基礎関係が興味深い重要な理由は、超限帰納法の一種をそれらに適用できるからである。もし ( X , R ) が整基礎関係ならば、P ( x ) はXの要素の何らかの性質であり、次のことを示したい。

P ( x )はXのすべての要素xに対して成り立ち、

次のことを示せば十分です。

x がXの要素であり、y R xとなるすべてのyに対してP ( y )が真である場合、P ( x )も真でなければなりません。

つまり、 $${\displaystyle (\forall x\in X)\;[(\forall y\in X)\;[y\mathrel {R} x\implies P(y)]\implies P(x)]\quad {\text{implies}}\quad (\forall x\in X)\,P(x).}$$

十分な根拠のある帰納法は、エミー・ネーターにちなんで、ネーター帰納法^[4]と呼ばれることもあります。

帰納法と同様に、整基礎関係は超限再帰によるオブジェクトの構築もサポートします。( X、R )を集合のような整基礎関係とし、F をXの要素x ∈ Xと 関数gの各ペアにオブジェクトF ( x、g )を割り当てる関数とします。すると、任意のx ∈ Xに対して、 $${\displaystyle G(x)=F\left(x,G\vert _{\left\{y:\,y\mathrel {R} x\right\}}\right).}$$

つまり、X上に関数G を構築したい場合、 y R xに対するG ( y )の値を使用してG ( x )を定義できます。

例として、整基礎関係( N、S )を考えてみましょう。ここで、N はすべての自然数の集合であり、S は後続関数x ↦ x +1のグラフです。S上の帰納法は通常の数学的帰納法であり、S上の再帰は原始再帰をもたらします。順序関係( N、 < )を考えると、完全な帰納法と値の経過の再帰が得られます。 ( N、 < )が整基礎であるというステートメントは、整順序原理としても知られています。

他にも、整根拠帰納法の興味深い特殊なケースがあります。整根拠関係がすべての順序数のクラス上の通常の順序である場合、この手法は超限帰納法と呼ばれます。整根拠集合が再帰的に定義されたデータ構造の集合である場合、この手法は構造帰納法と呼ばれます。整根拠関係が普遍クラス上の集合のメンバーシップである場合、この手法は∈-帰納法として知られています。詳細については、これらの記事を参照してください。

完全に順序付けられていない、十分に根拠のある関係には次のものがあります。

• 正の整数 {1, 2, 3, ...}。順序は、a がb を割り切れる場合かつa ≠ b の場合に限り、a < b で定義されます。
• 固定されたアルファベット上のすべての有限文字列の集合。順序は、 s がtの適切な部分文字列である場合に限り、s < tで定義されます。
• 自然数のペアの集合N × N 。n ₁ < m ₁かつn ₂ < m ₂の場合にのみ、( n ₁ , n ₂ ) < ( m ₁ , m ₂ )の順序になります。
• 要素が集合であるすべてのクラスは、関係∈（「要素である」）を持ちます。これが正則性の公理です。
• 任意の有限有向非巡回グラフのノード。関係Rは、 aからbへのエッジがある場合に限り、a R bとなるように定義されます。

十分に根拠のない関係の例には、次のようなものがあります。

• 負の整数{−1, −2, −3, ...}。任意の無限部分集合には最小の要素がないため、通常の順序になります。
• 通常の (辞書式) 順序では、有限のアルファベット上の複数の要素を持つ文字列の集合。シーケンス"B" > "AB" > "AAB" > "AAAB" > ...は無限降順チェーンであるためです。集合全体に最小要素、つまり空の文字列がある場合でも、この関係は適切ではありません。
• 標準的な順序付けによる非負の有理数(または実数) の集合。たとえば、正の有理数 (または実数) のサブセットには最小値がないためです。

( X , <)が well-founded 関係であり、x がXの要素である場合、 xから始まる降順チェーンはすべて有限ですが、これはその長さが必ずしも制限されることを意味するわけではありません。次の例を考えてみましょう。X を、任意の整数よりも大きい新しい要素 ω を持つ正の整数の和集合とします。この場合、X はwell-founded セットですが、 ω から始まる任意の大きな (有限の) 長さの降順チェーンが存在します。チェーンω, n − 1, n − 2, ..., 2, 1は、任意のnに対して長さがnです。

モストフスキーの崩壊補題は、集合のメンバーシップが外延的な整基礎関係の間で普遍的であることを意味します。つまり、外延的なクラスX上の任意の集合のような整基礎関係Rに対して、 ( X、R ) が( C、∈)と同型であるようなクラスC が存在します。

関係R は、関係の定義域内のすべてのaに対してR aが成り立つ場合、反射的であるという。空でない定義域上のすべての反射的関係には、無限の下降連鎖がある。これは、任意の定数列が下降連鎖だからである。たとえば、通常の順序 ≤ を持つ自然数では、 1 ≥ 1 ≥ 1 ≥ ...となる。これらの自明な下降シーケンスを回避するために、半順序 ≤ を扱うときは、別の関係 < に well-founded の定義を（おそらく暗黙的に）適用するのが一般的である。この関係 < は、 a ≤ bかつa ≠ b の場合にのみa < bとなるように定義される。より一般的には、前順序≤を扱うときは、 a ≤ bかつb ≰ aの場合にのみa < bとなるように定義される関係 < を使用するのが一般的である。自然数のコンテキストでは、これは、 well-founded である関係 < が、 well-founded ではない関係 ≤ の代わりに使用されることを意味する。いくつかのテキストでは、well-founded 関係の定義は、これらの規則を含めるために上記の定義から変更されています。

• Just, Winfried および Weese, Martin (1998) 「現代の集合論の発見」 I、アメリカ数学会 ISBN 0-8218-0266-6。 
• Karel Hrbáček & Thomas Jech (1999)集合論入門、第 3 版、「Well-founded relationships」、251 ～ 255 ページ、Marcel Dekker ISBN 0-8247-7915-0