Primitive recursive functions of bounded sum

569 Views Asked by At

I'm reading "Introduction to Mathematical Logic, Sixth Edition" (by Elliott Mendelson) and confused at Proposition 3.17 (page 179), which is about primitive recursion obtained from bounded sum. I understand the proposition, which states that if $f(x_1,...,x_n, y)$ is primitive recursive, then the bounded sum $g(x_1,...,x_n, z) = \sum_{y<z}f(x_1,...,x_n, y)$ is also primitive recursive. The proof is simple and straightforward.

Now my question is: what if in the summation the value of $f$ also depends on $z$? That is to say, is $g(x_1,...,x_n, z) = \sum_{y<z}f(x_1,...,x_n, y, z)$ also primitive recursive?

The author gave an example (page 179), $\tau(x) = \sum_{y \leq x} \overline{sg}(rm(y, x))$, and claims that it is primitive recursive. It seems that it can be proved directly from Proposition 3.17. But it does not appear so, as $\overline{sg}(rm(y, x))$ is a function $f(x, y)$ that also depends on $x$.

One way to resolve this issue seems to be: if in the summation $\sum_{y<z}f(x_1,...,x_n, y, z)$ the function $f$ is obtained by "recursion on $z$", i.e. $f(x_1,...,x_n, y, z)$ depends on $f(x_1,...,x_n, y, z-1)$ which also depends on $f(x_1,...,x_n, y, z-2)$ and so on, then we can find a function $h(x_1,..., x_n, y) = f(x_1,...,x_n, y, z)$. It means we can eliminate the dependency on $z$ and $h$ is also primitive recursive.

The above method only applies to certain cases. Is the general case true?

1

There are 1 best solutions below

1
On

Hint: the dependency of $f$ on $z$ and the dependency of the sum on $z$ are independent $\ddot{\smile}$. I.e., you can define

$$h(x_1,...,x_n, z_1, z_2) = \sum_{y<z_2}f(x_1,...,x_n, y, z_1)$$

and then define

$$g(x_1,...,x_n, z) = h (x_1,...,x_n, z, z)$$