- Код статьи
- 10.31857/S2686954322600641-1
- DOI
- 10.31857/S2686954322600641
- Тип публикации
- Статус публикации
- Опубликовано
- Авторы
- Том/ Выпуск
- Том 510 / Номер выпуска 1
- Страницы
- 3-7
- Аннотация
- Арифметики Бюхи BAn, \(n \geqslant 2\), являются расширениями арифметики Пресбургера унарным функциональным символом \({{V}_{n}}(x)\), обозначающим наибольшую степень n, делящую x. Определимость множества в BAn эквивалентна распознаванию его конечным автоматом, принимающим числа в n‑ичной записи. Мы рассматриваем интерпретации арифметики Пресбургера в стандартной модели BAn и показываем, что для всякой такой интерпретации внутренняя модель изоморфна стандартной. Это дает ответ на вопрос А. Виссера, касающийся интерпретаций некоторых слабых арифметических теорий в себя.
- Ключевые слова
- формальные арифметики интерпретации автоматные структуры автоматные абелевы группы
- Дата публикации
- 17.09.2025
- Год выхода
- 2025
- Всего подписок
- 0
- Всего просмотров
- 13
Библиография
- 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
