Originally asked at MSE:
Let $\Sigma=\{+,<,0,1\}$ be the usual language of Presburger arithmetic. Given a "reasonable" logic $\mathcal{L}$, let $\mathbb{Pres}(\mathcal{L})$ be the $\mathcal{L}$-theory consisting of
Axioms 1-4 of the usual presentation of Presburger arithmetic, and
for each $\ma...
I recently became interested in some problems concerning decidability of extensions of Presburger arithmetic. However, being a number-theorist rather than a logician, I am confused by some notational questions which are probably very basic.
Presburger arithmetic is the first order theory of the i...
Fischer and Rabin proved a superexponential bound $2^{2^{cn}}$ for the worst-case length of a proof of a proposition of length $n$ in Presburger arithmetic. The result is in
Michael J. Fischer and Michael O. Rabin, Super-Exponential Complexity of Presburger Arithmetic, Proceedings of the SIAM-A...
Fischer and Rabin proved a superexponential bound $2^{2^{cn}}$ for the worst-case length of a proof of a proposition of length $n$ in Presburger arithmetic. The result is in
Michael J. Fischer and Michael O. Rabin, Super-Exponential Complexity of Presburger Arithmetic, Proceedings of the SIAM-A...
