# How to prove that the set of recursive primitive functions is closed under

the scheme of iteration ?

Here is the scheme of iteration : for $$g : \mathbb{N}^p\to \mathbb{N}$$ and $$h:\mathbb{N}^{p+1}\to \mathbb{N}$$ two primitive recursive functions we associate $$f: \mathbb{N}^{p+1}\to \mathbb{N}$$ defined by :

$$f(\bar a, 0)=g(\bar a)\\ f(\bar a, x+1)=h(\bar a, f(\bar a, x)).$$

Here is my attempt :

Let consider a primitive recursive function $$F: \mathbb{N}^{p+1}\to \mathbb{N}$$.

Then by the primitive recursion : $$F(\bar a,0))=k(\bar a) \\ F(\bar a, x+1)= l(\bar a, x, F(\bar a,x))$$ where $$k$$ and $$l$$ are recursive primitive functions.

We want $$F$$ to check the scheme of iteration. First we can take $$k\equiv g$$ and then how can make a link with $$h$$ and $$l$$ ?

Take $$l(\bar{a}, x, y) = h(\bar{a},y)$$. More precisely, writing $$\pi_i$$ for the $$i$$-th projection from $$\mathbb{N}^{p+2}$$ to $$\mathbb{N}$$, we see that $$l$$ is the composition of $$h$$ and projections, as follows: $$l(a_1, \ldots, a_p, x, y) = h(\pi_1(a_1, \ldots, a_p, x, y), \ldots, \pi_p(a_1, \ldots, a_p, x, y), \pi_{p+2}(a_1, \ldots, a_p, x, y))$$
• Thank you for answering but the two functions do not have the same arity, so how can it be equal ? Moreover why do we have to take $y$ ? We cannot just put $F(\bar a, x)$ instead ? Oct 13, 2021 at 14:14
• The change in arity is accomplished by composing with projections. I'll add an explanation. No, you cannot put $F(\bar{a}, x)$ into the definition, because on the left-hand side $l$ must be applied to variables. Oct 13, 2021 at 15:18
• Thank you for the details ! In fact it is the function $h(\pi_1,...,\pi_p,\pi_{p+2}): \mathbb{N}^{p+2}\to \mathbb{N}$ which is recursive primitive by composition right ? Oct 13, 2021 at 16:29
• Just one thing, for instance if we want to prove that $add : \mathbb{N}^2\to \mathbb{N},(x,y)\mapsto x+y$ is primitive recursive using the primitive recursion we have $add(x,0)= x = \pi_1^1 =k$ and $add(x,y+1)=x+(y+1)=s(x+y)= l(x,y,add(x,y))= s(\pi_{3}^{3}(x,y, add(x,y)))$ ? As you said the problem is that $add(x,y)$ is not a variable so should I write $l(x,y,x+y)$ or $l(x,y,t)$ instead ? Oct 13, 2021 at 16:45
• You should write $l(x,y,t)$. When you substitute $x + y$ for $t$ you will get the desired equation. Oct 13, 2021 at 21:09