importance of primitive recursion
In this entry, we show that the operation of primitive recursion is an important ingredient in the definition of primitive recursive functions. Very basic arithmetic functions, such as addition, 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 derivable from the initial functions using functional composition alone, and then find a primitive recursive function that fails this property. Thus, we begin with the following definition:
Definition. Let be the smallest subset of the set of primitive recursive functions such that
From the definition above, we observe that any function obtained without the use of the successor function must be bounded by . Now, since one application of increments the input by , a finite applications of in the construction of results in being bounded by plus some fixed integer. This is the property we seek, and we prove it formally:
For any with arity , the following condition is satisfied:
(*) there is an integer such that .
For each integer , let be the subset of that contains all the initial functions, as well as functions derivable from the initial functions by applying functional composition at most times. The following facts are clear:
is the set of all initial functions,
and , where contains in this context.
We prove our assertion by induction on . In fact, we will prove a stronger assertion:
in the conditon (*) above, can be picked for every function in .
For , it is clear that all initial functions have the desired property: for and , and for . In either case, we can pick .
Suppose now that we can pick for any function in .
Let be an -ary function in . If , then can be picked by assumption. Otherwise, , where is -ary, and each is -ary. Furthermore, , each , and , where . Then, by assumption for all , where and . As a result,
This proves the stronger assertion.
Now, if we pick any , then for some by the third fact above. The proof is now complete by setting . ∎
Now, we show the following:
We prove that does not have property (*) above. But if it does, then for some non-negative integer . Then, for an arbitrary non-negative integer , , so that , a contradiction (pick )! ∎
In fact, the above proof shows the function , simpler than addition in the sense that 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 .
Remark. In fact, one can obtain an infinite chain of subsets of in the following manner: is the smallest set of all primitive recursive functions generated by the initial functions, closed under functional composition, and at most applications of primitive recursion. Then
For example, addition is in , as was shown earlier. Furthermore, it is not hard to show that multiplication is in , and exponentiation is in . In fact, the Ackermann function can be utilized to show that each 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 .
|Title||importance of primitive recursion|
|Date of creation||2013-03-22 19:05:21|
|Last modified on||2013-03-22 19:05:21|
|Last modified by||CWoo (3771)|