Решетка определимости (редуктов) для целых чисел с операцией следования
- Авторы: Семёнов А.Л.1,2,3, Сопрунов С.Ф.4
-
Учреждения:
- Московский государственный университет имени М. В. Ломоносова
- Федеральный исследовательский центр «Информатика и управление» Российской академии наук
- Московский физико-технический институт (национальный исследовательский университет)
- Центр педагогического мастерства
- Выпуск: Том 85, № 6 (2021)
- Страницы: 245-258
- Раздел: Статьи
- URL: https://ogarev-online.ru/1607-0046/article/view/133869
- DOI: https://doi.org/10.4213/im9107
- ID: 133869
Цитировать
Открытый доступ
Доступ предоставлен
Только для подписчиков
Аннотация
В статье описана решетка определимости для структуры целых чисел с операцией следования (операцией $y=x+1$). Элементы решетки, также называемые редуктами, образуют три (естественно задаваемых) бесконечных серии отношений. Доказательство использует вариант теоремы Свенониуса для специального вида структур.Библиография: 17 наименований.
Ключевые слова
Об авторах
Алексей Львович Семёнов
Московский государственный университет имени М. В. Ломоносова; Федеральный исследовательский центр «Информатика и управление» Российской академии наук; Московский физико-технический институт (национальный исследовательский университет)
Email: alsemno@ya.ru
доктор физико-математических наук, профессор
Сергей Федорович Сопрунов
Центр педагогического мастерства
Email: logo@int-edu.ru
кандидат физико-математических наук
Список литературы
- A. Tarski, “On definable sets of real numbers”, Logic, semantics, metamathematics, 2nd ed., ed. J. Corcoran, Hackett Publishing Co., Indianapolis, IN, 1983, 110–142
- А. Л. Семенов, “Пресбургеровость предикатов, регулярных в двух системах счисления”, Сиб. матем. журн., 18:2 (1977), 403–418
- A. Bès, C. Choffrut, Theories of real addition with and without a predicate for integers
- C. C. Elgot, M. O. Rabin, “Decidability and undecidability of extensions of second (first) order theory of (generalized) successor”, J. Symb. Log., 31:2 (1966), 169–181
- С. Ф. Сопрунов, “Разрешимые обогащения структур”, Сложность вычислений и прикладная математическая логика, Вопросы кибернетики, 134, Науч. совет АН СССР по комплексной проблеме “Кибернетика”, М., 1988, 175–179
- Ан. А. Мучник, А. Л. Семeнов, “Решетка определимости в порядке рациональных чисел”, Матем. заметки, 108:1 (2020), 102–118
- A. L. Semenov, S. F. Soprunov, “A combinatorial version of the Svenonius theorem on definability”, Log. J. IGPL, 23:6 (2015), 966–975
- А. Л. Семeнов, “Условия конечности для алгебр отношений”, Математическая логика и алгебра, Сборник статей. К 100-летию со дня рождения академика Петра Сергеевича Новикова, Труды МИАН, 242, Наука, МАИК «Наука/Интерпериодика», М., 2003, 103–107
- C. Frasnay, “Quelques problèmes combinatoires concernant les ordres totaux et les relations monomorphes”, Ann. Inst. Fourier (Grenoble), 15:2 (1965), 415–524
- D. Macpherson, “A survey of homogeneous structures”, Discrete Math., 311:15 (2011), 1599–1634
- P. J. Cameron, “Transitivity of permutation groups on unordered sets”, Math. Z., 148:2 (1976), 127–139
- M. Junker, M. Ziegler, “The 116 reducts of $(mathbb Q,
- M. Bodirsky, M. Pinsker, A. Pongracz, “The 42 reducts of the random ordered graph”, Proc. Lond. Math. Soc. (3), 111:3 (2015), 591–632
- G. Conant, “There are no intermediate structures between the group of integers and Presburger arithmetic”, J. Symb. Log., 83:1 (2018), 187–207
- A. Semenov, S. Soprunov, V. Uspensky, “The lattice of definability. Origins, recent developments, and further directions”, Computer science – theory and applications, Proceedings of the 9th international computer science symposium in Russia, CSR 2014 (Moscow, 2014), Lecture Notes in Comput. Sci., 8476, Springer, Cham, 2014, 23–38
- L. Svenonius, “A theorem on permutations in models”, Theoria (Lund), 25:3 (1959), 173–178
- W. Hodges, Model theory, Encyclopedia Math. Appl., 42, Cambridge Univ. Press, Cambridge, 1993, xiv+772 pp.
Дополнительные файлы
