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


1 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?


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.