Abstract
We establish a criterion for a structure M on an infinite domain to have the Galois closure \({{\,\textrm{InvAut}\,}}(M)\) (the set all relations on the domain of M that are invariant to all automorphisms of M) defined via infinite Boolean combinations of infinite (constructed by infinite conjunction) existential relations from M. Based on this approach, we present criteria for quantifier elimination in M via finite partial automorphisms of all existential relations from M, as well as criteria for (weak) homogeneity of M. Then we describe properties of M with a countable signature, for which the set of all relations, expressed by quantifier-fee formulas over M, is weakly inductive, that is, this set is closed under any infinitary intersection of the same arity relations. It is shown that the last condition is equivalent: for every \(n \ge 1\) there are only finitely many isomorphism types for substructures of M generated by n elements. In case of algebras with a countable signature such type can be defined by the set of all solutions of a finite system of equations and inequalities produced by n-ary terms over those algebras. Next, we prove that for a finite M with a finite signature the problem of the description of any relation from \({{\,\textrm{InvAut}\,}}(M)\) via the first order formula over M, which expresses it, is algorithmically solvable.
Similar content being viewed by others
References
Bodnarchuk, V.G., Kaluzhnin, L.A., Kotov, V.N., Romov, B.A.: Galois theory for post algebras, I–II. Cybernetics 5, 243–252 and 531–539 (1969)
Hodges, W.: A Shorter Model Theory. Cambridge University Press, Cambridge (1997)
Karp, C.R.: Languages with Expressions of Infinite Length. North-Holland, Amsterdam (1964)
Romov, B.A.: Local characteristics of Post algebras, I. Cybernetics 12, 338–345 (1976)
Romov, B.A.: Local characteristics of Post algebras, II. Cybernetics 13, 11–20 (1977)
Romov, B.A.: Homogeneous and strictly homogeneous criteria for partial structures. Discrete Appl. Math. 157, 699–709 (2009)
Romov, B.A.: Positive primitive structures. J. Multi-Valued Logic Soft Comput. 17, 581–589 (2011)
Romov, B.A.: Languages with finite string of quantifiers on uncountable structures. J. Multi-Valued Logic Soft Comput. 38, 581–589 (2022)
Scott, D.: Logic with denumerably long formulas and finite string of quantifiers. In: Addison, J., et al. (eds.) Theory of Models, pp. 329–341. North-Holland, Amsterdam (1964)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Presented by R. Pöschel.
To Victor Bodnarchuk, Leo Kaluzhnin, and Victor Kotov, my co-authors from the paper [1] (Kiev, 1969).
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Romov, B.A. Existential relations on infinite structures. Algebra Univers. 84, 24 (2023). https://doi.org/10.1007/s00012-023-00819-3
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s00012-023-00819-3
Keywords
- Finite partial automorphism
- Weak inductivity
- Language with finite string of quantifiers
- Existential relation
- Galois closure