# Is there a $\Delta^0_2$ real with "easy total computability problem"?

This was asked at MSE without success. Granted, a bounty is still ongoing there, but it doesn't look like it will be answered.

For (noncomputable) $$A\subseteq\omega$$ let $$\tilde{A}=\{e: \varphi_e^A\mbox{ is total and }\exists c(\varphi_e^A\simeq\varphi_c)\}$$. A priori $$\tilde{A}$$ is $$\Sigma^0_3(A)$$ ("$$\varphi_e^A$$ is total and there is some $$c$$ such that on all inputs we eventually see agreement between $$\varphi_c$$ and $$\varphi_e^A$$"). However, this bound isn't sharp in general: if $$A$$ is sufficiently Cohen generic then $$\tilde{A}$$ is $$\Pi^0_2(A)$$ (of course we can't do better than this: $$\tilde{A}$$ is always $$\Pi^0_2(A)$$-hard).

However, a fair amount of genericity (at a glance, $$2$$-genericity) is needed for that argument. This raises the question of how hard it must be to compute a real (nontrivially) satisfying "$$\tilde{A}$$ is not $$\Sigma^0_3(A)$$-complete." Specifically:

Does every noncomputable $$\Delta^0_2$$ set $$A$$ satisfy "$$\tilde{A}$$ is $$\Sigma^0_3$$-complete"?

Genericity-based arguments almost certainly won't be useful here, since there aren't even any $$\Delta^0_2$$ weak $$2$$-generics.

• @EmilJeřábek Wow, that wasn't my finest moment. Fixed, thanks! Jun 30 '21 at 18:27
• Don’t you want to fix the actual question? As written, the answer is trivially no. Perhaps it should only apply to non-recursive $\Delta^0_2$ sets? Jun 30 '21 at 20:06
• @EmilJeřábek Argh, I thought I had - fixed. Jun 30 '21 at 20:10

## 1 Answer

It seems to me that if $$G$$ is 1-generic and recursive in $$0'$$ then $$\tilde{G}$$ is Boolean $$\Sigma^0_2$$, which is sufficient to conclude that $$\tilde{G}$$ is not $$\Sigma^0_3(G)$$-complete.

First, show that if (1) there is a condition $$p$$ in $$G$$ such that there is no $$\varphi_e$$-splitting pair of conditions extending $$p$$ and (2) for every condition $$q$$ in $$G$$ and every $$m$$, there is an extension $$r$$ of $$q$$ which makes $$\varphi_e(m)$$ converge, then $$e$$ is in $$\tilde{G}$$. We can exhibit a $$\varphi_c$$ for $$\varphi_e(G)$$ by observing that the value of $$\varphi_e(G)$$ at $$m$$ can be recursively determined by searching for any extension of $$p$$ that gives a value at $$m$$. Second, show that if $$e$$ is in $$\tilde{G}$$ then (1) and (2) must hold. Obtaining (1) uses the 1-genericity of $$G$$ and obtaining (2) uses the totality of $$\varphi_e(G)$$.

Since $$G$$ is $$\Delta^0_2$$, Condition (1) is $$\Sigma^0_2$$ and (2) is $$\Pi^0_2$$, and so $$\tilde{G}$$ is Boolean $$\Sigma^0_2$$.

• Interesting, thanks! I'm now curious about the possible complexities of $\tilde{A}$ for $A\in\Delta^0_2$, but I'll think about that more before asking another question. Jun 30 '21 at 20:50