Lattice of definability (of reducts) for integers with successor
- Авторлар: Semenov A.L.1,2,3, Soprunov S.F.4
-
Мекемелер:
- Lomonosov Moscow State University
- Federal Research Center ‘Informatics and Control’ of Russian Academy of Science
- Moscow Institute of Physics and Technology (National Research University)
- Centre of pedagogical workmanship
- Шығарылым: Том 85, № 6 (2021)
- Беттер: 245-258
- Бөлім: Articles
- URL: https://ogarev-online.ru/1607-0046/article/view/133869
- DOI: https://doi.org/10.4213/im9107
- ID: 133869
Дәйексөз келтіру
Ашық рұқсат
Рұқсат берілді
Тек жазылушылар үшін
Аннотация
In this paper the lattice of definability for integers with a successor (the relation $y = x + 1$) is described. The lattice, whose elements are also knows as reducts, consists of three(naturally described) infinite series of relations.The proof uses a version of the Svenonius theoremfor structures of special form.
Негізгі сөздер
Авторлар туралы
Aleksei Semenov
Lomonosov Moscow State University; Federal Research Center ‘Informatics and Control’ of Russian Academy of Science; Moscow Institute of Physics and Technology (National Research University)
Email: alsemno@ya.ru
Doctor of physico-mathematical sciences, Professor
Sergei Soprunov
Centre of pedagogical workmanship
Email: logo@int-edu.ru
Candidate of physico-mathematical sciences
Әдебиет тізімі
- 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.
Қосымша файлдар
