原始再帰関数
射影関数を使って、上述の関数群での引数の個数を変化させることができる。射影関数の合成を行うと、ある関数の引数のサブセットを別の関数に渡すことができる。例えば、2 項原始再帰関数 g と h を次のように合成する。
f ( a , b , c ) = g ( h ( a , c ) , h ( a , b ) ) {\displaystyle f(a,b,c)=g(h(a,c),h(a,b))\!}
f も原始再帰的である。射影関数による形式的定義は以下のようになる。
f ( a , b , c ) = g ( h ( P 1 3 ( a , b , c ) , P 3 3 ( a , b , c ) ) , h ( P 1 3 ( a , b , c ) , P 2 3 ( a , b , c ) ) {\displaystyle f(a,b,c)=g(h(P_{1}^{3}(a,b,c),P_{3}^{3}(a,b,c)),h(P_{1}^{3}(a,b,c),P_{2}^{3}(a,b,c))} .
an) 絶対値: | a-b | =def a ∸ b + b ∸ a ~sg(a): NOT[signum(a}]: a=0 なら sg(a)=1 、そうでなく a>0 なら sg(a)=0 sg(a): signum(a): a=0 なら sg(a)=0 そうでなく a>0 なら sg(a)=1 剰余 (a, b): a が b で割り切れない場合の余り 除算 [ a | b ]: 剰余が 0 の場合。 s = b: sg | a - b | a < b: sg( a' ∸ b ) a | b: 除算 Pr(a): a は素数 Pr(a) =def a>1 & NOT(Exists c)1<c<a [ c|a ] Pi: i+1 番目の素数 (a)i : pi =def μx [ x<a [pi|a & NOT(pi |a ] の指数 ai 。μx は #E で説明されている最小化演算子。 lh(a): a の「長さ」または消えない指数 (non-vanishing exponents) の個数 a*b: a と b が素因数であるとき、a*b は素因数の乗算結果を示す。 lo(x, y): 基数 y での x の対数
以下では、x =def xi, ... xn という省略形を使用。添え字も必要に応じて使われる。「x において原始再帰的」とは「x が原始再帰的な場合は原始再帰的である」という意味。
#A: 関数 Ψ と定数 q1 , ... qn から明示的に定義できる関数 φ は Ψ において原始再帰的である。
#B: 総和 Σy<z ψ(x, y) と総乗 Πy<zψ(x, y) は ψ において原始再帰的である。