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$ ?

Thanks in advance !


1 Answer 1


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)) $$

  • $\begingroup$ 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 ? $\endgroup$
    – Maman
    Commented Oct 13, 2021 at 14:14
  • $\begingroup$ 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. $\endgroup$ Commented Oct 13, 2021 at 15:18
  • $\begingroup$ 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 ? $\endgroup$
    – Maman
    Commented Oct 13, 2021 at 16:29
  • $\begingroup$ 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 ? $\endgroup$
    – Maman
    Commented Oct 13, 2021 at 16:45
  • 1
    $\begingroup$ You should write $l(x,y,t)$. When you substitute $x + y$ for $t$ you will get the desired equation. $\endgroup$ Commented Oct 13, 2021 at 21:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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