importance of primitive recursion

In this entry, we show that the operationMathworldPlanetmath of primitive recursion is an important ingredient in the definition of primitive recursive functionsMathworldPlanetmath. Very basic arithmetic functions, such as additionPlanetmathPlanetmath, depend on primitive recursion in an essential way. One can not go very far without it.

One way to prove this is to come up with a property on those functions which are derivablePlanetmathPlanetmath from the initial functions using functionalPlanetmathPlanetmathPlanetmath compositionMathworldPlanetmath alone, and then find a primitive recursive function that fails this property. Thus, we begin with the following definition:

Definition. Let 𝒫0 be the smallest subset of the set 𝒫 of primitive recursive functions such that

  1. 1.

    (initial functions): z,s,pmk𝒫0 for all positive integers m,k with mk.

  2. 2.

    (closure under functional composition): if f,g1,,gm𝒫0 with f m-ary and gi n-ary, then the n-ary function h:=f(g1,,gm)𝒫0 as well.

From the definition above, we observe that any function f(x1,,xn) obtained without the use of the successor function s must be bounded by max{x1,,xn}. Now, since one application of s increments the input by 1, a finite applications of s in the construction of f results in f being bounded by max{x1,,xn} plus some fixed integer. This is the property we seek, and we prove it formally:

Proposition 1.

For any fPR0 with arity n, the following condition is satisfied:

(*) there is an integer r0 such that f(x1,,xn)max{x1,,xn}+r.


For each integer n0, let 𝒳n be the subset of 𝒫0 that contains all the initial functions, as well as functions derivable from the initial functions by applying functional composition at most n times. The following facts are clear:

  1. 1.

    𝒳0 is the set of all initial functions,

  2. 2.


  3. 3.

    and 𝒫0={𝒳nn}, where contains 0 in this context.

We prove our assertion by inductionMathworldPlanetmath on n. In fact, we will prove a stronger assertion:

in the conditon (*) above, r=n+1 can be picked for every function in 𝒳n.

  • For n=0, it is clear that all initial functions have the desired property: r=0 for z and pmk, and r=1 for s. In either case, we can pick r=1.

  • Suppose now that we can pick r=i+1 for any function in 𝒳i.

  • Let f be an k-ary function in 𝒳i+1. If f𝒳i, then r=i+1 can be picked by assumption. Otherwise, f=h(g1,,gm), where h is m-ary, and each gj is k-ary. Furthermore, gj𝒳ij, each iji, and h𝒳t, where t=i-max{i1,,im}. Then, by assumption gj(x1,,xk)x+ij+1x++1 for all j{1,,m}, where x=max{x1,,xk} and =max{i1,,im}. As a result,

    f(x1,,xk) = h(g1(x1,,xk),,gm(x1,,xk))

    This proves the stronger assertion.

Now, if we pick any f𝒫0, then f𝒳m for some m by the third fact above. The proof is now completePlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath by setting r=m+1. ∎

Now, we show the following:

Proposition 2.



We prove that add(x,y)=x+y does not have property (*) above. But if it does, then add(x,y)max{x,y}+r for some non-negative integer r. Then, for an arbitrary non-negative integer n, 2n=add(n,n)max{n,n}+r=n+r, so that nr, a contradictionMathworldPlanetmathPlanetmath (pick n=r+1)! ∎

In fact, the above proof shows the function f(x)=2x, simpler than addition in the sense that f is unary, can not be defined in terms of the initial functions and functional composition alone. Primitive recursion is required at least once to define f.

Remark. In fact, one can obtain an infinite chain of subsets of 𝒫 in the following manner: 𝒫n is the smallest set of all primitive recursive functions generated by the initial functions, closed under functional composition, and at most n applications of primitive recursion. Then

𝒫n𝒫n+1  and  𝒫=i=0𝒫i

For example, addition is in 𝒫1-𝒫0, as was shown earlier. Furthermore, it is not hard to show that multiplication is in 𝒫2-𝒫1, and exponentiation is in 𝒫3-𝒫2. In fact, the Ackermann functionMathworldPlanetmath can be utilized to show that each 𝒫n𝒫n+1 is proper. Using this technique, it is possible to show that the Ackermann function is a total recursive function that is not primitive recursive. With respect to the set of elementary recursive functions, it can be shown that =𝒫3.

Title importance of primitive recursion
Canonical name ImportanceOfPrimitiveRecursion
Date of creation 2013-03-22 19:05:21
Last modified on 2013-03-22 19:05:21
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 12
Author CWoo (3771)
Entry type Feature
Classification msc 03D20