第一再帰定理の証明の概略
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/10/03 01:23 UTC 版)
「クリーネの再帰定理」の記事における「第一再帰定理の証明の概略」の解説
第一再帰定理の前半の証明は、空集合から始めて枚挙演算子 Φ {\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} に関する帰納法で確かめられる。
※この「第一再帰定理の証明の概略」の解説は、「クリーネの再帰定理」の解説の一部です。
「第一再帰定理の証明の概略」を含む「クリーネの再帰定理」の記事については、「クリーネの再帰定理」の概要を参照ください。
- 第一再帰定理の証明の概略のページへのリンク
