1

I am trying to understand the proof here:

How to prove that this function is primitive recursive?

In the answer below, $f,\pi,g$ are primitive recursive. $P,G,h$ are defined in the way below: $$ \begin{align} P(n,x,0)&=x\\ P(n,x,i+1)&=\pi(n-(i+1),P(n,x,i)) \\ G(n,x,0)&=f(P(n,x,n)) \\ G(n,x,i+1)&=g(i,P(n,x,n-(i+1)),G(n,x,i)) \\ h(n,x) &= G(n,x,n) \\ \end{align} $$

I need to prove that $h$ is indeed primitive recursive. Here is my definition of primitive recursive:enter image description here

And we can obtain recursive function by composition, as this picture mentions that it can be obtained by substitution: enter image description here

So to prove that $h$ is primitive recursive, it is sufficient to prove $G$ is primitive recursive. But $G$ seems not to be a total function, and thus seems cannot be primitive recursive. For instance, it is not defined at $n=0,i+1=1$.

I am confused. So may I please ask if $G$ and $P$ are primitive recursive? How can I see this? Thanks in advance!

Jean Marie
  • 81,803
Y.X.
  • 3,995
  • The question is: what is the definition of subtraction? It's not uncommon in this context to define subtraction such that it produces $0$ when it would "normally" be negative. This produces a total function $\mathbb{N}^2\to\mathbb{N}$. – Derek Elkins left SE May 20 '17 at 21:33
  • @DerekElkins So in this way that subtraction is defined, is it remains can be called as primitive recursive? – Y.X. May 20 '17 at 21:45
  • 1
    Sure. Subtraction, in the sense I gave, is trivially definable with primitive recursion. With subtraction being primitively recursive, $P$ is clearly of the form appropriate for primitive recursion, just define $h(i,z,y) = \pi(\pi_{2,1}(y)-(i+1),z)$ which is a composition of primitive recursive functions and $g(y) = \pi_{2,2}(y)$. So $P$ is primitive recursive, and $G$ is then also clearly of the appropriate form for primitive recursion. In fact, even if you don't take as given that $x\mapsto f(x,x)$ is primitive recursive if $f$ is, you can prove it with the axioms in your question. – Derek Elkins left SE May 20 '17 at 23:21

0 Answers0