超限帰納法

超限帰納法は、数学的帰納法を順序付けられた集合、例えば順序数や基数の集合に拡張したものである。その正しさはZFCの定理である。^[1]

をすべての順序数に対して定義された性質とします。 がすべての に対して真である ときはいつでも、も真であるとします。^[2]すると、超限帰納法により、 がすべての順序数に対して真であること が分かります。${\displaystyle P(\alpha )}$${\displaystyle \alpha}$${\displaystyle P(\beta )}$${\displaystyle \beta <\alpha }$${\displaystyle P(\alpha )}$${\displaystyle P}$

通常、証明は次の 3 つのケースに分類されます。

• ゼロの場合:それが真実であることを証明してください。${\displaystyle P(0)}$
• 後続ケース:任意の後続順序数 に対して、が従うことを証明します(必要な場合は、すべての に対して が従います)。${\displaystyle \alpha +1}$${\displaystyle P(\alpha +1)}$${\displaystyle P(\alpha )}$${\displaystyle P(\beta )}$${\displaystyle \beta <\alpha }$
• 極限の場合:任意の極限順序数 に対して、すべての に対して が成り立つ場合、 であることを証明します。${\displaystyle \lambda}$${\displaystyle P(\beta )}$${\displaystyle \beta <\lambda }$${\displaystyle P(\lambda )}$

考慮する順序数の種類を除いて、これら 3 つのケースはすべて同一です。形式的には別々に考慮する必要はありませんが、実際には証明が非常に異なるため、別々に提示する必要があります。ゼロは極限順序数と見なされることがあり、同じケースの証明で極限順序数として扱われることがあります。

超限再帰は超限帰納法に似ていますが、すべての順序数に対して何かが成り立つことを証明する代わりに、順序数ごとに 1 つずつオブジェクトのシーケンスを構築します。

例として、（おそらく無限次元の）ベクトル空間の基底は、空集合から始めて、各順序数α > 0に対してベクトルの範囲にないベクトルを選択することによって作成できます。このプロセスは、ベクトルを選択できなくなると停止します。 ${\displaystyle \{v_{\beta }\mid \beta <\alpha \}}$

より正式には、超限再帰定理は次のように述べることができます。

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

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

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

超限再帰定理（バージョン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 ₃のドメインが十分に広い必要があることに注意してください。これらの特性を満たすシーケンスの一意性は、超限帰納法を使用して証明できます。

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

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

ヴィタリ集合の次の構成は、選択公理を超限帰納法による証明に使用できる 1 つの方法を示しています。

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

上記の議論では、実数を整列させるために、最初に選択公理を本質的に使用しています。そのステップの後、選択公理は再び使用されません。

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

• 数学的帰納法
• ∈誘導
• 超限数
• 根拠のある帰納法
• ゾルンの補題

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

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