On bases of identities for varieties of groupoids of relations

D. A. Bredikhin

Čebyševskij sbornik, Tome 19 (2018) no. 1, pp. 26-34.

Résumé

A set of binary relations closed with respect to some collection of operations on relations forms an algebra called an algebra of relations. Any such algebra can be considered as partially ordered by the relation of set-theoretic inclusion. For a given set $ \Omega $ of operations on relations, we denote by $ Var \{\Omega \} $ [$ Var \{\Omega, \subset \} $] the variety generated by the algebras [respectively ordered algebras] of relations with operations from $ \Omega $. Operations on relations, as a rule, are given by formulas of the first order predicate calculus. Such operations are called logical operations. An important class of logical operations is the class of Diophantine operations. An operation on relations is called Diophantine if it can be defined by a formula containing in its prenex normal form only existential quantifiers and conjunctions. We study algebras of relations with one binary Diophantine operation, i.e., groupoids of relations. As the operation being considered, the Diophantine operation $*$ that is defined in the following way: $ \rho \ast \sigma = \{(x, y) \in X \times X: (\exists z) (x, z) \in \rho \wedge (x, z) \in \sigma \}. $ The relation $ \rho \ast \sigma $ is the result of the cylindrification of the intersection $ \rho \cap \sigma $ of the binary relations $ \rho $ and $ \sigma $. In the paper, the finite bases of identities for varieties $Var\{\ast\}$ and $Var\{\ast, \subset \}$ are found. The groupoid $(A, \cdot) $ belongs to the variety $Var \{\ast \} $ if and only if it satisfies the identities: $xy=yx \: (1)$, $(xy)^2=xy\: (2)$, $(xy)y=xy\: (3)$, $x^2y^2=x^2y\: (4)$, $(x^2y^2)z=x^2(y^2z) \:(5).$ The partially ordered groupoid $ (A, \cdot, \leq) $ belongs to the variety $ Var\{\ast, \subset \} $ if and only if it satisfies the identities (1) - (5) and the identities: $ x \leq x^2 \: (6) $, $ xy \leq x^2 \:( 7)$. As a consequence, we also obtain a finite basis of identities for the variety $ Var \{\ast, \cup \} $.

Détail

Keywords: algebra of relations, diophantine operations, identities, varieties, groupoids, patially ordered groupoids.

Bibliographie

[1] Tarski A., “On the calculus of relations”, J. Symbolic Logic, 4 (1941), 73–89 | DOI | MR

[2] Tarski A., “Some methodological results concerning the calculus of relations”, J. Symbolic Logic, 18 (1953), 188–189 | MR

[3] Schein B. M., “Relation algebras and function semigroups”, Semigroup Forum, 1 (1970), 1–62 | DOI | MR | Zbl

[4] Jónsson B., “Varieties of relation algebras”, Algebra Universalis, 54 (1982), 273–299 | DOI | MR

[5] Andreka H., Bredikhin D. A., “The equational theory of union-free algebras of relations”, Algebra Universalis, 33 (1994), 516–532 | DOI | MR

[6] Bredikhin D. A., “Varietes of groupoids associated with involuted restrictive bisemigroups of binary relations”, Semigroup Forum, 44 (1992), 87–92 | DOI | MR | Zbl

[7] Bredikhin D. A., “The equational theory of algebras of relations with positive operations”, Izv. Vuzov. Matem., 1993, no. 3, 23–30 (in Russian)

[8] Bredikhin D. A., “On relation algebras with general superpositions”, Colloq. Math. Soc. J. Bolyai, 54 (1994), 111–124 | MR

[9] Bredikhin D. A., “On quasi-identities of algebras of relations with diophantine operations”, Siberian Mathematical Journal, 38:1 (1997), 23–33 | DOI | MR | Zbl

[10] Bredikhin D. A., “On algebras of relations with Diophantine operations”, Doklady Mathematics, 57:3 (1998), 435–436 | MR | Zbl

[11] Bredikhin D. A., “On varieties of groupoids of binary relations”, Izv. Sarat. Univ. N.S. Ser. Math. Mech. Inform., 13:1-1 (2013), 93–98 (in Russian)

[12] Bredikhin D. A., “On varieties of groupoids of relations with Diophantine Operations”, Izv. Sarat. Univ. N.S. Ser. Math. Mech. Inform., 13:1-2 (2013), 28–34 (in Russian)

[13] Bredikhin D. A., “On Varieties of Groupoids of Relations with Operation of Binary Cylindrification”, Algebra Universalis, 73 (2015), 43–52 | DOI | MR | Zbl

[14] Böner P., Pöschel F. R., “Clones of operations on binary relations”, Contributions to general Algebras, 7 (1991), 50–70 | MR

[15] Henkin L., Monk J. D., Tarski A., Cylindric Algebras, v. I, Studies in logic and the foundations of mathematics, North-Holland Publishing Company, Amsterdam–London, 1971, 508 pp. | MR | Zbl