Timeline for Special classes of the arithmetical hierarchy of sentences of finite-order arithmetic
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 4, 2021 at 17:10 | vote | accept | BPP | ||
| Aug 3, 2021 at 22:44 | answer | added | Noah Schweber | timeline score: 2 | |
| Aug 3, 2021 at 22:17 | history | edited | YCor | CC BY-SA 4.0 |
removed capitals from title
|
| Aug 3, 2021 at 22:14 | comment | added | BPP | I originally meant what you're calling a simple notion of deduction, so I think I was wrong. But deduction with the $\omega$-rule is not simple in your sense, so that question is still non-trivial, right? | |
| Aug 3, 2021 at 22:03 | comment | added | Noah Schweber | I mean, before you can be wrong or not you need to specify what notion of "follows from" you have in mind. The computability-theoretic point in my comment above means that any "simple" notion of deduction won't do the trick (e.g. it can't be a proof in the sense of Henkin semantics since the set of Henkin consequences of a ${\bf 0^{(\omega)}}$-computable theory will be ${\bf 0^{(\omega+1)}}$-computable). | |
| Aug 3, 2021 at 21:57 | comment | added | BPP | I could be misinterpreting what they proved. My understanding is that they proved that every true $\Pi^1_1$ sentence is provable using the $\omega$-rule. I assumed this is equivalent to saying that every true $\Pi^1_1$ sentence follows from true arithmetic sentences, but now I see that I could be wrong in assuming that (although I'm not sure why that would be wrong). If I am wrong (in which case the answer to my question is $m=0$ and any $n$), I'd still be interested in the modified question where we allow the use of the $\omega$-rule in the definition of "follows from" in step 2. | |
| Aug 3, 2021 at 21:08 | comment | added | Noah Schweber | I don't have access to the linked article but I don't see a sense in which $\Pi^1_1$ sentences follow from true arithmetic sentences in general. There's a very coarse obstacle here: the true first-order theory of $\mathbb{N}$ has Turing degree ${\bf 0^{(\omega)}}$ but the true $\Pi^1_1$ theory of $\mathbb{N}$ isn't even hyperarithmetic. | |
| Aug 3, 2021 at 20:47 | history | asked | BPP | CC BY-SA 4.0 |