Is this set $\Sigma^0_3$-complete in the parameter $A$?

Question

Pick a non-computable set of natural numbers $A$. Is the set $\tilde A=\{n:\varphi_n^A \text{ is total computable}\}$ a $\Sigma^{0,A}_3$-complete set? If yes, how can we prove that? The insight is that we have no smarter strategy for checking whether $n$ is in $\tilde A$ or not than looking for an $e$ such that $\varphi_e$ coincides with $\varphi_n^A$. The difficulty lies in the fact that the proof must not work for computable $A$, as in that case $\tilde A$ is just the $\Pi^0_2$-complete set $\text{Tot}$.

Answer 1

Surprisingly, if $G$ is sufficiently (Cohen) generic then $\tilde{G}$ is $\Pi^0_2(G)$. This means that not only is the upper bound not sharp in general, but it in fact fails to be sharp for a comeager set of oracles!

This assumes familiarity with computability-theoretic forcing and genericity. If you haven't seen this before, the point is that there is a comeager set $\mathcal{C}$ of oracles - the "sufficiently generic" ones - such that for every $G\in\mathcal{C}$ and every arithmetical property $p$, there is some finite string $\sigma$ such that every element of $\mathcal{C}$ extending $\sigma$ has property $p$. In that case we say that $\sigma$ forces that $p$ holds. I make various claims about forcing below; if you're willing to take them for granted, the argument should make sense.

Actually, more limited genericity notions are more common in computability theory - see especially the notions of "$n$-genericity" and "weak $n$-genericity" for each $n$. At a glance, what we need here is $2$-genericity.

---

Fix $G$ sufficiently generic and $e\in\omega$; we want to determine whether $e\in\tilde{G}$ in a $\Pi^0_2(G)$ way. We start by defining three types of binary string which "strongly determine" the behavior of $\varphi_e^G$.

• $\sigma\in 2^{<\omega}$ is type 0 iff there is some $c<\vert\sigma\vert$ such that for all $n$ and all extensions $\tau\succ\sigma$ there is an extension $\eta\succ\tau$ such that $\varphi_e^\eta(n)$ and $\varphi_c(n)[\vert\eta\vert]$ are each defined and are equal. This property is $\Pi^0_2$.

• $\sigma\in 2^{<\omega}$ is type 1 iff there is some $n<\vert\sigma\vert$ such that no extension $\tau\succ\sigma$ has $\varphi_e^\tau(n)\downarrow$. This property is $\Pi^0_1$.

• $\sigma\in 2^{<\omega}$ is type 2 iff for every $m$ and every extension $\tau\succ\sigma$ there is an $n>m$ and a further pair of extensions $\eta_1,\eta_2\succ\tau$ such that $\varphi_e^{\eta_1}(n)$ and $\varphi_e^{\eta_2}(n)$ are each defined and are not equal. This property is $\Pi^0_2$.

Note the "bounding by length" in the definitions of type 0 and 1; in particular, this keeps type-0-ness $\Pi^0_2$ instead of $\Sigma^0_3$.

Now since $G$ is sufficiently generic, every true fact about $G$ that we care about is forced by some initial segment. We reason as follows:

• If $e\in\tilde{G}$, let $c$ be such that $\varphi_c$ is total and equal to $\varphi^G_e$ and let $\sigma\prec G$ force that. Then the initial segment of $G$ of length $\max\{\vert\sigma\vert, c+1\}$ will be a type 0 string.

• If $\varphi_e^G$ is not total, let $n$ be such that $\varphi_e^G(n)\uparrow$ and let $\sigma\prec G$ force that. Then the initial segment of $G$ of length $\max\{\vert\sigma\vert, n+1\}$ is a type 1 string.

• If $e\not\in\tilde{G}$ but $\varphi_e^G$ is total, let $\sigma\prec G$ force that. Then $\sigma$ is type 2.

So to tell whether $e\in\tilde{G}$ we just search through initial segments of $G$ until we find one which is either type 0, type 1, or type 2; if we find a type 0 initial segment we know $e\in\tilde{G}$ and if we find a type 1 or type 2 initial segment we know $e\not\in\tilde{G}$.

---

There are two natural follow-up questions at this point.

• How hard-to-compute must a real $A$ satisfying "$\tilde{A}$ is not $\Sigma^0_3(A)$-complete" be? This is of course vague, but one interesting way to make it precise is to ask for the least $n$ such that ${\bf 0}^{(n)}$ computes such a degree (equivalently, such that some real with this property is $\Delta^0_{n=1}$). Increasingly generic reals are increasingly hard to compute in this sense - e.g. ${\bf 0'}$ doesn't compute any $2$-generic reals. So the answer above does provide an upper bound, but it's probably not a great one. In particular, as far as I know it's plausible that no ${\bf 0'}$-computable real $A$ has this property. I've asked this here.

• Genericity isn't the only "mostness" game in town: there's also randomness. While genericity is connected with category (meager/comeager), randomness is connected with measure (null/full measure). Randomness can be viewed as a kind of "generalized genericity" (forcing construed more broadly), and we can show that measure-$1$ many reals "agree on their $\tilde{\cdot}$-behavior." So, which way does it go? Do all sufficiently random reals satisfy "$\tilde{A}$ is $\Sigma^0_3(A)$-complete" or not?