Timeline for Is $0^{(\omega)}$ a minimal cover in the arithmetic degrees
Current License: CC BY-SA 4.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 30, 2023 at 17:59 | comment | added | Noah Schweber | @PeterGerdes See my answer. The point is that a 2-lub would be too easily decodable from any other ub. | |
| Mar 26, 2023 at 4:16 | comment | added | Peter Gerdes | 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. | |
| Mar 26, 2023 at 3:28 | comment | added | Peter Gerdes | @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! | |
| Mar 26, 2023 at 3:08 | comment | added | Noah Schweber | @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$. | |
| Mar 26, 2023 at 3:05 | comment | added | Peter Gerdes | @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? | |
| Mar 26, 2023 at 2:52 | comment | added | Peter Gerdes | 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})$? | |
| Mar 24, 2023 at 16:54 | comment | added | Noah Schweber | 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$. | |
| Mar 24, 2023 at 5:07 | comment | added | Noah Schweber | @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 | |
| Mar 24, 2023 at 4:44 | comment | added | Peter Gerdes | @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? | |
| Mar 24, 2023 at 0:20 | comment | added | Noah Schweber | @James Yes, this is a classic resut of Spector; see the discussion at this old MO post. | |
| Mar 24, 2023 at 0:03 | comment | added | Peter Gerdes | 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. | |
| Mar 23, 2023 at 22:42 | comment | added | Joel David Hamkins | 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. | |
| Mar 23, 2023 at 21:35 | comment | added | James | This argument would generalize to show there is no least upper bound to any strictly increasing sequence of Turing degrees, right? | |
| Mar 23, 2023 at 19:18 | comment | added | Joel David Hamkins | Vote up this comment if I should delete this answer, which is based on a misunderstanding of the question. | |
| Mar 23, 2023 at 15:24 | history | answered | Joel David Hamkins | CC BY-SA 4.0 |