# How to show that the following function $F$ is primitive recursive?

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

$$F(p,a,0)=g(\eta^{p}(a))$$
$$F(p,a,x+1)=h(\eta^{(p-(x+1))}(a),x,F(p,a,x))$$

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

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.
• 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 ? Sep 26, 2022 at 13:20
• 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. Sep 27, 2022 at 9:35