6
$\begingroup$

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"

$\endgroup$
5
  • 1
    $\begingroup$ I wonder whether one can make a smaller upper bound by taking sum of suitably generically modified copies of $0^{(n)}$? That is, put them together and make a finite change to each one, so as to prevent the whole thing from computing $0^{(\omega)}$. $\endgroup$ Commented Mar 23, 2023 at 10:14
  • 1
    $\begingroup$ I posted a solution based on that idea. $\endgroup$ Commented Mar 23, 2023 at 15:24
  • 1
    $\begingroup$ Oh, I realized I may have misunderstood your question. Are you asking whether $0^{(\omega)}$ is a minimal cover of some degree $B$? Obviously $B$ cannot be arithmetic (so not in the arithmetic degrees--perhaps you should have meant hyperarithmetic?). $\endgroup$ Commented Mar 23, 2023 at 15:42
  • 2
    $\begingroup$ @Joel: I think Peter means in the degree structure associated to the relation "A is arithmetic in B". $\endgroup$ Commented Mar 23, 2023 at 18:17
  • 2
    $\begingroup$ Ah, that makes sense. Sorry for the misunderstanding. $\endgroup$ Commented Mar 23, 2023 at 19:17

3 Answers 3

5
$\begingroup$

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.

$\endgroup$
14
  • 2
    $\begingroup$ Vote up this comment if I should delete this answer, which is based on a misunderstanding of the question. $\endgroup$ Commented Mar 23, 2023 at 19:18
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Mar 24, 2023 at 0:03
  • 1
    $\begingroup$ @James Yes, this is a classic resut of Spector; see the discussion at this old MO post. $\endgroup$ Commented Mar 24, 2023 at 0:20
  • 1
    $\begingroup$ @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 $\endgroup$ Commented Mar 24, 2023 at 5:07
  • 1
    $\begingroup$ 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$. $\endgroup$ Commented Mar 24, 2023 at 16:54
3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thanks, sorry for being dense. $\endgroup$ Commented Apr 12, 2023 at 15:43
  • 1
    $\begingroup$ @PeterGerdes All good, it makes forcing easier! $\endgroup$ Commented Apr 12, 2023 at 16:31
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.