1
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ 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 ... $\endgroup$ – plop Sep 29 '20 at 11:11
  • $\begingroup$ ... 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$. $\endgroup$ – plop Sep 29 '20 at 11:12
  • $\begingroup$ Does the book contain no examples? $\endgroup$ – Yuval Filmus Sep 29 '20 at 11:15
  • $\begingroup$ 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. $\endgroup$ – plop Sep 29 '20 at 11:17
1
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.