2
$\begingroup$

The set of primitive recursive function is defined inductively, starting with a countably infinite set consisting of the constant zero, the successor and all projections $P^n_i$, with $n \ge 1$ and $1 \le i \le n$. It seems very natural to include all projections, since one wants to define recursive functions of an arbitrary (but finite) number of arguments. But is it really necessary to do so if one only wants to construct functions of a single argument?

More precisely, my question is the following:

Does there exist some $n \ge 1$ such that every primitive recursive function of arity $1$ can be obtained by composition and primitive recursion from the constant zero, the successor and only projections of arity $k \le n$?

I think the answer should be no, but given $n$, I don't know how to construct a function that can't be obtained without using projections of arity at least $n+1$.

In order to prove that a certain function $f : \mathbb{N}^k \rightarrow \mathbb{N}$ can't belong to a certain set of functions $S$ (usually defined by induction), most of the arguments I've seen in computability theory exploit a bound on $f(x_1, \dotsc, x_k)$. I'm thinking of the proof that the Ackermann function is not primitive recursive, and the proof that the sum of natural numbers can't be obtained without using primitive recursion.

Therefore I wanted to use a similar reasoning here, but in this case I can't see any bound for the growth of the functions which can be written using only projections of arity at most $n$.

Any help or references to texts discussing problems of this kind would be very appreciated. Thanks.

$\endgroup$
2
$\begingroup$

Contrary to what I thought, the answer is yes: there exists an $n$ such that projections of arity up to $n$ are enough to write all unary primitive recursive functions. In fact, $n = 3$ is enough! (And I think it must be the least $n$ for which the statement holds.)

Theorem 7.3 in R. M. R. Robinson, Primitive recursive functions, Bull. Amer. Math. Soc. 53 (1947) says precisely that the class of unary primitive recursive functions can be characterized using only the successor, the excess over a square, unary composition, addition and pure recursion. It is quite easy (but a bit long) to show that these functions and operations require only projections of arity at most $3$ to be defined. Therefore this proves the statement for $n = 3$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.