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 mโ‰คk.

  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 fโˆˆPโขR0 with arity n, the following condition is satisfied:

(*) there is an integer rโ‰ฅ0 such that fโข(x1,โ€ฆ,xn)โ‰คmaxโก{x1,โ€ฆ,xn}+r.

Proof.

For each integer nโ‰ฅ0, 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.

    ๐’ณnโŠ†๐’ณn+1,

  3. 3.

    and ๐’ซโขโ„›0=โ‹ƒ{๐’ณnโˆฃnโˆˆโ„•}, 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 ijโ‰คi, and hโˆˆ๐’ณt, where t=i-maxโก{i1,โ€ฆ,im}. Then, by assumption gjโข(x1,โ€ฆ,xk)โ‰คx+ij+1โ‰คx+โ„“+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))
    โ‰ค maxโก{gjโข(x1,โ€ฆ,xk)โˆฃj=1,โ€ฆ,m}+t+1
    โ‰ค (x+โ„“+1)+t+1=x+(i+1)+1.

    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.

๐’ซโขโ„›0โŠ‚๐’ซโขโ„›.

Proof.

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, 2โขn=addโก(n,n)โ‰คmaxโก{n,n}+r=n+r, so that nโ‰คr, a contradictionMathworldPlanetmathPlanetmath (pick n=r+1)! โˆŽ

In fact, the above proof shows the function fโข(x)=2โขx, 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