Is $0^{(\omega)}$ a minimal cover in the arithmetic degrees

Question

Is it known if $0^{(\omega)}$ a minimal cover in the arithmetic degrees? In the Turing degrees to show that $0'$ (indeed $0^{(n)}$) isn't a minimal cover one uses the density of r.e. degrees. However, given that it's not known if downward density holds for the REA sets (even in the arithmetic degrees) is it known if $0^{(\omega)}$ a minimal cover in the arithmetic degrees?

EDIT: To be clear, I'm asking whether it's the case that there is an arithmetic degree $X$ such that $X <_a 0^{\omega}$ but that there is no $Y$ with $X <_a Y <_a 0^{\omega}$ where $<_a$ is the relation "is arithmetic in"

Answer 1

I claim that $0^{(\omega)}$ is not minimal upper bound of $0^{(n)}$ in the Turing degrees. I shall construct a set $A\subseteq\newcommand\N{\mathbb{N}}\N\times\N$ with the following properties:

• the $n$th section $A_n$ differs only finitely from $0^{(n)}$
• $A$ is computable from $0^{(\omega)}$
• and yet, $0^{(\omega)}$ is not computable from $A$.

We define $A$ in stages. At stage $n$, the $n$th approximation $A_n$ is defined fully on the first $n$ slices $0,1,...,n-1$, plus perhaps a finite extension of those slices. At this stage, we ask whether there is a finite extension of $A_n$ to $A_n^+$ and number $m$ such that $\varphi_n^{A_n^+}(m)\downarrow\neq 0^{(\omega)}(m)$. This is a question to which $0^{(\omega)}$ knows the answer. If we can do that, we go ahead and extend to $A_n^+$, and then fill up the rest of the $n$th column to agree with $0^{(n)}$.

By construction, we have fulfilled the first two properties about $A$. To see that $0^{(\omega)}$ is not computable from $A$, if it were, then it would be computed by some program $n$. But at stage $n$, we made sure that there was a disagreement, if this was possible with a finite extension of $A_n$, and if it wasn't, then it would follow that $\varphi_n^{A}(m)$ could not agree with $0^{(\omega)}(m)$ for every $m$, since it would be the same as $\varphi_n^{A_n}(m)$, but $A_n\leq_T 0^{(n)}$, so it cannot compute $0^{(\omega)}$.

I believe that this kind of thing is a standard construction in computability theory, and there may be a very general assertion to be made, connected with the exact pair phenomenon.

Answer 2

This is really a comment, but it's too long:

Building off of a question in a comment thread above, let me give a more detailed argument for why we can't expect countable Turing ideals to have $2$-lubs (or $n$-lubs, or etc.) in general. I'll focus on the $2$-lub case, and explain at the end how this generalizes.

Let $Col(\omega,\mathbb{R})$ be the usual forcing making the reals countable. Let $G,H$ be mutually $Col(\omega,\mathbb{R})$-generic, and let $J=\mathbb{R}^V$. In $V[G,H]$, we have that $J$ is a countable Turing ideal; I claim that $V[G,H]\models$ "$J$ has no $2$-lub."

The point is absoluteness, specifically of Turing computations and double jumps, between transitive models of set theory. Working in $V[G,H]$, suppose $r$ were a $2$-lub of $J$. Then - letting $g,h$ be the usual reals enumerating $J$ via $G,H$ respectively - we would have $$V[G,H]\models \Phi_d^{g''}=\Phi_e^{h''}=r$$ for some $d,e$. By arithmetical absoluteness, we have $$(\Phi_d^{g''})^{V[G,H]}=(\Phi_d^{g''})^{V[G]}$$ and so $r\in V[G]$; similarly, we get $r\in V[H]$. But then $r\in V$ since $G$ and $H$ were mutually generic, and this is a clear contradiction.

So in $V[G,H]$ there is a countable Turing ideal with no $2$-lub, or to put it a bit more conveniently we have

$V[G,H]\models$ "There is a countable Turing ideal $I$ and a pair of upper bounds $r,s$ of $I$ such that no upper bound for $I$ is computable in both $r''$ and $s''$."

This is $\Sigma^1_1$ (the apparent universal quantifier over reals implicit in "no upper bound" is actually arithmetical), and so absolute between $V[G,H]$ and $V$ by Mostowski absoluteness. And if we want to avoid absoluteness/forcing over $V$, we can simply run the above argument with a bit more care replacing $V$ with some fixed countable elementary submodel of $H_{\omega_{17}}$ (say). That is, we have:

If $M$ is a countable elementary submodel of $H_{\omega_{17}}$, then $\mathbb{R}^M$ is a countable Turing ideal with no $2$-lub.

The crucial point here is that computability from a double jump is "too canonical:" the recipe for finding the purported $2$-lub $r$ given any other upper bound $b$ won't take us outside the model $V[b]$, and that's a problem. More generally, there are countable Turing ideals with no $17$-lub, no $\omega^2$-hyperjump-lub, etc. In fact at a glance I believe the following should hold:

Suppose $F:[\mathbb{R}]^\omega\rightarrow\mathbb{R}$ is a function such that for every countable Turing ideal $I$, we have $F(I)\ge_Tx$ for all $x\in I$. Then $F$ is non-Borel. On the other hand, if $\mathsf{V=L}$ then there is a $\Delta^1_2$ such $F$ (namely, "Pick the $L$-least upper bound").

Answer 3

This isn't quite an answer but it's almost a reduction to a famous unsolved problem. Consider the question of whether there is an $\omega$-REA set of minimal arithmetic degree. If this question has a relativizing solution (e.g. either there is an $\omega$-REA operator A(X) which produces a minimal cover for X in the arithmetic degrees or for all such A, X A(X) is not a minimal arithmetic cover) then it's answer decides this question.

If there is such a minimal cover operator then, by the inversion theorem for $\omega$-REA operators there is an operator J s.t. A(J(0)) is Turing equivalent to $0^{\omega}$ and J(0) non-arithmetic so $0^{\omega}$ is a minimal cover. OTOH the operator A(X) that always returns $X \oplus 0^{\omega}$ would necessarily yield a minimal cover for some $X$ if $0^{\omega}$ was a minimal cover.