超限帰納法
性質 P ( α ) {\displaystyle P(\alpha )} が全ての順序数 α {\displaystyle \alpha } に定義されているとする。全ての β < α {\displaystyle \beta <\alpha } に対して P ( β ) {\displaystyle P(\beta )} が正しいと仮定した上で、そして P ( α ) {\displaystyle P(\alpha )} も正しいことを示す。 このとき超限帰納法は全ての順序数に対して P {\displaystyle P} が真であることを結論する。
通常、超限帰納法による証明は次の3ケースに分解される:
基本ケース: P ( 0 ) {\displaystyle P(0)} が真であることを証明する。
後続者ケース: 全ての後続順序数 α + 1 {\displaystyle \alpha +1} に対して、 P ( α + 1 ) {\displaystyle P(\alpha +1)} を P ( α ) {\displaystyle P(\alpha )} から証明する。
超限再帰は超限帰納法に似た手法である; 何かを全ての順序数について証明する代わりに、各順序数に対するオブジェクトからなる列を構成する。
例として、(無限次元でもよい)ベクトル空間の基底は空集合から始めて、各順序数 α > 0 に対してベクトルの線型包にないベクトル { v β ∣ β < α } {\displaystyle \{v_{\beta }\mid \beta <\alpha \}} を選ぶことで作ることができる。この処理は、どのベクトルも選択できないときに停止する。
より正式には、超限再帰定理を次のように述べることができる:
超限再帰定理(バージョン1). クラス関数 G: V → V (ここで V は全ての集合からなるクラス)が与えられたとき、次の超限列が一意的に存在する。F: Ord → V (ここで Ord は全ての順序数からなるクラス) : 全ての順序数 α について F ( α ) = G ( F ↾ α ) {\displaystyle F(\alpha )=G(F\upharpoonright \alpha )} 、ここで ↾ {\displaystyle \upharpoonright } は F の定義域を順序数 α へ制限することを表す。