E を空でない集合とする。 Eに対するR の関係は、次の 2 つの条件のうちの 1 つを満たしている場合にのみ、十分に根拠がある、またはネーター的であると言うのはさらにまれです (アルティニアンの厳密さを尽くして、さらにめったに言われないことを言う必要があります)。依存選択 (選択公理の非常に弱いバージョン):
- Eの任意の部分Xについて、 XにR前件を持たないXの要素x が存在します。
( XにおけるxのR前件は、 yRxを満たすXの要素yです); - すべてのn に対して x n+1 Rx n が存在するようなEの要素の無限シーケンス(x n )は存在しません。
例
- 空のツリーから構築された有限バイナリ ツリーのセット上$$ {\Box} $$そして ¤ をルート化する (つまり、2 つのツリーAとBからツリーA ¤ B を形成する) という厳密な順序「 is a strict subtree of 」は十分に根拠のある順序です。意味: A ¤ B >$$ {\Box} $$またはA ¤ B > Cの場合$$ {\ge} $$CまたはB$$ {\ge} $$C.
- すべての文字列において、厳密な順序 ” は ” の厳密な接頭辞であり、十分な根拠があります。
- すべての文字列について、辞書の順序には十分な根拠がありません。
- 厳格な秩序と良好な秩序の組み合わせ。
- 一般に、全体的な順序関係は、関連する厳密な関係が十分に確立されている場合に限り、良好な順序となります。
- 基礎公理は、メンバーシップ関係が十分に確立されていることを表します。
- すべてのバイナリ ツリーで、次の十分な根拠のある順序を定義できます。
- A¤B> $$ {\Box} $$、
- またはA ¤ B > C ¤ Dであるため、
- A > CおよびA ¤ B > D 、
- またはA = CおよびB > D
- A¤B>
最後の順序では、ツリー (
アルゴリズムでの使用
詳細には立ち入らないが、十分に根拠のある厳密な順序の定義の直接的かつ準自明な結果は、構築された要素がその前のものより厳密に劣っていることを保証しながら、そのような順序の要素のシーケンスを構築するアルゴリズムが、また、その終了も保証します（不条理によって証明されています。実際、そうでなければ、厳密に減少する無限シーケンスを構築することになります）。
アルゴリズムで使用される構造 (構築型) は、多くの場合、十分に根拠のある厳密な順序であるため、コンピューター プログラムの終了を証明するための非常に一般的な方法があります。
十分に根拠のある関係と再発
十分に根拠のある関係は、超限回帰によって構築されたランク関数に関連付けられており、超限回帰による実証が可能になります。詳しく見てみましょう。
R を集合E上の十分に根拠のある関係とし、 Jを整然とした集合とし、カーディナリティーがEより大きく、「序数の貯蔵庫」として機能させます (その最初の要素は 0,1,…)。 ）。 Rのランク関数ρ は、次のように超限帰納法によって定義されるJ内のEのマップです。x ∈ Eの場合
- xにRの前件がない場合、ρ( x ) = 0。
- 一般的な場合、ρ( x ) = sup { ρ( y )+1, Rのxのy前件 }。
したがって、 xの順位は、 xの先行詞の順位よりも厳密に優れた最小の序数です。それは第 1 種または第 2種の場合があります。リレーションRの長さは、多くの場合 | で表されます。 R | は、すべての ρ(x) より厳密に大きい最小の序数です。ランク関数を使用すると、明白な方法でE を階層構造に編成することができ、 Rのメンバーシップ関係を使用した公理的な集合論で広く使用されます。
ランク関数を使用すると、ペアノの公理 n°5 または漸化の原理を一般化する次の定理を使用した超有限漸化による実証が可能になります。
- P を、ランク < j のすべての x が含まれるとすぐに、すべての j についてランク j のすべての x∈E を含む E の一部とする。すると P は集合 E 全体になります。
空の集合 (ランク <0 のxの集合) のおかげで、明示的に再帰を開始する必要はありませんでした。注意 ！ここでは、第 2 種序数が存在するため、ランクjからランクj+1に移動するだけでは十分ではありません。
