Email this article 
ON INTERPRETATIONS OF PRESBURGER ARITHMETIC IN BÜCHI ARITHMETICS
- Authors: Zapryagaev A.A.1
-
Affiliations:
- National Research University “Higher School of Economics”
- Issue: Vol 510, No 1 (2023)
- Pages: 3-7
- Section: MATHEMATICS
- URL: https://rjsvd.com/2686-9543/article/view/647851
- DOI: https://doi.org/10.31857/S2686954322600641
- EDN: https://elibrary.ru/XHJOFS
- ID: 647851
Cite item
Open Access
Access granted
Subscription Access
Abstract
Büchi arithmetics BAn, \(n \geqslant 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 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 show that each such interpretation has an internal model isomorphic to the standard one. This answers a question by A. Visser on the interpretations of certain weak arithmetical theories in themselves.
About the authors
A. A. Zapryagaev
National Research University “Higher School of Economics”
Author for correspondence.
Email: azapryagaev@hse.ru
Russian Federation, Moscow
References
- Büchi J.R. Weak second-order arithmetic and finite automata // Mathematical Logic Quarterly. 1960. V. 6. № 1–6. P. 66–92. https://doi.org/10.1002/malq.19600060105
- Bruyère V. Entiers et automates finis // Mémoire de fin d’études, Université de Mons (1985).
- Bruyère V. et al. Logic and p-recognizable sets of integers // Bulletin of the Belgian Mathematical Society Simon Stevin. 1994. V. 1. № 2. P. 191–238. https://doi.org/10.36045/bbms/1103408547
- Cobham A. On the base-dependence of sets of numbers recognizable by finite automata // Mathematical systems theory. 1969. V. 3. № 2. P. 186–192. https://doi.org/10.1007/BF01746527
- Семёнов А.Л. Пресбургеровость предикатов, регулярных в двух системах счисления // Сибирский математический журнал. 1977. Т. 18. № 2. С. 403–418. https://doi.org/10.1007/BF00967164
- Presburger M. Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt // Comptes Rendus du I congrès de Mathématiciens des Pays Slaves 92–101, 1929.
- Pakhomov F., Zapryagaev A. Multi-dimensional interpretations of Presburger arithmetic in itself // Journal of Logic and Computation. 2020. V. 30. № 8. P. 1681–1693. https://doi.org/10.1093/logcom/exaa050
- Tarski A., Mostowski A., Robinson R.M. Undecidable theories. North-Holland, 1953. 98 p.
- Braun G., Strüngmann L. Breaking up finite automata presentable torsion-free abelian groups // International Journal of Algebra and Computation. 2011. V. 21. № 08. P. 1463–1472. https://doi.org/10.1142/S0218196711006625
Supplementary files
