On Identities and Quasiidentities of Algebras of Relations
by
D.A. Bredikhin
Saratov State Technical University

In the investigation of algebras of relations, one of the most important problem is to study their identities and quasiidentities. For any set \Omega of positive operations [1] on binary relations, denote by R{\Omega} the class of algebras whose elements are binary relations and whose operations are members of \Omega. Any algebra from R{\Omega} can be considered as ordered by subset . Let L_\infty be a positive first-order logic [2] and L_n be a restriction of L_\infty on formulas with n individual variables. Denote by Eq_n{\Omega} (Qeq_n{\Omega}) the set of all identities (quasiidentities) of algebras from R{\Omega} that can be derived in L_n, and let V_n{\Omega} (Q_n{\Omega}) be the corresponding variety (quasivariety). The variety (quasivariety) V_n{\Omega, subset } (Q_n{\Omega, subset }) is defined analogously. We shall consider the operations of relation product o , relation inverse ^-1, intersection \cap , and identity relations \Delta. It follows from [3] that identities and quasiidentities of algebras with these operations can be expressed in L₃. Note that the case n=3 is more or less trivial and we suppose that n >= 4.

The class R{ o , ^-1, subset } was studied in [4, 5].

THEOREM 1. V₄{ o , ^-1, subset } = V_\infty{ o , ^-1, subset },     V₄{ o , ^-1, subset } is fininaly based;     an ordered algebra (A, ·, ^-1, <= ) belongs to V₄{ o , ^-1, subset } if and only if it satisfies following identities: (xy)z=x(yz) (1),     (x^-1)^-1=x (2),     (xy)^-1=y^-1x^-1 (3),     x <= xx^-1x (4).

V₄{ o , ^-1, subset } =/= Q₄{ o , ^-1, subset },     Q₄{ o , ^-1, subset } is fininaly based;     an ordered algebra (A, ·, ^-1, <= ) belongs to Q₄{ o , ^-1, subset } if and only if it satisfies (1)-(4) and x <= yz --> x <= yy^-1x.

The class R{ o , ^-1, \cap , \Delta} was introduced and studied in [6] (see also [7]).

THEOREM 2. Q₄{ o , ^-1, \cap , \Delta} = V₄{ o , ^-1, \cap , \Delta};    V₄{ o , ^-1, \cap , \Delta} is finitely based;     algebra (A, ·, ^-1, /\ , e) belongs to V₄{ o , ^-1, \cap , \Delta} if and only if it satisfies (1)-(3) and xe=ex=x,     x /\ x=x,     x /\ y=y /\ x,     (x /\ y) /\ z=x /\ (y /\ z),     (x /\ y)^-1=x^-1 /\ y^-1,     xy /\ x(y /\ z)=x(y /\ z),     x /\ yz=x /\ y(z /\ x^-1y).

Q₅{ o , ^-1, \cap , \Delta} does not contain in V_\infty{ o , ^-1, \cap , \Delta},     in particular,
Q₅{ o , ^-1, \cap , \Delta} =/= V₅{ o , ^-1, \cap , \Delta}.

REFERENCES: [1] Böner F., Pöschel R. Clones of operations on binary relations. Contributions to general algebras. - Wien, (7)1991, 50-70. [2] Rasiowa H., Sikorski R. The mathematics of metamathematics. Warszawa, 1963. [3] Tarski A. On the calculus of relations. J. Symbolic Logic 6(1941), no. 3, 73-89. [4] Schein B.M. Representation of involuted semigroups by binary relations. Fundamenta Math. (82)1974, no. 2, 121-141. [5] Bredikhin D.A. Representations of ordered involuted semigroups. Izv. vuzov. Matem. 1975, no. 7, 19-29. [6] Jónsson B. Representation of modular lattices and of relation algebras. Trans. Amer. Math. Soc. 92(1959), 449-464. [7] Andreka H., Bredikhin D.A. The equational theory of union-free algebras of relations. Algebra Univers. 33(1994), 516-532.

Date received: March 11, 2000