ОБ ИНТЕРПРЕТАЦИЯХ АРИФМЕТИКИ ПРЕСБУРГЕРА В АРИФМЕТИКАХ БЮХИ

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Только для подписчиков

Аннотация

Арифметики Бюхи BAn, \(n \geqslant 2\), являются расширениями арифметики Пресбургера унарным функциональным символом \({{V}_{n}}(x)\), обозначающим наибольшую степень n, делящую x. Определимость множества в BAn эквивалентна распознаванию его конечным автоматом, принимающим числа в n‑ичной записи. Мы рассматриваем интерпретации арифметики Пресбургера в стандартной модели BAn и показываем, что для всякой такой интерпретации внутренняя модель изоморфна стандартной. Это дает ответ на вопрос А. Виссера, касающийся интерпретаций некоторых слабых арифметических теорий в себя.

Об авторах

А. А. Запрягаев

Национальный исследовательский университет “Высшая школа экономики”

Автор, ответственный за переписку.
Email: azapryagaev@hse.ru
Россия, Москва

Список литературы

  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

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© А.А. Запрягаев, 2023