6

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"

Peter Gerdes
  • 2,613

3 Answers3

5

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.

Joel David Hamkins
  • 224,022
  • 2
    Vote up this comment if I should delete this answer, which is based on a misunderstanding of the question. – Joel David Hamkins Mar 23 '23 at 19:18
  • This argument would generalize to show there is no least upper bound to any strictly increasing sequence of Turing degrees, right? – James Mar 23 '23 at 21:35
  • I had used the jump, though, to know if there was a finite extension at stage n. Perhaps one can omit that with a priority argument instead to achieve that stronger result. – Joel David Hamkins Mar 23 '23 at 22:42
  • 1
    The usual way to do this argument is with recursively pointed trees. It's just the standard argument to construct an upper bound interleaved with stages to avoid computing $0^{\omega}$ I believe you can even get that your jump doesn't compute $0^{\omega}$. What's true is that $0^{\omega}$ is a 2-least upper bound (it's computed by the double jump of any other least upper bound). But yah, not quite I was asking. Sorry for the confusion. – Peter Gerdes Mar 24 '23 at 00:03
  • 1
    @James Yes, this is a classic resut of Spector; see the discussion at this old MO post. – Noah Schweber Mar 24 '23 at 00:20
  • @NoahSchweber Do you know/remember if you can always get a 2-lub (eg a least upper bound computed by the double jump of any other upper bound) or is that only true when you are taking the upper bound of a sequence of hops? – Peter Gerdes Mar 24 '23 at 04:44
  • 1
    @PeterGerdes You definitely can't get a 2-lub in all cases. For an overkill proof of this, let $G,H$ be mutually $Col(\omega,\mathbb{R})$-generic. Then (shifting from sequences to ideals for simplicity) in $V[G\times H]$, the Turing ideal $\mathbb{R}^V$ is countable but has no 2-lub. The latter is because $V[G]\cap V[H]=V$ (if $\mathbb{R}^V$ had a 2-lub in $V[G\times H]$ then $V[G]$ and $V[H]$ would share some Turing upper bound of $\mathbb{R}^V$). Now by Shoenfield absoluteness, the statement "There is a countable Turing ideal with no 2-lub" is true in $V$ already. :P – Noah Schweber Mar 24 '23 at 05:07
  • 1
    I conjecture that any "sufficiently fast-growing" sequence of Turing degrees will have this property. To make this precise, consider the "Turing-Hechler" forcing whose conditions are pairs $(p,F)$ for $p$ a finite increasing sequence of Turing degrees and $F\succ p$ an infinite sequence of Turing degrees, with conditions ordered by $$(p,F)\le (q,H)\quad\iff\quad p\succcurlyeq q\mbox{ and } \forall i(F(i)\ge_TH(i)).$$ I suspect that there is a countable family of dense sets $\mathscr{D}$ for this forcing such that no $\mathscr{D}$-generic sequence of degrees has an $n$-lub for any $n\in\omega$. – Noah Schweber Mar 24 '23 at 16:54
  • Sorry, I mangled the definition of 2-lub a bit. It's the least element (if it exists) of $x^2$ s.t. x is a minimal upper bound ($0^{\omega}$ isn't itself a minimal upper bound). This shouldn't make a difference to your argument since what I said defines $x$ where $x^2$ is the 2-lub (I presume you understood I meant x is minimal upper bound not lub since that's what were were just saying doesn't exist for strictly increasing sequence of degrees). I'll have to think for a bit about your arg but what is $Col(\omega, \mathbb{R})$? – Peter Gerdes Mar 26 '23 at 02:52
  • @NoahSchweber I guess I'm a bit confused as to how your forcing argument makes use of the double jump. I mean, using recursively pointed trees you can prove that there is a minimal upper bound of any countable collection $C$ of degrees (or $C$ contains a greatest element). So how are we showing we can't have a minimal upper bound that isn't computed by the double jump of any other? Or are you just showing the non-existence of a lub and it's my bad for saying lub rather than minimal upper bound? – Peter Gerdes Mar 26 '23 at 03:05
  • 1
    @PeterGerdes $Col(\omega,\mathbb{R})$ is the forcing making the (old) reals countable - conditions are finite sets of real numbers, ordered by reverse extension. The point of my argument is that if $x,y$ are upper bounds - minimal or otherwise - of $\mathbb{R}^V$ with $x\in V[G],y\in V[H]$, then no upper bound $r$ of $\mathbb{R}^V$ (minimal or otherwise) is computable from $x^{(n)}$ and from $y^{(n)}$ for any $n$ (we can push this much further). This is because such an $r$ would be in $V[G]\cap V[H]$, hence in $V$ already, but $\mathbb{R}^V$ isn't countable in $V$. – Noah Schweber Mar 26 '23 at 03:08
  • @NoahSchweber Ahh thanks, I was confused b/c Jech always uses $Col(\omega, \kappa)$. So to lay out your argument you are saying let $b_H$ be an upper bound of $\mathbb{R}^{V}$ in $V[H]$ and similarly for $b_G$. If $b$ was a minimal upper bound of $\mathbb{R}^{V}$ in $V[H \times G]$ and $b \leq_T b_H^{2}, b_G^{2}$ (both bound minimal upper bounds) then $b \in V[H] \cap V[G] = V$ but since $b \geq_T X$ is absolute this gives $b$ computes every real. Ok, neat! – Peter Gerdes Mar 26 '23 at 03:28
  • Wait, no that doesn't seem quite right. Why can't this $b$ exist in $V[H \times G]$ but not in $V[H]$ and $V[G]$? I mean there will be sets in $V[H \times G]$ that aren't in either $V[H]$ or $V[G]$. The worry here is that there might be a 2-lub in each of $V[H \times G]$, $V[H]$ and $V[G]$ but that they aren't the same. I mean just consider $\oplus \mathbb{R}^{V}$ this has to exist in all 3 forcing extensions but can't be the same in them by the argument you just gave. – Peter Gerdes Mar 26 '23 at 04:16
  • @PeterGerdes See my answer. The point is that a 2-lub would be too easily decodable from any other ub. – Noah Schweber Mar 30 '23 at 17:59
3

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").

Noah Schweber
  • 18,932
1

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.

Peter Gerdes
  • 2,613