Automorphisms and Definability (of Reducts) for Upward Complete Structures

Mathematics. 2022. Vol. 10. No. 20. Article 3748.

Semenov A., Soprunov S.

The Svenonius theorem establishes the correspondence between definability of relations in a countable structure and automorphism groups of these relations in extensions of the structure. This may help in finding a description of the lattice constituted by all definability spaces (reducts) of the original structure. Results on definability lattices were previously obtained only for ω-categorical structures with finite signature. In our work, we introduce the concept of an upward complete structure and define the upward completion of a structure. For upward complete structures, the Galois correspondence between definability lattice and the lattice of closed supergroups of the automorphism group of the structure is an anti-isomorphism. We describe the natural class of structures which have upward completion, we call them discretely homogeneous graphs, present the explicit construction of their completion and automorphism groups of completions. We establish the general localness property of discretely homogeneous graphs and present examples of completable structures and their completions.

Keywords: automorphism group, definability, Svenonius theorem, definability lattice, reduct