Skip to main content
1 of 3
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).

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.

Noah Schweber
  • 20.5k
  • 10
  • 110
  • 331