ON INTERPRETATIONS OF PRESBURGER ARITHMETIC IN BÜCHI ARITHMETICS
- 作者: Zapryagaev A.1
-
隶属关系:
- National Research University “Higher School of Economics”
- 期: 卷 510, 编号 1 (2023)
- 页面: 3-7
- 栏目: МАТЕМАТИКА
- URL: https://journals.rcsi.science/2686-9543/article/view/134352
- DOI: https://doi.org/10.31857/S2686954322600641
- EDN: https://elibrary.ru/XHJOFS
- ID: 134352
如何引用文章
详细
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.
作者简介
A. Zapryagaev
National Research University “Higher School of Economics”
编辑信件的主要联系方式.
Email: azapryagaev@hse.ru
Russian Federation, Moscow
参考
- 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