Geodesic
Lattice of definability (of reducts) for integers with successor
Izvestiya. Mathematics , Tome 85 (2021) no. 6, pp. 1257-1269.

Voir la notice de l'article provenant de la source Math-Net.Ru

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 theorem for structures of special form.
Keywords: definability, reducts, Svenonius theorem. 
@article{IM2_2021_85_6_a7,
     author = {A. L. Semenov and S. F. Soprunov},
     title = {Lattice of definability (of reducts) for integers with successor},
     journal = {Izvestiya. Mathematics },
     pages = {1257--1269},
     publisher = {mathdoc},
     volume = {85},
     number = {6},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/IM2_2021_85_6_a7/}
}
TY  - JOUR
AU  - A. L. Semenov
AU  - S. F. Soprunov
TI  - Lattice of definability (of reducts) for integers with successor
JO  - Izvestiya. Mathematics 
PY  - 2021
SP  - 1257
EP  - 1269
VL  - 85
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IM2_2021_85_6_a7/
LA  - en
ID  - IM2_2021_85_6_a7
ER  - 
%0 Journal Article
%A A. L. Semenov
%A S. F. Soprunov
%T Lattice of definability (of reducts) for integers with successor
%J Izvestiya. Mathematics 
%D 2021
%P 1257-1269
%V 85
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IM2_2021_85_6_a7/
%G en
%F IM2_2021_85_6_a7
A. L. Semenov; S. F. Soprunov. Lattice of definability (of reducts) for integers with successor. Izvestiya. Mathematics , Tome 85 (2021) no. 6, pp. 1257-1269. http://geodesic.mathdoc.fr/item/IM2_2021_85_6_a7/

[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 ; “Sur les ensembles définissables de nombres réels I”, Fundamenta Math., 17 (1931), 210–239 | MR | DOI | Zbl

[2] A. L. Semenov, “Presburgerness of predicates regular in two number systems”, Siberian Math. J., 18:2 (1977), 289–300 | DOI | MR | Zbl

[3] A. Bès, C. Choffrut, Theories of real addition with and without a predicate for integers, arXiv: 2002.04282

[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 | DOI | Zbl

[5] S. F. Soprunov, “Razreshimye obogascheniya struktur”, Slozhnost vychislenii i prikladnaya matematicheskaya logika, Voprosy kibernetiki, 134, Nauch. sovet AN SSSR po kompleksnoi probleme “Kibernetika”, M., 1988, 175–179 | MR | Zbl

[6] An. A. Muchnik, A. L. Semenov, “Lattice of definability in the order of rational numbers”, Math. Notes, 108:1 (2020), 94–107 | DOI | DOI | MR | Zbl

[7] A. L. Semenov, S. F. Soprunov, “A combinatorial version of the Svenonius theorem on definability”, Log. J. IGPL, 23:6 (2015), 966–975 | DOI | MR | Zbl

[8] A. L. Semenov, “Finiteness conditions for algebras of relations”, Proc. Steklov Inst. Math., 242 (2003), 92–96 | MR | Zbl

[9] C. Frasnay, “Quelques problèmes combinatoires concernant les ordres totaux et les relations monomorphes”, Ann. Inst. Fourier (Grenoble), 15:2 (1965), 415–524 | DOI | MR | Zbl

[10] D. Macpherson, “A survey of homogeneous structures”, Discrete Math., 311:15 (2011), 1599–1634 | DOI | MR | Zbl

[11] P. J. Cameron, “Transitivity of permutation groups on unordered sets”, Math. Z., 148:2 (1976), 127–139 | DOI | MR | Zbl

[12] M. Junker, M. Ziegler, “The 116 reducts of $(\mathbb Q, , a)$”, J. Symb. Log., 73:3 (2008), 861–884 | DOI | MR | Zbl

[13] M. Bodirsky, M. Pinsker, A. Pongrácz, “The 42 reducts of the random ordered graph”, Proc. Lond. Math. Soc. (3), 111:3 (2015), 591–632 | DOI | MR | Zbl

[14] G. Conant, “There are no intermediate structures between the group of integers and Presburger arithmetic”, J. Symb. Log., 83:1 (2018), 187–207 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[16] L. Svenonius, “A theorem on permutations in models”, Theoria (Lund), 25:3 (1959), 173–178 | DOI | MR

[17] W. Hodges, Model theory, Encyclopedia Math. Appl., 42, Cambridge Univ. Press, Cambridge, 1993, xiv+772 pp. | DOI | MR | Zbl