Geodesic
Lattice of Definability in the Order of Rational Numbers
Matematičeskie zametki, Tome 108 (2020) no. 1, pp. 102-118.

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

A lattice of definability subspaces in the order of rational numbers is described. It is proved that this lattice consists of five subspaces defined in the paper that are generated by the following relations: “equality,” “less,” “between,” “cycle,” and “linkage.” For each of the subspaces, its width (the minimum number of arguments of a generating relation) is found and a convenient description of the automorphism group is given. Although the structure of this lattice was known previously, the proof in the paper is of syntactic nature and avoids the use of a group-theoretical method.
Keywords: finitely generated space, lattice of definability subspaces, syntactic nature. 
@article{MZM_2020_108_1_a7,
     author = {An. A. Muchnik and A. L. Semenov},
     title = {Lattice of {Definability} in the {Order} of {Rational} {Numbers}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {102--118},
     publisher = {mathdoc},
     volume = {108},
     number = {1},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2020_108_1_a7/}
}
TY  - JOUR
AU  - An. A. Muchnik
AU  - A. L. Semenov
TI  - Lattice of Definability in the Order of Rational Numbers
JO  - Matematičeskie zametki
PY  - 2020
SP  - 102
EP  - 118
VL  - 108
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2020_108_1_a7/
LA  - ru
ID  - MZM_2020_108_1_a7
ER  - 
%0 Journal Article
%A An. A. Muchnik
%A A. L. Semenov
%T Lattice of Definability in the Order of Rational Numbers
%J Matematičeskie zametki
%D 2020
%P 102-118
%V 108
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2020_108_1_a7/
%G ru
%F MZM_2020_108_1_a7
An. A. Muchnik; A. L. Semenov. Lattice of Definability in the Order of Rational Numbers. Matematičeskie zametki, Tome 108 (2020) no. 1, pp. 102-118. http://geodesic.mathdoc.fr/item/MZM_2020_108_1_a7/

[1] A. L. Semenov, “Presburgerovost predikatov, regulyarnykh v dvukh sistemakh schisleniya”, Sib. matem. zhurn., 18:2 (1977), 403–418 | MR | Zbl

[2] An. A. Muchnik, Vyrazimyi kriterii vyrazimosti v arifmetike Presburgera i ego primeneniya, Institut novykh tekhnologii, M., 1991; “The definable criterion for definability in Presburger arithmetic and its applications”, Theoret. Comput. Sci., 290:3 (2003), 1433–1444 | DOI | MR | Zbl

[3] A. Semenov, S. Soprunov, V. Uspensky, “The lattice of definability. Origins, recent developments, and further directions”, Computer Science – Theory and Applications, Lecture Notes in Comput. Sci., 8476, Springer, Cham, 2014, 23–38 | MR | Zbl

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

[5] 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

[6] A. L. Semenov, S. F. Soprunov, Lattice of Relational Algebras Definable in Integers with Successor, 2012, arXiv: 1201.4439v3

[7] A. L. Semenov, Matematicheskaya logika i algebra, Tr. MIAN, 242, Nauka, MAIK «Nauka/Interperiodika», M., 2003, 103–107 | MR | Zbl

[8] E. V. Huntington, “Inter-relations among the four principal types of order”, Trans. Amer. Math. Soc., 38:1 (1935), 1–9 | DOI | MR

[9] S. A. Adeleke, P. M. Neumann, “Relations related to betweenness: their structure and automorphisms”, Mem. Amer. Math. Soc., 131, no. 623, 1998 | DOI | MR

[10] P. Erdős, G. Szekeres, “A combinatorial problem in geometry”, Compositio Math., 2 (1935), 463–470 | MR

[11] J. Leroux, “A polynomial time Presburger criterion and synthesis for number decision diagrams”, 20th Annual IEEE Symposium on Logic in Computer Science (LICS' 05), Chicago, IL, 2005, 147–156 | DOI