Does the definite description operator generate all general recursive functions?

Question

Suppose, instead of adding the $\mu$ operator to the primitive recursive functions, we add the definite description operator. For a given relation $R$, the definite description operator returns the unique natural number that satisfies $R(y)$. Let us say that it returns $0$, when there is zero or more than one object satisfying the predicate. Do we still get all general recursive functions?

Answer 1

In order to see that we still get all the (partial) recursive functions it is enough to show that we can write the minimization operator $\mu$ using the definite description operator, call it $\delta$ for simplicity. I am assuming $\delta(R)=x+1$ if $R(x)$ holds, and $0$ otherwise (not exactly what is written in the OP, but I guess this is what is meant).

Just so that we agree on the notation, we write $\mu(f)(\vec{y})=x$ if $x$ is the least s.t. $f(x,\vec{y})=0$.

For every $\vec{y}$ we can define the set $$ R_{\vec{y}}:= \{ x : f(x,\vec{y})= 0 \text{ and } (\forall i<x)(f(i,\vec{y})\neq 0)\}$$ Clearly $|R_{\vec{y}}|\le 1$. Using $\delta$ we can define

$$ h(\vec{y}) = \begin{cases} \delta(R_{\vec{y}})-1 & \text{if }\delta(R_{\vec{y}}) >0 \\ \uparrow & \text{otherwise} \end{cases} $$

We now prove that $h=\mu(f)$. Notice that if $R_{\vec{y}}\neq\emptyset$ then $\delta(R_{\vec{y}})>0$ and therefore $h(\vec{y})=\delta(R_{\vec{y}})-1 = x = \mu(f)(\vec{y})$. On the other hand, if $R_{\vec{y}}=\emptyset$ it means that there is no least $x$ that satisfies $f(x,\vec{y})=0$. In this case we have that both $\mu(f)(\vec{y})$ and $h(\vec{y})$ are undefined.

So yes, you can get every (partial) recursive function using $\delta$.

Let me also point out that, since $\delta$ also gives information in case there is no $x$ that satisfies $R(x)$, we actually have more. For example, let $h(n,x)$ be s.t. $h(n,x)=0$ if $\{x\}(x)$ halts in $n$ steps, and $1$ otherwise. Let also $R_x := \{ x_s \}$ where $x_s$ is the least integer $n$ s.t. $\{x\}(x)$ halts in $n$ steps. For each $x$ we have $$ x\in \emptyset' \iff \mu(h)(x)\downarrow \iff \delta(R_x)>0 $$ But now, by hypothesis, the map $x\mapsto \delta(R_x)$ is total and computable, and since this encodes the characteristic function of $\emptyset'$ we have that the halting problem is computable.

If you relax the requirement that $\delta$ gives information also in case the relation $R$ is empty then you should get exactly the same family of computable functions.