Timeline for Complexity of induction formulas in proof theoretic ordinals
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 15, 2020 at 7:27 | history | edited | CommunityBot |
Commonmark migration
|
|
| Sep 30, 2017 at 23:04 | vote | accept | Erfan Khaniki | ||
| Sep 30, 2017 at 2:32 | answer | added | Dmytro Taranovsky | timeline score: 3 | |
| Aug 14, 2017 at 2:37 | comment | added | Erfan Khaniki | @AndreasBlass: Actually, my main concern is about $PA$ and weaker systems. | |
| Aug 14, 2017 at 2:32 | comment | added | Andreas Blass | I agree that, below $\varepsilon_0$ (and in fact for some distance beyond that), all the notation systems I've seen are rather obviously equivalent, so I'd expect their equivalence to be provable in rather weak theories. The problems begin either at higher ordinals or at extremely weak theories. | |
| Aug 14, 2017 at 2:28 | comment | added | Erfan Khaniki | @AndreasBlass: At least for ordinals below $\epsilon_0$, a notation system is introduced in Ordinal Notations and Well-Orderings in Bounded Arithmetic (cs.swan.ac.uk/~csarnold/publ/show-paper.php?10) with low complexity. | |
| Aug 14, 2017 at 2:00 | comment | added | Andreas Blass | I don't know enough proof theory to say anything really helpful here, but I should point out that, when the complexity of the class $X$ in $TI(\alpha,X)$ gets low enough, you need to worry, more the usual, about the details of the notation system used for $\alpha$. | |
| Aug 13, 2017 at 19:48 | history | asked | Erfan Khaniki | CC BY-SA 3.0 |