ON INTERPRETATIONS OF PRESBURGER ARITHMETIC IN BÜCHI ARITHMETICS

封面

如何引用文章

全文:

开放存取 开放存取
受限制的访问 ##reader.subscriptionAccessGranted##
受限制的访问 订阅存取

详细

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

参考

  1. 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
  2. Bruyère V. Entiers et automates finis // Mémoire de fin d’études, Université de Mons (1985).
  3. 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
  4. 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
  5. Семёнов А.Л. Пресбургеровость предикатов, регулярных в двух системах счисления // Сибирский математический журнал. 1977. Т. 18. № 2. С. 403–418. https://doi.org/10.1007/BF00967164
  6. 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.
  7. 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
  8. Tarski A., Mostowski A., Robinson R.M. Undecidable theories. North-Holland, 1953. 98 p.
  9. 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

版权所有 © А.А. Запрягаев, 2023

##common.cookie##