関数の再帰的定義
ここではある形の関数の再帰的定義について考えます。
に対して
を
と定義します。
、
とおきます。
、
とおくと
は
を満たす最小の集合となります。
に対して
と定義します。
とおくと
が成り立つので、自然数の性質より となります。
計算可能性の議論にはこれだけでも良いとは思うのですが
によって関数 を定義するには、任意の
と任意の
に対して
かつ
ならば
が成り立つ必要があります。以下でこれを示します。
となるので
となります。
とすると
なので
となります。よって
となります。
よって のときには成り立ちます。
次に のときには成り立つと仮定します。
とします。
、
とおくと
となります。
となるので
となります。
とすると
なので
となります。よって
となって
のときにも成り立ちます。
よって帰納法により任意の と任意の
に対して
かつ
ならば
が成り立ちます。よって
によって関数 を定義することができます。