Clarifications on primitive recursive function definition

Question

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

• Raphael: It's done to fit the schemes allowed by the definition of primitive recursion.
• haunted85: @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.
• Ainsley H.: 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.
• Ainsley H.: Moreover, $g$ takes three arguments, again because of the definition (the scheme). It is simply the way we write p.r. functions.
• Raphael: "The scheme" is in essence a programming language, if a "strange" one.

Answer 1

The first equation is what you would normally write down as a mathematician if you were to define addition in terms of successor. The second equation is the same thing, except it is written in a precise manner so as to make it obvious that this indeed is a definition by primitive recursion. You have to pay close attention to details.

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.

The first equation in your question is not of this form but the second one is. Concretely:

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.

When you try to show that something satisfies a definition (in this case "is primitive recursive") you have to get it exactly in the correct form. Only later, when you already understand what is going on, can you start to make shortucts and wave your hands, and say "it's obvious". Your professor does not think you are at that stage (and you are not, since you asked this question).