Zoran Skoda primitive recursion

Let $S : N\to N$ be the successor function on the set of natural numbers as defined by Peano axioms.

Primitive Recursion Theorem. Let $g: N^n\to N$ and $h: N^{n+2}\to N$. Then there is a unique function $f: N^{n+1}\to N$ such that for all $x_1, x_2,\ldots, x_n, y \in N$ the following equations hold

$$h(x_1, x_2, \ldots, x_n, 0) = g(x_1, x_2, \ldots, x_n)$$

$$f(x_1 ,x_2,\ldots, x_n, S(y)) = h(x_1,x_2,\ldots, x_n, y, f(x_1, x_2,\ldots,x_n, y)).$$

For a proof see Appendix A3 in

• Joel W. Robbin, Mathematical logic, a first course, Benjamin 1969.

See also recursion.