The lattice of clones of self-dual operations collapsed

DOI10.1142/S0218196723500327MaRDI QIDQ6116396zbMATH OpenFDO

Authors Manuel Bodirsky, Albert Vucaj, D. N. Zhuk

Publication date 18 July 2023

Published in International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2109.01371

zbMATH Keywords

cloneclone homomorphismlinear Mal'cev conditionminor-preserving mapprimitive positive constructionthree-valued logic

Mathematics Subject Classification ID

Many-valued logic (03B50) Applications of universal algebra in computer science (08A70) Equational logic, Mal'tsev conditions (08B05)

Abstract: There are continuum many clones on a three-element set even if they are considered up to emph{homomorphic equivalence}. The clones we use to prove this fact are clones consisting of emph{self-dual operations}, i.e., operations that preserve the relation $(0,1),(1,2),(2,0)$. However, there are only countably many such clones when considered up to equivalence with respect to emph{minor-preserving maps} instead of clone homomorphisms. We give a full description of the set of clones of self-dual operations, ordered by the existence of minor-preserving maps. Our result can also be phrased as a statement about structures on a three-element set, ordered by primitive positive constructability, because there is a minor-preserving map from the polymorphism clone of a finite structure $mathfrakA$ to the polymorphism clone of a finite structure $mathfrakB$ if and only if there is a primitive positive construction of $mathfrakB$ in $mathfrakA$.

Cites work

• Bounded width problems and algebras
• Closed systems of functions and predicates
• Complexity of infinite-domain constraint satisfaction
• Conservative constraint satisfaction re-revisited
• Finitely related algebras in congruence distributive varieties have near unanimity terms
• Function Algebras on Finite Sets
• scientific article; zbMATH DE number 3162893 (Why is no real title available?)
• scientific article; zbMATH DE number 3853164 (Why is no real title available?)
• scientific article; zbMATH DE number 3815607 (Why is no real title available?)
• scientific article; zbMATH DE number 3972930 (Why is no real title available?)
• scientific article; zbMATH DE number 3664909 (Why is no real title available?)
• scientific article; zbMATH DE number 3231913 (Why is no real title available?)
• scientific article; zbMATH DE number 3094257 (Why is no real title available?)
• Minimal clones -- a minicourse
• On the number of finite algebraic structures
• On the number of finite Mal'tsev algebras
• The lattice of all clones of self-dual functions in three-valued logic
• The lattice of interpretability types of varieties
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• The wonderland of reflections

Cited in

(3)

• Submaximal clones over a three-element set up to minor-equivalence
• Multisorted Boolean clones determined by binary relations up to minion homomorphisms
• On when the union of two algebraic sets is algebraic

This page was built for publication: The lattice of clones of self-dual operations collapsed

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6116396)