How large is the proof-theoretic ordinal of Presburger arithmetic?[]
Is it ≥ω? 80.98.179.160 15:31, December 29, 2017 (UTC)
- I would be leaning to believe the answer is \(\omega^2\). Using only addition we can define well-orders of any smaller length and, by completeness, Presburger arithmetic proves induction along them. I don't think in this language we can even express longer well-orders, so that sets the PTO at \(\omega^2\). LittlePeng9 (talk) 15:50, December 29, 2017 (UTC)
- OK, then is this the weakest arithmetic? 80.98.179.160 16:26, December 29, 2017 (UTC)
- There are arithmetics which don't even prove usual induction, like Robinson's Q. LittlePeng9 (talk) 19:03, December 29, 2017 (UTC)
- By weaker arithmetics I mean arithmetics with smaller PTO. 80.98.179.160 18:10, December 30, 2017 (UTC)
- See here. LittlePeng9 (talk) 18:31, December 30, 2017 (UTC)
- So Q has PTO of \(\omega\). Is Q the weakest? 80.98.179.160 18:59, January 23, 2018 (UTC)