Loading article…
数学において、二項関係Rは、集合またはより一般的にはクラスX上で、空でない部分集合 (または部分クラス) S ⊆ X がRに関して最小の要素を持つ場合、整礎(または基礎的) [ 1 ] である。つまり、すべてのs ∈ Sに対してs R mが存在しないようなm ∈ Sが存在する。より厳密には、関係が整礎であるとは、次の条件を満たす場合である 。一部の著者は、 Rが集合のような性質を持つ、つまり、任意の与えられた要素よりも小さい要素が集合を形成するという 追加条件を含めている。
同様に、従属選択公理を仮定すると、関係は無限下降鎖を含まない場合に整礎である。つまり、すべての自然数nに対してx n +1 R x nとなるようなXの要素の無限列x 0、x 1、x 2、 ...が存在しない。[ 2 ] [ 3 ]
順序理論において、半順序は、対応する厳密順序が整礎関係である場合に、整礎関係と呼ばれる。順序が全順序である場合は、整列順序と呼ばれる。
集合論において、集合x は、その推移閉包に基づいて集合の帰属関係が整礎である場合に、整礎集合と呼ばれる。ツェルメロ＝フレンケル集合論の公理の一つである正則性の公理は、すべての集合が整礎集合であることを主張する。
関係Rは、逆関係R −1がX上で整礎である場合、逆整礎、上方整礎、またはネーター的である。この場合、Rは上昇連鎖条件を満たすとも言われる。書き換えシステムの文脈では、ネーター的関係は終端的とも呼ばれる。
整礎関係が興味深い重要な理由の一つは、超限帰納法の一種をそれらに適用できるからである。すなわち、( X , R ) が整礎関係であり、P ( x )がXの要素の何らかの性質であり、我々は次のことを示したいのである。
次のことを示すだけで十分である。
つまり、
根拠のある帰納法は、エミー・ノーターにちなんでノーター帰納法と呼ばれることもある[ 4 ]。
帰納法と同様に、整礎関係も超限再帰によるオブジェクトの構築をサポートする。集合のような整礎関係( X , R )と、 Xの要素x ∈ Xと、x の先行要素の集合{ y : y R x }上の関数gの各ペアにオブジェクトF ( x , g )を割り当てる関数をFとする。このとき、すべてのx ∈ Xに対して、一意の関数Gが存在し、
つまり、X上に関数Gを構築したい場合、y ∈ xのG ( y )の値を使用してG ( x )を定義することができます。
例として、自然数の集合をN、後継関数x ↦ x +1のグラフをSとしたときの、整礎関係( N , S )を考えてみましょう。このとき、 Sに対する帰納法は通常の数学的帰納法であり、Sに対する再帰は原始再帰となります。順序関係( N , <)を考えると、完全帰納法と値系列再帰が得られます。 ( N , <)が整礎であるという命題は、整列原理としても知られています。
整礎帰納法には、他にも興味深い特殊なケースがあります。整礎関係がすべての順序数のクラスにおける通常の順序である場合、この手法は超限帰納法と呼ばれます。整礎集合が再帰的に定義されたデータ構造の集合である場合、この手法は構造帰納法と呼ばれます。整礎関係が普遍クラスにおける集合のメンバーシップである場合、この手法は∈帰納法として知られています。詳細については、それぞれの記事を参照してください。
完全には順序付けられていないものの、十分に根拠のある関係には以下のようなものがある。
根拠が不十分な関係の例としては、以下のようなものがある。
( X , <)が整礎関係であり、xがXの要素である場合、 xから始まる下降鎖はすべて有限ですが、これは必ずしもその長さが制限されることを意味するものではありません。次の例を考えてみましょう。Xを、任意の整数よりも大きい新しい要素 ω を含む正の整数の和集合とします。このとき、Xは整礎集合ですが、任意の大きな (有限) 長さの ω から始まる下降鎖が存在します。鎖ω, n − 1, n − 2, ..., 2, 1 は、任意のnに対して長さnを持ちます。
モストフスキーの崩壊補題は、集合メンバーシップが外延的整礎関係の普遍性であることを示唆している。すなわち、クラスX上の任意の集合のような整礎関係R が外延的である場合、 ( X , R )が( C , ∈)と同型となるようなクラスCが存在する。
関係Rは、その関係の定義域内のすべてのaに対してa R aが成り立つ場合、反射的であると言われます。空でない定義域上のすべての反射的関係は無限の下降列を持ちます。なぜなら、任意の定数列は下降列だからです。たとえば、通常の順序 ≤ を持つ自然数では、 1 ≥ 1 ≥ 1 ≥ ...となります。このような自明な下降列を避けるために、部分順序 ≤ を扱う場合、a < bとなるのはa ≤ bかつa ≠ bの場合のみであるように定義される代替関係 < に、整礎性の定義を（おそらく暗黙のうちに）適用するのが一般的です。より一般的には、前順序≤を扱う場合、 a < bとなるのはa ≤ bかつb ≰ aの場合のみであるように定義される関係 < を使用するのが一般的です。自然数の文脈では、これは整礎性を持つ関係 < が、整礎性を持たない関係 ≤ の代わりに使用されることを意味します。一部の文献では、上記の定義から変更され、これらの慣例が含まれるようになっている。
![{\displaystyle (\forall S\subseteq X)\;[S\neq \varnothing \implies (\exists m\in S)(\forall s\in S)\lnot (s\mathrel {R} m)].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/39674b23f300f531f307e8dbab52b953786a5e4b)
![{\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).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/891f3d17973e3226b31a0773b4b81e03b2292754)
