Smallest base to reach partial recursive functions as a closure of unbound search

Question

It is customary to define the class of partial recursive functions by taking the set of primitive recursive functions $PR$ and taking closure over unbound search operation.

Do we need the "whole" set of primitive recursive functions as a base to reach the class of partial recursive functions with the closure? It seems reasonable to assume that unbound search could be used in the place of primitive recursion to reach the class $PR$ from a smaller base class.

For example Grzegorczyk proves that

Every computable function can be presented in the form $f(u)=A(ix[B(u,x)=0])$, where $A$ and $B$ are functions of the class $\mathcal{E}_0$.

Here $ix[B(u,x)=0]$ is the unique $x$ such that $B(u,x)=0$ and $\mathcal{E}_0$ is the lowest set in Grzegorczyk-hierarchy. I don't, however, see how to change the "unique $x$ such.." to "smallest $x$ such..".

Answer 1

$\def\dotm{\mathbin{\scriptstyle\dot{\smash{\textstyle-}}}}$It follows from the MRDP theorem that every partial recursive function $f(\vec x)$ can be written as $$f(\vec x)\simeq l\bigl(\mu z\,[p(\vec x,l(z),l(r(z)),\dots,l(r^{k-1}(z)),r^k(z))=0]\bigr),$$ where $p(\vec x,y_0,\dots,y_k)$ is a polynomial with integer coefficients, and $l(z)$ and $r(z)$ are the left and right inverse of a pairing function. If we take the Cantor pairing function $$[x,y]=\frac{(x+y)(x+y+1)}2+x,$$ we can express $l(z)=z-[0,g(z)]$, $r(z)=g(z)-l(z)$, where $g(z)=\mu u\,[2z\dotm(u+1)(u+2)=0]$. Thus, partial recursive functions are the closure of projections, successor, multiplication, and limited subtraction under minimization and composition. (Note that $x+y=S(x)S(y)\dotm ((S(x)S(y)\dotm x)\dotm y)$.)

Answer 2

No. We don't need every primitive recursive function.

In fact every recursive function is the composition of two primitive recursive functions definable by $\Delta_0$ formulas, and using the minimization operator. Since not every primitive recursive function is $\Delta_0$ this shows that you don't really need all the primitive recursive functions after all.

This is because we can write the graph of every recursive function as a $\Sigma_1$ set, i.e. $f(\vec x)=y\iff\exists z\varphi(\vec x,y,z)$, where $\varphi$ is a $\Delta_0$ formula. We can define from $\varphi$ two functions $G$ and $H$ as follows:

• $G(\vec x,w)=\min_{y < w}\exists z < w\varphi(\vec x,y,z)$ - this function returns the least $y$ such that $\varphi(\vec x,y,z)$ holds, if such $z$ exists.
• $H(\vec x,w)=\exists y < w\exists z < w\varphi(\vec x,y,z)$ - this function returns $0$ if there is such $y$ and $z$ below $w$, and $1$ otherwise.

It is not difficult to see that indeed both $G$ and $H$ are primitive recursive, and defined by $\Delta_0$ formulas.

Now $f(\vec x)=G(\vec x,\mu w H(\vec x,w))$, and one can verify that even if $f$ is a partial function the result is the same (i.e. it does not extend $f$).