# Restricted definition of primitive recursive function

I'm reading Peter Smith's introduction to Gödel's Theorems. He defines a primitive recursive (PR) function as:

• Zero, projection, successor functions
• Closed under composition
• Closed under primitive recursion, defined as

$$f(x_1, ..., x_n, Sy) = g(x_1, ..., x_n, y, f(x_1, ..., x_n, y))$$

I was wondering what the class of functions is if you restrict this to not use y:

$$f(x_1, ..., x_n, Sy) = g(x_1, ..., x_n, f(x_1, ..., x_n, y))$$

This seems like it should be more restrictive (I can't obviously get predecessor from this, but I can get multiplication), but I can't prove it.

What family of functions do you get from this?

• If you can implement a pairing function under these constraints, then you don't lose anything other than convenience. – Derek Elkins left SE Aug 9 '19 at 4:16
• Can't you define multiplication by $x \times 0 = 0$ and $x \times Sy = (x \times y) + x$? – Rob Arthan Aug 9 '19 at 15:36
• Oh, of course - somehow I'd convinced myself I needed +y, not +x. Thanks! – ECG Aug 9 '19 at 21:26
• What about predecessor? Is it possible to prove that predecessor is not definable in this framework? – Taroccoesbrocco Aug 10 '19 at 9:00
• @Taroccoesbrocco: predecessor is definable, but it's a bit tricky. See A Reduction of the Recursion Scheme by M. D. Gladstone JSL, Vol. 32, No. 4 (1967). Available on JSTOR here – Rob Arthan Aug 10 '19 at 11:33

Good question! This kind of recursion was considered by R. Robinson in Primitive Recursive Functions Bull. AMS, vol 53 (1947) pp. 925-942 (available here). Robinson called your restricted recursion scheme "pure recursion". The functions $$x+y$$, $$xy$$ and $$x^y$$ are all definable by pure recursion and hence so is the very handy function $$0^x$$, which is the characteristic function of the set $$\{0\}$$ (or $$\{ n \mid n > 0\}$$ depending on your conventions).

Robinson observed that if you can give pure recursive definitions of a pairing function $$\langle, \rangle : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$$ and projection functions $$\lambda, \rho : \mathbb{N} \to \mathbb{N}$$ such that:

\begin{align*} \lambda(\langle x, y\rangle) &=x \\ \rho(\langle x, y\rangle) &=y \end{align*}

then pure recursion is equivalent to unrestricted primitive recursion. (The notation here is mine, not Robinson's.) To see this (omitting the parameters $$x_1, \ldots, x_n$$), if we want to define $$f$$ such that:

\begin{align*} f(0)&= h \\ f(S(y)) &= g(y, f(y)) \end{align*}

we can define $$f'$$ by the pure recursion scheme:

\begin{align*} f'(0)&= \langle 0, h \rangle\\ f'(S(y)) &= \langle S(\lambda(f'(y))), g(\lambda(f'(y)), \rho(f'(y)))\rangle \end{align*}

and then put $$f(x) = \rho(f'(x))$$.

Robinson proposed the following definitions of the pairing and projection functions.

\begin{align*} \langle x, y \rangle &= (x + y)^2 + x\\ \lambda(x) &= x - \lfloor \sqrt{x} \rfloor^2 \\ \rho(x) &= \lfloor \sqrt{x} \rfloor - \lambda(x) \end{align*}

The definition of $$\langle,\rangle$$ can be obtained by composing addition and multiplication and so it is pure recursive. Robinson noted that $$\lfloor\sqrt{x}\rfloor$$ is definable by the pure recursion scheme:

\begin{align*} \lfloor \sqrt{0} \rfloor &= 0 \\ \lfloor \sqrt{S(y)} \rfloor &= \lfloor \sqrt{y} \rfloor + 0^{(S(\lfloor \sqrt{y} \rfloor))^2 - S(y)} \end{align*}

(the exponent $$(S(\lfloor \sqrt{y} \rfloor))^2 - S(y)$$ here is $$0$$ iff $$S(y)$$ is a perfect square, so we add $$1$$ in that case and $$0$$ otherwise). Subtraction $$x - y$$ (for $$x \ge y$$) can be defined by the following pure recursion scheme using the predecessor function $$P$$.

\begin{align*} x - 0 &= x\\ x - S(y) &= P(x - y) \end{align*}

Thus pure recursion is equivalent to unrestricted primitive recursion iff $$P$$ can be defined by pure recursion. This was subsequently proved by M. D. Gladstone in A Reduction of the Recursion Scheme JSL, Vol. 32, No. 4 (1967) pp. 505-508 (available here). The key to Gladstone's proof is a pure recursive definition of a function $$C(x, y)$$ such that $$C(x, y) = 0$$ iff $$x \le y$$. Using, this Gladstone defines a function $$f$$ by

\begin{align*} f(0, y) &= y \\ f(S(x), y)&= \left\{ \begin{array}{l} 0\mbox{, if C(y, f(x, y)) = 0}\\ f(x, y) +1 \mbox{, otherwise.} \end{array} \right. \end{align*}

and then $$P(x) = f(x, x)$$. (To see this prove by induction on $$x$$ that for $$1 \le x \le y$$, $$f(x, y) = P(x)$$.) I refer you to Gladstone's short and clear paper for the clever technique he uses to define $$C(x, y)$$.