Skip to main content
3 of 3
added 358 characters in body
Noah Schweber
  • 20.5k
  • 10
  • 110
  • 331

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
  • 20.5k
  • 10
  • 110
  • 331