Timeline for Does every cofinal branch through Kleene's O compute true arithmetic?
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 11, 2020 at 8:05 | vote | accept | Joel David Hamkins | ||
| May 10, 2020 at 22:47 | answer | added | Dan Turetsky | timeline score: 10 | |
| May 10, 2020 at 18:24 | comment | added | Joel David Hamkins | Yes, Andreas @AndreasBlass, I agree completely. This was the main reason to think that the Turing degree of the cofinal paths should be high. But I don't see how to reduce the hyperarithmetic reduction to Turing reduction. | |
| May 10, 2020 at 17:52 | comment | added | Andreas Blass | A small observation: $O$ is hyperarithmetic in any of its paths $z$. The point is that $n\in O$ iff there's an $<_O$-preserving embedding of the $<_O$-predecessors of $n$ into $z$. That makes $O$ $\Sigma^1_1$ in $z$, and since it's $\Pi^1_1$ even without $z$, it's hyperarithmetic in $z$. There might be some hope for estimating the relevant level of the $z$-hyperarithmetic hierarchy and so dragging this observation down to a level near what you asked about. | |
| May 10, 2020 at 16:06 | comment | added | Joel David Hamkins | More specifically, my idea about type 1 and type 2 is that we will stick on another $\omega$ many terms (by powers of $2$) and then include the index $3\cdot 5^e$, where $e$ is a program that is recognizably of the form (1) wait for $p$ to halt, then climb through that $\omega$ tower, or (2) climb through the tower as long as $p$ is not halting. Since it is dense to have this occur (with programs recognizably of this form), we can eventually find it in $z$. So we can decide the halting problem from $z$. By now doing this in a nested way, we can similarly decide TA. | |
| May 10, 2020 at 15:23 | comment | added | Joel David Hamkins | @NoahSchweber I can prove that the generic path you describe must at least compute the halting problem. The reason is that for any program p it is dense to include an index either of type 1 or type 2, where the type 1 index works only if p halts and the index of type 2 works only if it doesn't. We can parameterize those program types, and simply search for it in z, thereby solving the halting problem. I believe that this idea ramps up to get TA from any generic path. | |
| May 10, 2020 at 13:43 | comment | added | Joel David Hamkins | Perhaps we can use that all bounded initial segments of the branch are uniformly c.e. That is, for each n in z, we can enumerate $z\upharpoonright n$. | |
| May 10, 2020 at 13:42 | comment | added | Joel David Hamkins | I see; you want to argue something like this: it is dense that a given TM program does not compute some instance of TA. | |
| May 10, 2020 at 13:40 | comment | added | Noah Schweber | Yes, it's not enough to use the isomorphism type of the forcing. But there might still be something we can get from the fact that the set of notations of a given length extending a given notation isn't too complicated. | |
| May 10, 2020 at 13:38 | comment | added | Joel David Hamkins | This forcing is isomorphic to the forcing to add a Cohen real. But the Turing degree of the branches will not generally be respected by the isomorphism. So I'm not sure how much we can get this way. | |
| May 10, 2020 at 13:28 | comment | added | Noah Schweber | An idea: fix a sequence $A=(\alpha_i)_{i\in\omega}$ cofinal in $\omega_1^{CK}$. Now consider the forcing notion $\mathbb{P}$ where conditions are finite sequences $(n_i)_{i<k}$ with $\vert n_i\vert_\mathcal{O}=\alpha_i$ and $n_j<_\mathcal{O}n_{i}$ for all $j<i<k$ (and conditions are ordered by extension as usual). How complicated are the correspondingly generic paths, that is, the $<_\mathcal{O}$-downwards closures of the set of notations occurring in the conditions in the generic filter? (And I think this is independent of choice of $A$.) | |
| May 10, 2020 at 11:48 | history | edited | Joel David Hamkins | CC BY-SA 4.0 |
fixed some grammar issues; improved the writing
|
| May 10, 2020 at 11:29 | history | edited | Joel David Hamkins | CC BY-SA 4.0 |
added 110 characters in body
|
| May 10, 2020 at 11:24 | history | asked | Joel David Hamkins | CC BY-SA 4.0 |