On bases of identities for varieties of groupoids of relations

Abstract

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 Ω of operations on relations, we denote by V  ar{Ω} [V ar{Ω,⊂}] the variety generated by the algebras [respectively ordered algebras] of relations with operations from Ω. 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: ρ*σ = {( x,у) ∈ X × X : (∃z)( x, z) ∈ ρ∧( x, z) ∈ σ}. The relation ρ*σ is the result of the cylindrification of the intersection ρ∩σ of the binary relations ρ and σ. In the paper, the finite bases of identities for varieties V ar{*}  and V ar{*,⊂}. are found. The groupoid (A,·) belongs to the variety V ar {*} if and only if it satisfies the identities: xy = уx (1), (xу)2 = xу (2), (xу)у = xу (3), x 2у 2 = x 2у (4), (x 2у 2)z = x 2(у 2z) (5). The partially ordered groupoid (A,·,≤) belongs to the variety V ar{*,⊂}if and only if it satisfies the identities (1) - (5) and the identities: х ≤ x2 (6), xу ≤ x 2 (7). As a consequence, we also obtain a finite basis of identities for the variety V ar{*,∪}.