# How to show a function is primitive recursive by induction?

I know, loosely speaking, if we can define a function $$f$$ in term of \begin{align} &f(0,\vec{x})=g(\vec{x})\\ &f(n+1,\vec{x})=h(f(n),n,\vec{x}) \end{align} where functions $$g,h$$ are primitive recursive. Then $$f$$ is primitive recursive.

However, what it means to show a function is primitive recursive by induction? I had read above explaination on page 93 on book $$\textit{Computability}$$ by Epstein and Carnielli, but still I'm not sure if I got the idea. Could someone provide some examples about how a inductive definition shows a function is primitive recursive?

• Your first question --how to show that a function is $PR$ by induction-- is not exactly what the quoted text is talking about. Let me explain the role of induction in the text and then maybe you can confirm if you still have a question. In the text they are defining a set, $PR$. They define $PR$ to be the union of sets $PR_0,PR_1,...,PR_n,...$ that are defined for all natural numbers $n$. The set $PR_0$ is defined as all basic functions. For each natural number $n$ the set $PR_{n+1}$ is defined as the functions that can be obtained from $PR_n$ by applying the basic operations one or ...
– plop
Sep 29, 2020 at 11:11
• ... zero times. The role of induction is to be able, from those two statements to make the claim that -- for all natural numbers $n$ we have defined a set $PR_n$ --. After that the definition of $PR$ ends by saying that $PR$ is the union of all $PR_n$ for all natural numbers $n$.
– plop
Sep 29, 2020 at 11:12
• Does the book contain no examples? Sep 29, 2020 at 11:15
• The thing is that the definition is being based on two propositions: [(1) The definition of $PR_0$ and (2) the definition of $PR_{n+1}$ in terms of $PR_n$, for each natural number $n$.] But to end the definition one needs the proposition that [(3) For all natural numbers $n$, the set $PR_n$ is defined.] A logical deduction is needed to get from ((1) and (2)) to (3). Induction is that logical deduction.
– plop
Sep 29, 2020 at 11:17

The successor function $$S(x) = x+1$$ is a basic function, and so is assigned 0. Projection functions such as $$P_1^1(x) = x$$, $$P_2^3(x,y,z) = y$$ and $$P_3^3(x,y,z) = z$$ are also assigned 0. The constant function $$z(x) = 0$$ is also assigned 0.
The function $$g(x,y,z) = S(P_2^3(x,y,z)) = y + 1$$ is a composition of two functions assigned 0, and so is assigned 1.
Using these functions, we can define a function $$h(x,y)$$ by primitive recursion: $$h(0,y) = P_1^1(y) = y$$, and $$h(S(x),y) = g(x,h(x,y),y) = h(x,y) + 1$$. This function is assigned 2, and you can check that $$g(x,y) = x + y$$.
The function $$r(x,y,z) = h(P_2^3(x,y,z),P_3^3(x,y,z)) = g(y,z) = y + z$$ is assigned 3.
We can define a function $$k(x,y)$$ by primitive recursion: $$k(0,y) = z(y) = 0$$, and $$k(S(x),y) = r(x,k(x,y),y) = k(x,y)+y$$. This function is assigned 4, and you can check that $$k(x,y) = x\cdot y$$.