Timeline for Code universal arithmetical sets by a hyperarithmetical set?
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 15, 2020 at 7:27 | history | edited | CommunityBot |
Commonmark migration
|
|
| Jul 25, 2011 at 18:05 | comment | added | Cole Leahy | You've helped me a lot on this. Thanks. | |
| Jul 25, 2011 at 18:04 | vote | accept | Cole Leahy | ||
| Jul 25, 2011 at 14:57 | comment | added | Ali Enayat | @Cole: my choice was informed by the fact that the truth set of $\Sigma_n$-sentences of arithmetic is Turing equivalent to $0^{(n)}$. | |
| Jul 25, 2011 at 5:20 | comment | added | Cole Leahy | @Ali: When you said we could "identify" the sets S-n from my original posting with the codeset for Sigma-0-n truths of arithmetic, did you have something special in mind, or were you just observing that both are Sigma-0-n complete with respect to Turing reducibility? | |
| Jul 25, 2011 at 5:09 | comment | added | Cole Leahy | @Ali: Your approach is sensible. When I spoke of purity, perhaps I was just trying to rationalize having spent time reinventing a wheel. In any case, it was a good exercise for a student like me. | |
| Jul 25, 2011 at 2:33 | comment | added | Ali Enayat | @Cole: everything else being equal, my approach to MO answers gravitates towards not* re-inventing the wheel. For many of us, Logic, Model Theory, and Recursion Theory are all parts of the same subject; with all due respect to purity of methods; whose charms I will never deny. | |
| Jul 24, 2011 at 23:27 | comment | added | Cole Leahy | Thanks for your reply, Ali. Lamentably, I didn't mention that I seek a more direct proof that there is a set Q meeting my description. Before posting, I had already skimmed the part of Rogers you mention; I wasn't satisfied with the observation that the codeset of true arithmetic is hyperarithmetical but not arithmetical. This is partly because that observation doesn't immediately yield a Q as I described, and partly because it requires a detour through logic and model theory which, for the sake of purity, I want to avoid. I think (?) I've found a more recursion theoretic proof, posted below. | |
| Jul 23, 2011 at 22:38 | history | edited | Ali Enayat | CC BY-SA 3.0 |
editorial clean-up
|
| Jul 23, 2011 at 22:04 | history | answered | Ali Enayat | CC BY-SA 3.0 |