1
$\begingroup$

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 !

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • $\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$ 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$ 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$ 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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.