Is there a partial recursive function mapping $e$ to the least element of $W_e$?

Question

Is there a partial recursive function $f$ that maps $e$ to the least element of $W_e$ if $W_e\neq \varnothing$?

Can we apply the $\mu$-operator (minimization) to a partially decidable predicate to get a partial recursive function (as in defining $f(x)=\mu z(z\in W_e)$ if $W_e\neq\varnothing$ and undefined otherwise, since $z\in W_e$ is partially decidable)?

My guess was that there is no such $f$, but I wasn't sure how to show that. Thanks in adavnce.

Answer 1

Your intuition is right: there is no such function.

We can see this in a couple different ways:

• Contradiction: Suppose there were such an $f$. Then - given an arbitrary (infinite) c.e. set $A$ - we could compute the sequence $$\min(A), \min(A\setminus\{\min(A)\}), \min(A\setminus\{\min(A), \min(A\setminus\{\min(A)\})\}), ...$$ by iteratively applying $f$. But this precisely enumerates $A$ in order, and so makes $A$ computable. Since there are non-computable sets, this can't happen.

• Direct diagonalization: Given a computable function $f$, we can find an $e$ such that $(i)$ $2$ enters $W_e$ at stage $0$, $(ii)$ $1$ enters $W_e$ at stage $n+1$ iff $f(e)$ halts and outputs "$2$" at stage exactly $n$, and $(iii)$ no other numbers enter $W_e$ under any other circumstances. Then we get $\min(W_e)=2$ iff $f(e)\not=2$, so $f$ doesn't do what we want it to.

  • This fits into the "game picture" of c.e. sets: I pick a computable $f$, and you start building my $W_e$. You put $2$ into it, which forces me to eventually decide what $f(e)$ is; as soon as I do, if I say "$2$" then you put $1$ into my set, and if I say anything other than "$2$" you do nothing. Either way, you've defeated my purported $f$.

I haven't provided full details of either case, but the idea should be clear. Filling in the details (of the first one, especially) is a good exercise.