How to show a function is primitive recursive by induction?

Question

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?

Answer 1

Wikipedia gives such an example. You haven't stated the definition of basic functions or basic operations, so I will assume the Wikipedia definition.

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