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?

  • 3
    $\begingroup$ If you can implement a pairing function under these constraints, then you don't lose anything other than convenience. $\endgroup$ – Derek Elkins left SE Aug 9 '19 at 4:16
  • 1
    $\begingroup$ Can't you define multiplication by $x \times 0 = 0$ and $x \times Sy = (x \times y) + x$? $\endgroup$ – Rob Arthan Aug 9 '19 at 15:36
  • $\begingroup$ Oh, of course - somehow I'd convinced myself I needed +y, not +x. Thanks! $\endgroup$ – ECG Aug 9 '19 at 21:26
  • $\begingroup$ What about predecessor? Is it possible to prove that predecessor is not definable in this framework? $\endgroup$ – Taroccoesbrocco Aug 10 '19 at 9:00
  • 2
    $\begingroup$ @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 $\endgroup$ – 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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.