Lattice of definability (of reducts) for integers with successor

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

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.

About the authors

Aleksei Lvovich 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 Fedorovich Soprunov

Centre of pedagogical workmanship

Email: logo@int-edu.ru
Candidate of physico-mathematical sciences

References

  1. A. Tarski, “On definable sets of real numbers”, Logic, semantics, metamathematics, 2nd ed., ed. J. Corcoran, Hackett Publishing Co., Indianapolis, IN, 1983, 110–142
  2. А. Л. Семенов, “Пресбургеровость предикатов, регулярных в двух системах счисления”, Сиб. матем. журн., 18:2 (1977), 403–418
  3. A. Bès, C. Choffrut, Theories of real addition with and without a predicate for integers
  4. 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
  5. С. Ф. Сопрунов, “Разрешимые обогащения структур”, Сложность вычислений и прикладная математическая логика, Вопросы кибернетики, 134, Науч. совет АН СССР по комплексной проблеме “Кибернетика”, М., 1988, 175–179
  6. Ан. А. Мучник, А. Л. Семeнов, “Решетка определимости в порядке рациональных чисел”, Матем. заметки, 108:1 (2020), 102–118
  7. A. L. Semenov, S. F. Soprunov, “A combinatorial version of the Svenonius theorem on definability”, Log. J. IGPL, 23:6 (2015), 966–975
  8. А. Л. Семeнов, “Условия конечности для алгебр отношений”, Математическая логика и алгебра, Сборник статей. К 100-летию со дня рождения академика Петра Сергеевича Новикова, Труды МИАН, 242, Наука, МАИК «Наука/Интерпериодика», М., 2003, 103–107
  9. C. Frasnay, “Quelques problèmes combinatoires concernant les ordres totaux et les relations monomorphes”, Ann. Inst. Fourier (Grenoble), 15:2 (1965), 415–524
  10. D. Macpherson, “A survey of homogeneous structures”, Discrete Math., 311:15 (2011), 1599–1634
  11. P. J. Cameron, “Transitivity of permutation groups on unordered sets”, Math. Z., 148:2 (1976), 127–139
  12. M. Junker, M. Ziegler, “The 116 reducts of $(mathbb Q,
  13. M. Bodirsky, M. Pinsker, A. Pongracz, “The 42 reducts of the random ordered graph”, Proc. Lond. Math. Soc. (3), 111:3 (2015), 591–632
  14. G. Conant, “There are no intermediate structures between the group of integers and Presburger arithmetic”, J. Symb. Log., 83:1 (2018), 187–207
  15. 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
  16. L. Svenonius, “A theorem on permutations in models”, Theoria (Lund), 25:3 (1959), 173–178
  17. W. Hodges, Model theory, Encyclopedia Math. Appl., 42, Cambridge Univ. Press, Cambridge, 1993, xiv+772 pp.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2021 Semenov A.L., Soprunov S.F.

Согласие на обработку персональных данных

 

Используя сайт https://journals.rcsi.science, я (далее – «Пользователь» или «Субъект персональных данных») даю согласие на обработку персональных данных на этом сайте (текст Согласия) и на обработку персональных данных с помощью сервиса «Яндекс.Метрика» (текст Согласия).