Primitive Recursive Proof in Davis, Sigal & Weyuker Textbook

[gnome]

In the Davis, Sigal & Weyuker textbook "Computability, Complexity and Languages" their proof that $f(x) = x + y$ goes like this:
$$\begin{equation*}\begin{split}f(x,0) &= u_1^1(x)\\f(x,y+1) &= g(y,f(x,y),x)\end{split}\end{equation*}$$
where $g(x_1,x_2,x_3) = s(u_2^3(x_1,x_2,x_3))$.

And (I'm paraphrasing now in the interest of brevity) these functions u, s and g are all primitive recursive so therefore f is too.

I'm wondering, would it be equally valid (and simpler) to say
$$\begin{equation*}\begin{split}f(x,0) &= u_1^1(x)\\f(x,y+1) &= s(f(x,y))\end{split}\end{equation*}$$
followed by the same explanation?

Apparently, the reason for the form of their proof is that they defined recursion to be one of these two "things":

Either:
$$\begin{equation*}\begin{split}h(0) &= k\\h(t+1) &= g(t,h(t))\end{split}\end{equation*}$$
or:
$$\begin{equation*}\begin{split}h(x_1,...,x_n,0) &= f(x_1,...,x_n),\\h(x_1,...,x_n,t+1) &= g(t,h(x_1,...,x_n,t),x_1,...,x_n)\end{split}\end{equation*}$$

and they had to put their proof into the same form as their definition of recursion.

So I guess my question boils down to, is that just their definition of recursion, or is it everybody's?

i.e. does every proof involving recursion have to be in exactly that format?

 

[CrankFan]

That is the standard definition of primitive recursion.

Both of the examples are primitive recursive. The foot note on page 40 indicates that they will agree to call "primitive recursion", "recursion" simply as a convenience, until later.

 

[tacman]

The proof presented in the Davis, Sigal & Weyuker textbook is a valid proof using the primitive recursive definition of recursion. The authors have chosen to present the proof in this specific format because it aligns with their definition of recursion. However, it is not necessary for every proof involving recursion to be in this exact format. There are other equivalent ways to define recursion, and as long as the proof follows the principles of recursion and is logically sound, it can be presented in a different format.

In fact, the alternative proof you have proposed is also a valid proof using the primitive recursive definition of recursion. It is simpler and more concise, but it still follows the same principles and logic as the original proof.

In conclusion, the specific format used in the Davis, Sigal & Weyuker textbook is their chosen definition of recursion, but it is not the only way to define recursion or present a proof involving recursion. As long as the proof follows the principles of recursion, it can be presented in different formats.