# Clarifications on primitive recursive function definition

I am studying primitive recursive functions and there's something that I don't quite understand: let's take the function that computes $x+y$, then, in order to show that $f(x,y)=x+y$ is primitive recursive, my lecture notes give the following equations:

\begin{cases} f(x,0)=x \\ f(x,y+1) = f(x,y)+1 \end{cases} this first bunch makes perfect sense to me, on the other hand, looking at the equations down below, I don't get why a new function $g$ is used and also why does it have three parameters, when the sum clearly has only two? Is that $y$ the variable that supposedly holds (partial) results from computation?

\begin{cases} f(x,0)=u^1_1(x) \\ f(x,y+1) = g(y, f(x,y),x) \end{cases}

where $g(x_1, x_2, x_3) = s(u^3_2(x_1, x_2, x_3))$.

• It's done to fit the schemes allowed by the definition of primitive recursion. – Raphael Jan 16 '13 at 10:07
• @Raphael first of all thank you for your comment to my question. Could you please explain a bit more? I still can't fully connect the dots. – haunted85 Jan 16 '13 at 10:14
• The second definition for $f$ you give is almost the definition of primitive recursive functions. You need to understand that the p.r.f.s are defined according to some scheme and that is all. If you can write a function, e.g., $a+b$, so that it fits in the scheme, you have proved that the function is primitive recursive. Edit: Ps, the top most definition of $+$ isn't written in this scheme, so it doesn't prove $+$ to be p.r. – Pål GD Jan 16 '13 at 11:07
• Moreover, $g$ takes three arguments, again because of the definition (the scheme). It is simply the way we write p.r. functions. – Pål GD Jan 16 '13 at 11:09
• "The scheme" is in essence a programming language, if a "strange" one. – Raphael Jan 16 '13 at 12:44

A function $f$ is said to be defined by primitive recursion if we can write its definition in the following form: $$f(x_1, \ldots, x_k, 0) = u(x_1, \ldots, x_k)\\ f(x_1, \ldots, x_k, n+1) = v(x_1, \ldots, x_k, n, f(x_1, \ldots, x_k, n)$$ where $u$ is a function of $k$ arguments and $v$ is a function of $k + 2$ arguments. Furthermore, $u$ and $v$ must be known to be primitive recursive alrady.
1. We cannot write $f(x,0) = x$ because "$x$" is not a primitive recursive function, whereas $u_1^1$ is. Again, it does not matter that $u_1^1(x)$ happens to be the same thing as $x$ because we are doing bureaucracy, and no shortcuts are allowed.
2. We cannot write $f(x, y+1) = f(x,y) + 1$ because the right-hand side is not in the correct form. For it to be in correct form we need to find a suitable $g$ so that $f(x, y+1) = g(x, y, f(x, y)$. Here $g$ must take $y$ as its second argument, even if it does not need it, otherwise we are not following the correct form. With this in mind it is easy to see that $g(a, b, c) = s(u^3_2(a,b,c))$ does the job.