Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am having trouble understanding the definition of primitive recursion. I would like to have clarification of the definition with simple applications of the definition with examples.

The definition of Primitive Recursion is: $h(x,0)=f(x)$, $h(x,s(y))=g(x,y,h(x,y))$.

The short hand is $h=\Pr[f,g]$.

What exactly does: $h(x,s(y))=g(x,y,h(x,y))$ mean?

The example the book gives is Pr for addition: $s(x,0)=x$, $\text{sum}(x,s(y))=s(\text{sum}(x,y))$. Where s means "successor". I do not understand the example, nor how the example correlates to the definition.

Specifically how does $h(x,s(y))=g(x,y,h(x,y))$ correlate to $\text{sum}(x,s(y))=s(\text{sum}(x,y))$ and what is $\text{sum}(x,s(y))=s(\text{sum}(x,y))$ doing? I'd like to see an example so I can see how the definition works.

share|cite|improve this question
up vote 4 down vote accepted

The basic idea of primitive recursion is that the value of $h ( x, y+1 )$ can depend on the history of this function (i.e., the values $h(x,0), h(x,1), \ldots , h(x,y)$). (This is not how it is stated, but it turns out to be an equivalent formulation in the class of recursive functions). If you recall the Fibonacci numbers $F(0) = 0, F(1) = 1, F(n+2) = F(n) + F(n+1)$ you get the basic idea of this history, and how the value of a function at an argument can depend on its value at smaller arguments.

In terms of the "sum" function, note that we have an initial condition, $$\mathrm{sum} (x,0) = x.$$ As you have noticed, this is not quite formally correct. Instead, we should have a unary function $id$ such that $id(x) = x$ for all $x$, and then $$\mathrm{sum} (x,0) = id(x) = x.$$

Next we have the recursive element, $$\mathrm{sum} ( x, y+1 ) = S ( \mathrm{sum} (x,y) ).$$ Again, this is not quite formally correct. Instead we should have a ternary function $S_3$ where $S_3(x,y,z) = S(z)$, and then set $$\mathrm{sum} ( x , y+1 ) = S_3 ( x, y, \mathrm{sum} (x,y) ).$$ Of course, by our definition of $S_3$ this reduces down to the original formula.

In this manner, $\mathrm{sum}$ is defined via primitive recursion on the functions $id$ and $S_3$. (But this becomes a little bit unreadable, and you will usually see it written out in the manner described in your question.)

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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