We want to show that the following function $F$ is primitive recursive (using the primitive recursion scheme) :

For all $x,p,a\in \mathbb N$,


where $\eta, g : \mathbb{N}\to \mathbb{N}$ and $h: \mathbb{N}^3 \to \mathbb{N}$ are primitive recursive functions.

We want to apply the primitive recursion scheme which is defined as follows : if $g',h'$ are primitive recursive functions then the function $f$ defined by : $f(\bar y,0)=g'(\bar y)$ and $f(\bar y,x+1)=h'(\bar y,x,f(\bar y,x))$ is also primitive recursive.

Then I have to find the functions $f,g',h'$.

To build $g'$ let us consider that $\eta^{p}(a)=k(p,a)$ hence $g'(a,p)=g \circ k(p,a)$ which is a primitive recursive function by hypothesis.

To build $h'$ it seems that the difficulty is to get rid of the term in $\eta^{(p-(x+1))}(a)$ which depends of $x$ in particular. In fact we want $h'(p,a,x,F(p,a,x)) = h(-,-,-)$ but I am stuck. Any hints for this step would be very helpful

Thanks in advance !


1 Answer 1


Note that you can show that $k(p,a) = \eta^{p}(a)$ is primitive recursive. Also addition and subtraction are primitive recursive, thus definiing $h'(p,a,x,...) := h(k(p-(x+1),a),...) = h(\eta^{p-(x+1)}(a),...)$ is not a problem.

  • $\begingroup$ Thank you for the precisions. Indeed all the operations here are primitive recursive. Maybe it could be better to write $k(p-(x+1),a)=k'(p,a,x)$ because this function $\eta^{p-(x+1)}(a)$ depends on $3$ parameters no ? $\endgroup$
    – Maman
    Sep 26, 2022 at 13:20
  • 1
    $\begingroup$ Yes if you want to be rigorous. But note that composition of prim. rec. function is also prim. rec. So that $k(sub(p,add(x,1)),a)$ is prim. rec. directly follows from the definition that (finite) composition of primitive recursive functions is also primitive recursive. $\endgroup$
    – plshelp
    Sep 27, 2022 at 9:35

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.