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