Primitive recursive function

Primitive recursive functions are a class of functions which, while a subset of the recursive

functions (which themselves are exactly those functions

which we call "computable"), are an important building block

on the way to a full formalization of computability.

Primitive recursive functions are functions from natural numbers to natural numbers, defined as follows (from here on we will write "p.r." for primitive recursive):

Take as axioms the initial set of numbers and functions:

The constant 0 is p.r.

The "successor function" S is p.r.

The "projection functions" P_iⁿ are p.r.

Where the "successor function" takes the number k and returns the number

one greater than k on the natural number line, and the "projection

functions" P_iⁿ take n arguments and return the ith one.

Now consider the following operations:

Given f a k-ary p.r. function and k l-ary functions g₀,...,g_k-1 p.r. functions, the composition of f with g₀,...,g_k-1 is p.r., i.e. the function h(x₀,...,x₁)=f(g₀(x₀,...,x₁),...,g_k-1(x₀,...,x_l-1)) is p.r.

Given f a k-ary p.r. function and g a (k+2)-ary p.r. function, then the (k+1)-ary function defined as the primitive recursion of f and g is p.r., i.e. the function h where h(0,x₀,...,x_k-1)=f(x₀,...,x_k-1) and h(n+1,x₀,...,x_k-1)=g(n,h(n,x₀,...,x_k-1),x₀,x_k-1)) is p.r.

The closure of the operations over the initial set of numbers and functions forms the set of p.r. functions.

(Note that the projection functions allow us to get around the apparent rigidity in terms of the arity of the functions above, as via composition we can pass any subset of the arguments.)

Example P.R. definitions

addition

subtraction

exponentiation

(need actual definitions)

P.R. functions are a subset of the recursive functions

(need outline of proof/explanation)