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

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

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?