Zoran Skoda
primitive recursion

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

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

h(x 1,x 2,,x n,0)=g(x 1,x 2,,x n)h(x_1, x_2, \ldots, x_n, 0) = g(x_1, x_2, \ldots, x_n)
f(x 1,x 2,,x n,S(y))=h(x 1,x 2,,x n,y,f(x 1,x 2,,x n,y)).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.