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

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