On algebras of relations
Dmitry Aleksandrovich Bredikhin · Banach Center Publications · 1993
Throughout, by relation we mean a binary relation. Let Rel(X) be the set of all binary relations on the set X. An algebra of relations is a pair (Φ,Ω) where Ω is a set of operations on relations and Φ ⊂ Rel(X) is a set of relations closed under the operations of Ω. Each algebra of relations can be considered as ordered by the set-theoretic inclusion ⊂. Denote by M{Ω} the class of all algebras isomorphic to ones whose elements are relations and whose operations are members of Ω. The class M{Ω,⊂} is determined in the same way. We will consider the following operations on relations: relation product ◦, relation inverse −1, intersection ∩, diagonal relation ∆, and the unary operation ∗ determined as follows: %∗ = % ∩∆. The class M{◦,−1 ,∩, ∆} was introduced and characterized in [6]. It is not finitely axiomatizable [5]. The classes M{◦,−1 , ∆} and M{◦,−1 , ∆,⊂} were characterized in [1, 8]. The class M{◦,−1 , ∆} is not finitely axiomatizable [2]. In this paper we find a system of axioms for the class M{◦,−1 ,∗ , ∆,⊂} and use it to obtain some results about the class M{◦,−1 ,∩, ∆}. Theorem 1. An algebra (A, ·,−1 ,∗ , 1,≤) belongs to M{◦,−1 ,∗ , ∆,⊂} iff it satisfies the following conditions: (1) (A, ·,−1 , 1) is an involuted monoid , i.e. (xy)z = x(yz), 1x = x1 = x, (x−1)−1 = x, (xy)−1 = y−1x−1. (2) ≤ is an order relation and all operations are monotonic, i.e. x ≤ y implies xz ≤ yz, zx ≤ zy, x−1 ≤ y−1, x∗ ≤ y∗. (3) The following identities are satisfied :