超限誘導

超限帰納法は、数学的帰納法を順序数に拡張したものです。その正しさはZFの定理であり、順序数が整列しているという事実に基づいています。したがって、すべての順序数に対して普遍的に真でない命題には、最小限の反例が存在します。実際、この原理は任意の整列集合に対しても真ですが、任意の整列集合は順序を保持する方法で順序数によってインデックス付けできるため、順序数に対してこの原理を確立すれば十分です。^{[ 1 ]}

超限帰納法の原理は以下のとおりです。

させて${\displaystyle P(\alpha )}$すべての序数に対して定義されたプロパティである。${\displaystyle \alpha }$. いつでも${\displaystyle P(\beta )}$すべてに当てはまる${\displaystyle \beta <\alpha }$⁠、それから${\displaystyle P(\alpha )}$これも真実である。^{[ 2 ]}すると${\displaystyle P}$これは全ての序数に当てはまります。

この原理は、対偶形式を考えることで容易に証明できる。

もし​${\displaystyle P}$⁠ がすべての序数に対して真でないならば、ある序数⁠が存在する。${\displaystyle \alpha }$⁠そのため⁠${\displaystyle P(\beta )}$すべてに当てはまる${\displaystyle \beta <\alpha }$しかし​​${\displaystyle P(\alpha )}$⁠は偽です。

このような${\displaystyle \alpha }$⁠は最小限の反例にすぎず、その存在は順序数のクラスが整列しているという事実によって保証されている。

超限再帰は超限帰納法に似ていますが、すべての序数に対して何かが成り立つことを証明する代わりに、各序数に対応するオブジェクトの列を構築します。

例えば、(無限次元の場合もある)ベクトル空間の基底は、空集合から始めて、各順序数α > 0に対して、ベクトルの張る空間に含まれないベクトルを選択することによって作成できます。${\displaystyle \{v_{\beta }\mid \beta <\alpha \}}$適切なベクトルを選択できなくなった時点で、このプロセスは停止します。

より厳密に言えば、超限再帰定理は次のように述べることができる。

超限再帰定理（バージョン 1）。クラス関数^{[ 3 ]} G : V → V ( Vはすべての集合のクラス) が与えられたとき、一意の超限列F : Ord → V (Ord はすべての順序数のクラス)

${\displaystyle F(\alpha )=G(F\upharpoonright \alpha )}$すべての順序数αに対して、${\displaystyle \upharpoonright }$F の定義域をα未満の順序数に制限することを意味します。

帰納法の場合と同様に、異なる種類の順序数を別々に扱うことができます。超限再帰の別の定式化は次のとおりです。

超限再帰定理（バージョン2）。集合g ₁とクラス関数G ₂、G ₃が与えられたとき、一意の関数F : Ord → Vが存在し、

• F (0) = g ₁、
• F ( α + 1) = G ₂ ( F ( α ))、すべてのα ∈ Ordに対して、
• ${\displaystyle F(\lambda )=G_{3}(F\upharpoonright \lambda )}$、 λ ≠ 0 のすべての極限に対して。

上記の性質が意味を持つためには、 G ₂およびG ₃の定義域が十分に広い必要があることに注意してください。これらの性質を満たす数列の一意性は、超限帰納法を用いて証明できます。

より一般的には、任意の整礎関係R上で超限再帰によってオブジェクトを定義することができる。（R は集合である必要はなく、集合のような関係であれば、適切なクラスであってもよい。つまり、任意のxに対して、 yRxが集合となるようなすべてのyの集合である。）

帰納法や再帰法を用いた証明や構成では、選択公理を用いて、超限帰納法で扱える整列関係を生成することが多い。しかし、問題の関係が既に整列している場合は、選択公理を用いずに超限帰納法を用いることができる場合が多い。^{[ 4 ]}例えば、ボレル集合に関する多くの結果は、集合の順序ランクに対する超限帰納法によって証明される。これらのランクは既に整列しているため、選択公理を用いて整列させる必要はない。

以下のヴィタリ集合の構成は、選択公理を超限帰納法による証明に用いる方法の一例を示している。

まず、実数を整列させる（ここで整列定理を通して選択公理が現れる）、数列が得られる。${\displaystyle \langle r_{\alpha }\mid \alpha <\beta \rangle }$ここで、βは連続体の濃度を表す順序数です。v _0をr ₀とします。次に、v 1 を r α 1 とします。ここで、α 1_はr α ₁ − v _0が有理数でない_最小の数です_。これを繰り返します。各ステップで、 v列でこれまでに構築されたどの要素とも有理数の差を持たないr列の最小の実数を使用します。r 列のすべての実数がなくなるまで繰り返します。最終的なv列は、ヴィタリ集合を列挙します。  

上記の議論では、実数を整列させるために、冒頭で選択公理を本質的に用いている。その後は、選択公理は再び用いられない。

選択公理の他の用法はより微妙です。たとえば、超限再帰による構成では、αまでの列が与えられた場合、A _{α +1}の一意の値を指定するのではなく、 A _{α +1が満たさなければならない}条件のみを指定し、この条件を満たす集合が少なくとも 1 つ存在することを主張します。各段階でそのような集合の一意の例を定義することができない場合は、各ステップでそのような集合を 1 つ選択するために、（何らかの形の）選択公理を呼び出す必要があるかもしれません。可算長の帰納法と再帰では、弱い依存選択公理で十分です。ツェルメロ・フレンケル集合論には、依存選択公理は満たすが完全な選択公理は満たさない、集合論者にとって興味深いモデルが存在するため、特定の証明が依存選択のみを必要とするという知識は有用です。

• 数学的帰納法
• ε誘導
• 超限数
• 根拠に基づいた帰納法
• ゾルンの補題

• サップス、パトリック（1972）、「第7.1節」、公理的集合論、ドーバー出版、ISBN 0-486-61630-4

• エマーソン、ジョナサン、レザマ、マーク、ワイススタイン、エリック W. 「超限帰納法」 . MathWorld .