?
Presburger arithmetic and Visser's conjecture
Ch. 18.
Presburger Arithmetic the true theory of natural numbers with addition. We show that the interpretations of Presburger Arithmetic in itself are definably isomorphic to the trivial one, confirming the conjecture of A. Visser. To prove that, we develop a characterization of linear orderings interpretable in (N, +). We show that all interpretable linear orderings can be expressed as a restriction of the lexicographical ordering on Z_k for some k to some Presburger-definable set. This generalizes the results of Zapryagaev, A., Pakhomov F.: Interpretations of Presburger arithmetic in itself. International Symposium on Logical Foundations of Computer Science. Springer, Cham (2018) where the one-dimensional result was proven.
Pahomov F., Zapryagaev A., Logic Journal of the IGPL 2026 Vol. 34 No. 4 Article jzag045
We prove the linear orders first-order definable in the standard model (Z;<,+) of Presburger arithmetic are exactly those that are (Z;<,+)-definably embeddable into the lexicographic ordering on Z^n for some n. ...
Added: July 16, 2026
Zapryagaev A., / Series arXiv "math". 2023.
Büchi arithmetics BA_n, n≥2, are extensions of Presburger arithmetic with an unary functional symbol V_n(x) denoting the largest power of n that divides x. A rank of a linear order is the minimal number of condensations required to reach a finite order. We show that linear orders of arbitrarily large finite rank can be interpreted in BA_n. We also prove that the extension ...
Added: October 25, 2023
Zapryagaev A., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2023 Т. 510 С. 3–7
Büchi arithmetics BAn, , are extensions of Presburger arithmetic with an unary functional symbol
denoting the largest power of n that divides x. Definability of a set in BAn is equivalent to its recognizability
by a finite automaton receiving numbers in their n-ary expansion. We consider the interpretations of Presburger
Arithmetic in the standard model of BAn and ...
Added: July 27, 2023
Zapryagaev A., / Series arXiv "math". 2022.
Büchi arithmetics BA_n, n >= 2, are extensions of Presburger arithmetic with an unary functional symbol V_n(x) denoting the largest power of n that divides x. Definability of a set in BA_n is equivalent to its recognizability by a finite automaton receiving numbers in their n-ary expansion. We show that Büchi arithmetics BA_n and BA_m ...
Added: December 5, 2022
Zorile Dorina D., Тенденции развития науки и образования 2021 Т. 75 № 3 С. 37–42
The article deals with the involving into the history of law the methodology of a new branch - jurislinguistics and of a traditional one - comparativistics, wich supply methdological approaches to the historical investigations. The features of its implementation in order to acheave a correct translation of foreign legal texsts and interpretation of their terminology are ...
Added: December 4, 2022
Zapryagaev A., В кн.: Двенадцатые Смирновские чтения: материалы Международной научной конференции, Москва, 24–26 июня 2021 г.: М.: Русское общество истории и философии науки, 2021. С. 16–18.
Мы рассматриваем многомерные интерпретации линейных порядков в стандартной модели (N, +) арифметики Пресбургера. Устанавливается, что всякий такой порядок переводится определимым изоморфизмом в сужение лексикографического порядка Z 𝑛 на некоторое определимое множество для достаточно большого 𝑛. Это даёт более простое доказательство гипотезы Виссера об определимом изоморфизме тождественной всякой интерпретации самой арифметики Пресбургера в (N, +). ...
Added: June 28, 2021
Pahomov F., Zapryagaev A., Journal of Logic and Computation 2020 Vol. 30 No. 8 P. 1681–1693
Presburger arithmetic is the true theory of natural numbers with addition. We study interpretations of Presburger arithmetic in itself. The main result of this paper is that all self-interpretations are definably isomorphic to the trivial one. Here we consider interpretations that might be multi-dimensional. We note that this resolves a conjecture by Visser (1998, An ...
Added: November 12, 2020
Zapryagaev A., / Series arXiv "math". 2019. No. 1911.07182.
Presburger Arithmetic PrA is the true theory of natural numbers with addition. We consider linear orderings interpretable in Presburger Arithmetic and establish various necessary and sucient conditions for interpretability depending on dimension n of interpretation. We note this problem is relevant to the interpretations of Presburger Arithmetic in itself, as well as the characterization of ...
Added: November 28, 2019
Zapryagaev A., Pahomov F., , in: International Symposium on Logical Foundations of Computer Science, LFCS 2018Vol. 10703.: Springer, 2018. P. 354–367.
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 ...
Added: October 25, 2019
Zapryagaev A., Pahomov F., , in: International Symposium on Logical Foundations of Computer Science, LFCS 2018Vol. 10703.: Springer, 2018. P. 354–367.
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 ...
Added: April 11, 2018
Beklemishev L. D., Оноприенко А. А., Математический сборник 2015 Т. 206 № 9 С. 3–20
We formulate some term rewriting systems in which the number of computation steps is finite for each output, but this number cannot be bounded by a provably total computable function in Peano arithmetic PA. Thus, the termination of such systems is unprovable in PA. These systems are derived from an independent combinatorial result known as the Worm ...
Added: March 13, 2016