■

帰納的関数の主要定理は大体理解したので一つ問題を解いてみる。

問題 1.4.9

問題

述語  の特徴関数 
が帰納的関数のときpを帰納的述語という。
帰納的述語の最小関数  は
（定義域が)の帰納的関数である事を示せ。

証明

帰納的述語の最小解関数  に最小値が存在するとしその値を とする。
特徴関数の定義により を固定したとき、
 未満の  について特徴関数  の値は1であり
  以上の  での値は0である。
よって

となるので

と表せる。
ところで、仮定より  は帰納的関数であるのでKleeneの標準形定理により 
適当な原始的関数と原始的述語を使って

と表す事が出来る。
※とは別の述語である。
すなわち

となり、右辺は原始的述語の最小解関数と原始的関数の合成関数の和で表され、
これは帰納的関数の定義により帰納的関数である。
また、定義域はが真となるが存在する領域なので となる。