In the following, \(n\), \(m\), \(k\), and \(i\) are positive natural numbers.
Constant
\(Z(x_1, x_2, \ldots, x_n) = q\)
where \(q\) is a natural number.
Successor
\(S(x) = x^\prime\)
Projection
\(P_i(x_1, x_2, \ldots x_n) = x_i\)
where \(i \in \{ 1, 2, \ldots, n \}\).
Composition
\(C(x_1, x_2 , \ldots, x_m ) =\) \(f(g_1(x_1, x_2, \ldots, x_m),\) \(g_2(x_1, x_2, \ldots, x_m),\) \( \ldots,\) \(g_n(x_1, x_2, \ldots, x_m))\)
where \(f\) and \(g_i\) are primitive recursive for \(i \in \{ 1, 2, \ldots, n \}\).
Recursion
\(h(0, x_1, x_2, \ldots, x_n) = f(x_1, x_2, \ldots, x_n)\)
\(h(y^\prime, x_1, x_2, \ldots, x_n) = g(y, h(y, x_1, x_2, \ldots, x_n), x_1, x_2, \ldots, x_n)\)
where \(f\) and \(g_i\) are primitive recursive.
Examples
Addition
\(A(0, x) = P_1(x)\)
\(A(y^\prime, x) = F(y, A(y, x), x)\)
\(F(z_1, z_2, z_3) = S(P_2(z_1, z_2, z_3))\)
Predecessor
\(R(0) = 0\)
\(R(y^\prime) = P_1(y, R(y))\)
Subtraction
\(h(0, x) = x\)
\(h(y^\prime, x)) = F(y, h(y, x), x)\)
\(F(z_1, z_2, z_3) = R(P_2(z_1, z_2, z_3))\)