All Questions
Tagged with computability-theory presburger-arithmetic
2 questions
11
votes
0
answers
233
views
+50
Is there a decidable theory of arithmetic with a non-collapsing quantifier hierarchy?
This question is very close to this old MSE question of mine, which is still unanswered.
Is there an (ideally reasonably-natural!) expansion of the structure $(\mathbb{N};+)$ in a finite language ...
- 21.2k
18
votes
3
answers
1k
views
Computable nonstandard models for weak systems of arithmetic
By Tennenbaum's theorem, PA itself does not have any computable nonstandard models. The integer polynomials which are 0 or have a positive leading coefficient form a computable nonstandard model of ...
user5810