クリーネの再帰定理
第一再帰定理は帰納的な枚挙作用素の不動点に関するものである。枚挙作用素とは対 ( A , n ) {\displaystyle (A,n)} の集合であって、 A {\displaystyle A} はコード化された有限集合、 n {\displaystyle n} は自然数である。 関数が枚挙作用素を通じて定義される場合など n {\displaystyle n} は自然数の対のコードと見做されることがある。枚挙作用素は枚挙還元性の研究で最も重要な概念のひとつである。
枚挙作用素 Φ は自然数の集合から自然数の集合への関数を定める:
Φ ( X ) = { n ∣ ∃ A ⊆ X [ ( A , n ) ∈ Φ ] } . {\displaystyle \Phi (X)=\{n\mid \exists A\subseteq X[(A,n)\in \Phi ]\}.}
この証明では以下で定義される計算可能関数 h {\displaystyle h} を利用する。 自然数 x {\displaystyle x} が与えられたとき、関数 h {\displaystyle h} は次のような計算を行う部分計算可能関数の指標を出力する:
入力 y {\displaystyle y} が与えられると、 まず φ x ( x ) {\displaystyle \varphi _{x}(x)} の計算を試行する。この計算が出力 e {\displaystyle e} を返したならば、そのときに限って φ e ( y ) {\displaystyle \varphi _{e}(y)} を計算してその値を返す。
任意の x {\displaystyle x} について、 φ x ( x ) {\displaystyle \varphi _{x}(x)} が停止するならば φ h ( x ) = φ φ x ( x ) {\displaystyle \varphi _{h(x)}=\varphi _{\varphi _{x}(x)}} であり、停止しないならば φ h ( x ) {\displaystyle \varphi _{h(x)}} は停止しない。
第一再帰定理の前半の証明は、空集合から始めて枚挙演算子 Φ {\displaystyle \Phi } の反復によって得られる。まず集合列 F k {\displaystyle F_{k}} を次のように帰納的に定義する:
F 0 = ∅ , {\displaystyle F_{0}=\varnothing ,}
F k + 1 = F k ∪ Φ ( F k ) {\displaystyle F_{k+1}=F_{k}\cup \Phi (F_{k})}
次に F = ⋃ F k {\displaystyle F=\bigcup F_{k}} とおく。 F k {\displaystyle F_{k}} は一様に帰納的な増大列であるので F {\displaystyle F} は帰納的可算である。さらに F {\displaystyle F} は Φ {\displaystyle \Phi } の最小不動点である。ここで構成した F k {\displaystyle F_{k}} は完備半順序で定義された単調関数の不動点の存在を述べるクリーネの不動点定理のクリーネ鎖に対応している。
定理の後半は前半から従う。実際 Φ {\displaystyle \Phi } を帰納作用素とすると上の証明の F {\displaystyle F} が部分関数のグラフになることが k {\displaystyle k} に関する帰納法で確かめられる。