Timeline for 2-REA PA degrees
Current License: CC BY-SA 4.0
28 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 12, 2021 at 5:13 | history | edited | Michael Hardy | CC BY-SA 4.0 |
added 7 characters in body
|
| May 12, 2021 at 4:00 | vote | accept | Peter Gerdes | ||
| May 12, 2021 at 3:59 | answer | added | Joe Miller | timeline score: 6 | |
| May 12, 2021 at 3:23 | comment | added | Peter Gerdes | ohh duh yah I was misreading thanks. Re elementary diagram was a bit confused about how u handle non-std params but I guess we just picking some consistent path and using Henkinization so not a problem. OK thanks a huge amount that's a neat proof...if you want karma or to close Q feel free to write it up as ans or if not I'll do it in a couple days if still marked open since this is a great ans. Ill up vote comments once I on computer again not phone. | |
| May 12, 2021 at 3:14 | comment | added | Patrick Lutz | @PeterGerdes In Dan's argument, P computes both Q and S and S is PA over Q so P is also PA over Q. | |
| May 12, 2021 at 3:13 | comment | added | Patrick Lutz | @PeterGerdes Not sure if this was clear: my first comment talking about nonstandard models of PA was sketching an argument that low r.e. sets are low-for-PA. My second comment was responding to your question abut the Reimann-Day paper. | |
| May 12, 2021 at 3:12 | comment | added | Peter Gerdes | @DanTuretsky I'm surely just being dumb now but what is S in your argument. We want Q so P is PA over Q but your arg only helps if there infinite path with second component P which is just another way of saying there is some Q of PA degree which P is PA over. | |
| May 12, 2021 at 3:11 | comment | added | Patrick Lutz | The standard system of a model M of PA is the set of subsets of $\mathbb{N}$ which are equal to $x \cap \mathbb{N}$ for some $M$-finite set $x$. | |
| May 12, 2021 at 3:07 | comment | added | Patrick Lutz | @PeterGerdes the elementary diagram of the true natural numbers is Turing equivalent to $0^{(\omega)}$ but every PA degree computes the elementary diagram of some model of PA. | |
| May 12, 2021 at 3:05 | comment | added | Peter Gerdes | @PatrickLutz How does the elementary diagram help here? Isn't that something which computes 0^n for all n? I presume this is explaining connection between being contained in the standard initial segment (or does std system mean something different?) | |
| May 12, 2021 at 3:01 | comment | added | Dan Turetsky | The set of (X,Y) such that X is a completion of PA and Y is a completion of $PA^X$ is a $\Pi^0_1$-class. $P$ computes some element (Q, S), and as it computes $S$, $P$ is PA over $Q$. | |
| May 12, 2021 at 2:58 | comment | added | Patrick Lutz | @PeterGerdes If T is a computable infinite binary tree and M is a nonstandard model of PA then there is a path through T which is in the standard system of M. The elementary diagram of M is PA over everything in the standard system of M. | |
| May 12, 2021 at 2:54 | comment | added | Peter Gerdes | Also I'm having trouble with the proof of 2.3 in the linked paper as they say it only uses two facts but then there is this Q whose existence I'm not seeing a justification for. Am I being dumb? | |
| May 12, 2021 at 2:54 | comment | added | Patrick Lutz | The argument I know of goes like this though: if P is PA then P codes the first order theory of some model M of PA. There are two cases: either there is a nonstandard element n of M such that the enumeration of A below n is correct or for every nonstandard element n of M, there is some element of the complement of A that M believes is enumerated into A below n. In the former case, A is in the standard system of M so P is PA relative to A. And in the latter case, A + P can compute 0'. | |
| May 12, 2021 at 2:52 | comment | added | Dan Turetsky | Edit: Nevermind, I see. We're considering P+A, not P. | |
| May 12, 2021 at 2:51 | comment | added | Patrick Lutz | @DanTuretsky Corollary 2.3 of that paper says that if A is r.e. and P is PA such that P computes A then either P computes 0' or P is PA relative to A. If A is low then both of these conclusions imply P is PA relative to A. | |
| May 12, 2021 at 2:51 | comment | added | Dan Turetsky | Sorry, I deleted my earlier comment about homeomorphic $\Pi^0_1$ classes because I'm suddenly doubting it. | |
| May 12, 2021 at 2:49 | comment | added | Peter Gerdes | Ohh that's good thx! I'm curious how being r.e. helps in that computable homeomorphism question. | |
| May 12, 2021 at 2:49 | comment | added | Dan Turetsky | I agree that low r.e. is low-for-PA, but I don't see why it follows from 2.3 in the linked paper? | |
| May 12, 2021 at 2:46 | comment | added | Patrick Lutz | @PeterGerdes The fact that a low r.e. set is low-for-PA does relativize and so you can continue the argument I gave by induction. The alternate argument I know of that low r.e. sets are low-for-PA is not the same as what Dan mentioned though (it involves reasoning in the nonstandard model of PA coded by the PA degree and actually shows that if A is r.e. and P is PA then either A + P is PA relative to A or A + P computes 0'). | |
| May 12, 2021 at 2:30 | comment | added | Peter Gerdes | Dan, yes I see (well already knew...nicely bounded number of mind changes) the w-REA point but are you assuming or know that collarly 2.3 relativizes and are arguing by induction to reach the conclusion for n-REA? | |
| May 12, 2021 at 2:27 | comment | added | Peter Gerdes | Hmm, that looks like a counterexample alright. Not too surprised as I haven't put in the detailed effort to double check my reasoning. Thanks greatly .. for some reason I'm not seeing comment upvotes. | |
| May 12, 2021 at 2:21 | comment | added | Dan Turetsky | Continuing what Patrick wrote, no n-REA set is of low PA degree. In contrast, the construction of the low basis theorem produces a set of $\omega$-REA degree. | |
| May 12, 2021 at 1:13 | comment | added | Patrick Lutz | Unless I'm missing something, I think your theorem is false. Call a set A low-for-PA if for every PA degree P, A+P is PA relative to A. It follows from Corollary 2.3 of this paper by Reimann and Day that every low r.e. set is low-for-PA (I also know of another more direct proof of this fact). Suppose A_0 is r.e., A_1 is r.e. relative to A_0, A_0+A_1 is low and A_0+A_1 is PA. Since A_0 is low-for-PA, A_0+A_1 is PA relative to A_0. But by Arslanov's completeness criterion, this means that A_0+A_1 is Turing equivalent to the jump of A_0 and hence not low. | |
| May 11, 2021 at 22:04 | comment | added | Peter Gerdes | You can sorta think of n-REA sets as Sigma n sets that carry along their construction via repeated Sigma 1 definitions but carrying around the sets used to build it makes it much harder to build sets that have limited computational power. | |
| May 11, 2021 at 21:35 | comment | added | Peter Gerdes | Because you have to build it up in pieces and keep them all (A1 on its own is Sigma2 but it's not 2-REA ..A0+A1 is). For instance, you can have a non-computable Sigma n set that doesn't compute any r.e set. The same isn't true of an n-REA set because first non-computable Ai is r.e.. Practically speaking, in this case the problem is you have this r.e part of set and u can't unenumerate elements when you might like to for lowness. | |
| May 11, 2021 at 21:26 | comment | added | Emil Jeřábek | Maybe I'm confused by the definition, but how is an $n$-REA degree different from $\Sigma_{n+1}$? There are low $\Delta_2$ PA-degrees, FWIW. | |
| May 11, 2021 at 20:48 | history | asked | Peter Gerdes | CC BY-SA 4.0 |