Interpretations of Presburger Arithmetic in Itself
| Autor: | Alexander Zapryagaev, Fedor Pakhomov |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Rank (linear algebra)
010102 general mathematics Dimension (graph theory) Mathematics::Classical Analysis and ODEs Hausdorff space Order (ring theory) Natural number 0102 computer and information sciences 01 natural sciences Combinatorics Identity (mathematics) 010201 computation theory & mathematics Bounded function 0101 mathematics Presburger arithmetic Computer Science::Formal Languages and Automata Theory Mathematics |
| Zdroj: | Logical Foundations of Computer Science ISBN: 9783319720555 LFCS |
| DOI: | 10.1007/978-3-319-72056-2_22 |
| Popis: | Presburger arithmetic \(\mathop {\mathbf {PrA}}\nolimits \) is the true theory of natural numbers with addition. We study interpretations of \(\mathop {\mathbf {PrA}}\nolimits \) 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 \((\mathbb {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 \(\mathop {\mathbf {PrA}}\nolimits \) it follows that \(\mathop {\mathbf {PrA}}\nolimits \) isn’t one-dimensionally interpretable in any of its finite subtheories. We note that the latter was conjectured by A. Visser. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|