Back to Search
Start Over
Interpretations of Presburger Arithmetic in Itself
- Publication Year :
- 2017
-
Abstract
- Presburger arithmetic PrA is the true theory of natural numbers with addition. We study interpretations of PrA in itself. We prove that all one-dimensional self-interpretations are definably isomorphic to the identity self-interpretation. In order to prove the results we show that all linear orders that are interpretable in (N,+) are scattered orders with the finite Hausdorff rank and that the ranks are bounded in terms of the dimension of the respective interpretations. From our result about self-interpretations of PrA it follows that PrA isn't one-dimensionally interpretable in any of its finite subtheories. We note that the latter was conjectured by A. Visser.<br />Comment: Published in proceedings of LFCS 2018
- Subjects :
- Mathematics - Logic
03C40
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.1709.07341
- Document Type :
- Working Paper