原始再帰関数
直観的に、加算は次の規則で再帰的に定義できる:
add(0, x) = x,
add(n + 1, x) = add(n, x) + 1.
これを厳密な原始再帰関数の定義に当てはめるため、次のように定義する:
add(0, x) = P1(x),
add(S(n), x) = S(P1(add(n, x), n, x)).
ここで、P1 は射影関数であり、3つの引数をとり、最初の引数を返す。また、S は後者関数である。
P1 は単純な恒等関数であり、上述の原始再帰関数の定義に当てはめるために導入されている。同語反復的な定義となっていた "+" 記号が無くなっている点に注意されたい。
#C: 述語 Q の各引数を関数 χ1 , ..., χm で置き換えた述語 P は χ1, ..., χm, Q において原始再帰的である。
#D: 以下の述語は Q と R において原始再帰的である:
否定: NOT_Q(x) . 論理和: Q(x) V R(x), 論理積: Q(x) & R(x), 含意: Q(x) → R(x) 同値: Q(x) ≡ R(x)
#E: 以下の述語は、述語 R において原始再帰的である:
(Ey)y<z R(x, y): (Ey)y<z とは、「ある z よりも小さい y が存在し、~が成り立つ」という意味 (y)y<z R(x, y): (y) とは、「z よりも小さい全ての y について ~ が成り立つ」という意味 μyy<z R(x, y): 演算子 μyy<z R(x, y) は最小化演算子あるいはμ演算子の限定された形式である。その定義は「z より小さい最小の y について R(x, y) が真である」ことを意味する。
#F: ケースによる定義: Q1, ..., Qm は相互排他的述語であるとき、φ1, ..., Q1, ... Qm において以下の関数は原始再帰的である:
φ(x) = φ1(x) if Q1(x) is true, . . . . . . . . . . . . . . . . . . . φm(x) if Qm(x) is true φm+1(x) otherwise
#G: φ が方程式 φ(y, x) = χ(y, NOT-φ(y; x2, ... xn ), x2, ... xn を満足するとき χ において φ は原始再帰的である。