3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ @EmilJeřábek Wow, that wasn't my finest moment. Fixed, thanks! $\endgroup$ Jun 30 '21 at 18:27
  • $\begingroup$ 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? $\endgroup$ Jun 30 '21 at 20:06
  • $\begingroup$ @EmilJeřábek Argh, I thought I had - fixed. $\endgroup$ Jun 30 '21 at 20:10
5
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Jun 30 '21 at 20:50

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.