Generalized quasiorders: constructions and characterizations

Abstract

Abstract Quasiorders $$ \varrho \subseteq A^{2}$$ ϱ ⊆ A 2 have the property that an operation $$f:A^{n}\rightarrow A$$ f : A n → A preserves $$\varrho $$ ϱ if and only if each (unary) translation obtained from f is an endomorphism of $$\varrho $$ ϱ . Generalized quasiorders $$\varrho \subseteq A^{m}$$ ϱ ⊆ A m are generalizations of (binary) quasiorders sharing the same property. We show how new generalized quasiorders can be obtained from given ones using well-known algebraic constructions. Special generalized quasiorders, as generalized equivalences and (weak) generalized partial orders, are introduced, which extend the corresponding notions for binary relations. It turns out that generalized equivalences can be characterized by usual equivalence relations. Extending some known results of binary quasiorders, it is shown that generalized quasiorders can be “decomposed” uniquely into a (weak) generalized partial order and a generalized equivalence. Furthermore, generalized quasiorders of maximal clones determined by equivalence or partial order relations are investigated. If $$F={{\,\textrm{Pol}\,}}\varrho $$ F = Pol ϱ is a maximal clone and $$\varrho $$ ϱ an equivalence relation or a lattice order, then every relation in $${{\,\textrm{Inv}\,}}F$$ Inv F is a generalized quasiorder. Moreover, lattice orders are characterized by this property among all partial orders. Finally we prove that each term operation of a rectangular algebra gives rise to a generalized partial order. Some problems requiring further research are also highlighted.