超限帰納法

超限帰納法（ちょうげんきのうほう、英: Transfinite induction）は、数学的帰納法の整列集合上への拡張である、例えば順序数や基数の集合の上で行う。この手法の正当性はZFCの定理である。

$\omega ^{\omega }$ までの順序数の表現。螺旋の各回転は$\omega$の1回冪を表す。超限帰納法では、基本ケース(0に対応)、後続者ケース(後続順序数に対応)、極限ケース(極限順序数に対応)で証明する必要がある。

各ケースにおける帰納法

性質 $P(\alpha )$ が全ての順序数 $\alpha$ に定義されているとする。全ての $\beta <\alpha$ に対して $P(\beta )$ が正しいと仮定した上で、そして $P(\alpha )$ も正しいことを示す。 このとき超限帰納法は全ての順序数に対して $P$ が真であることを結論する。

通常、超限帰納法による証明は次の3ケースに分解される:

• 基本ケース: $P(0)$ が真であることを証明する。
• 後続者ケース: 全ての後続順序数 $\alpha +1$ に対して、$P(\alpha +1)$ を $P(\alpha )$ から証明する。(必要ならば全ての $\beta <\alpha$ に対しての $P(\beta )$ を仮定してもよい。)
• 極限ケース: 全ての極限順序数 $\lambda$ に対して、$P(\lambda )$ であることを $P(\beta )$（全ての $\beta <\lambda$ について）から証明する。

この3つのケースは、考慮する順序数の種類を除けば全て同じである。これらは形式的には別々に考える必要はないが、実際には証明は別個に行う必要があるほど異なるのが普通である。0は極限順序数と見なされることがあり、極限順序数と同じケースとして証明で扱われることがある。

超限再帰

超限再帰は超限帰納法に似た手法である; 何かを全ての順序数について証明する代わりに、各順序数に対するオブジェクトからなる列を構成する。

例として、（無限次元でもよい）ベクトル空間の基底は空集合から始めて、各順序数 α > 0 に対してベクトルの線型包にないベクトル$\{v_{\beta }\mid \beta <\alpha \}$ を選ぶことで作ることができる。この処理は、どのベクトルも選択できないときに停止する。

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

超限再帰定理(バージョン1). クラス関数 G: V → V (ここで V は全ての集合からなるクラス)が与えられたとき、次の超限列が一意的に存在する。F: Ord → V (ここで Ord は全ての順序数からなるクラス) : 全ての順序数 α について$F(\alpha )=G(F\upharpoonright \alpha )$、ここで $\upharpoonright$ は F の定義域を順序数 α へ制限することを表す。

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

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

• F(0) = g₁,
• F(α + 1) = G₂(F(α)), for all α ∈ Ord,
• $F(\lambda )=G_{3}(F\upharpoonright \lambda )$, for all limit λ ≠ 0.

G₂, G₃ の定義域は、上記の性質を意味のあるものにするのに十分広いことが必要であることに注意。これらの性質を満たす数列の一意性は、超限帰納法を用いて証明できる。

より一般的には、任意の整礎関係 Rに対する超限再帰によってオブジェクトを定義することができる。(ここで R は集合でなく、真クラスであっても集合状な関係であればよい; すなわち、任意の x に対し、yRxを満たす yの集まりが集合になっていればよい)

選択公理との関係

帰納法や再帰を用いた証明や構成では、しばしば選択公理を用いて、超限帰納法で扱えるような整列された関係を作り出す。しかし、問題にしている関係がすでに整列されている場合は、選択公理を用いずに超限帰納法を用いることができる。例えば、ボレル集合に関する多くの結果は、ボレル階層上のランクに関する超限帰納法によって証明される。ボレル階層のランクは既に整列されているので、整列するために選択公理は必要ない。

次のヴィタリ集合の構成は、選択公理を超限帰納法による証明に使うことができる一つの方法を示している:

まず、実数を整列して（ここで整列可能定理に選択公理を用いる）、列 $\langle r_{\alpha }\mid \alpha <\beta \rangle$ を得る。ここでβ は連続体濃度を持つ順序数である。v₀ は r₀ とする。v₁ は r_α1 とする。ここで α₁ は r_α1 − v₀ が 有理数でなくなる最小のものである。続けて各ステップでは、r数列のうち、v数列でこれまでに構成されたどの要素とも有理数差を持たない最小の実数を取り続けていく。r 列の全ての実数がなくなるまで続ける。最後にできるv列はヴィタリ集合の列挙になっている。上記の議論は、実数を整列するために、冒頭で選択の公理を本質的な形で用いている。このステップの後、選択の公理は再び使われてはいない。

選択の公理の他の使い方はもっと微妙である。 例えば、超限再帰による構成では、αまでの数列が与えられたとき、A_α+1に一意な値を指定することはなく、A_α+1が満たさなければならない条件だけを指定し、この条件を満たす集合が少なくとも一つ存在することを論じることがよくある。各段階でそのような集合の一意的な例を定義することができない場合、各段階でそのような集合を1つ選択するために（ある形式の）選択の公理を呼び出す必要があるかもしれない。可算の長さの帰納法や再帰では、より弱い従属選択公理で十分である。集合論者にとって興味深いツェルメロ＝フレンケル集合論のモデルには、従属選択の公理は満たすが完全な選択の公理は満たさないものがあるので、特定の証明が従属選択だけを必要とするという知識は有用である．

関連項目

• 数学的帰納法
• ∈-induction
• 超限数
• 整礎関係
• ツォルンの補題
• イプシロン数

参考文献

• Suppes, Patrick (1972), “Section 7.1”, Axiomatic set theory, Dover Publications, ISBN 0-486-61630-4, https://books.google.com/books?id=sxr4LrgJGeAC&q=%22Transfinite+induction%22 

外部リンク

• Emerson, Jonathan; Lezama, Mark; Weisstein, Eric W. "Transfinite Induction". mathworld.wolfram.com (英語).