■
が原始的関数である事を示すのに以下の補題が必要なんだけどその証明が4行しかなくて一読しただけでは分からなかったので論理的に細かく追ってみた。
前提
真偽の定まる関数pを述語と呼ぶ。 述語pに対してを特徴関数とよび、その定義は 述語pが真の時0、偽の時1となる関数である。
補題 1.3.12
述語 が原始的ならば、 は原始的関数である。 ただし、
証明
の特徴関数をとすると の特徴関数は となる。 何故ならばなるが存在する時、特徴関数は0となるが、 存在しなければ1である。 すなわちを満たす全てにおいて を満たすが存在しなければ1、 一つでも存在すれば0なのでその特徴関数は上記のように置ける。 ここで をとおく。 を固定したときの値は、 はじめてとなる以後は0、 それ以外は1である。 その値を特別にとすると この式の各項は全て1なのでその和はとなる。 また は各項全て0であるので和も0である。 以上より となる。 ところではが真となる境界値なので その物である。ただし、が真とならない場合は は全て1なのでそのに関する和はその物である。 以上より、 と表す事ができ、原始的述語の特徴関数が原始的関数である事と、 以前の補題によりその積、和が原始的関数である事により命題の関数は 原始的関数である。
ここまで細かく論理の飛躍を追ってようやく理解出来た。数学の本ってのはえてして飛躍が多すぎるんだよなぁ。
さて、ここで
とおけるんだけど、何でおけるかっていうと を満たす最小のはだから。
これよりも原始的関数である事がわかったよ。
が原始的関数である事は既に証明されてるので四則演算が原始的関数である事が証明され模様。
そんで原始的関数はNプログラムという抽象化されたプログラムで計算出来る事が証明される。
この後に有名なAckermann関数という関数が原始的関数でない事が証明されるのでこれはまずいという事でそれを拡張した帰納的関数が登場。