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.

Created on October 5, 2017 at 09:14:39. See the history of this page for a list of all contributions to it.