Semigroups of tolerance relations

✍ Scribed by Boris M. Schein

• Publisher: Elsevier Science
• Year: 1987
• Tongue: English
• Weight: 673 KB
• Volume: 64
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(87)90194-4

✦ Synopsis

algebraic characterization of semigroups of tolerance relations and semigroups of symmetric binary relations.

Clearly, Mpo = MoMo, where Mp, Mo and Mpo are the 0, 1-matrices corresponding to p, o, and po, and the product of matrices is the Boolean one (i.e., 1 + 1 = 1). If p is a binary relation, then p-1 = {(a2, al): (al, a2) • p) denotes the converse of p. For example, p is symmetric preCisely when p-t= p. While a product of reflexive relations is always reflexive, the product of two partly reflexive, or symmetric, or tolerance relations need not have the same property. However, a set of symmetric relations (or relations of another type) may be closed under multiplication, in which case it forms a semigroup of symmetric relations. We find algebraic conditions characterizing such semigroups, i.e., necessary and sufficient conditions under which a semigroup is isomorphic to a semigroup of symmetric binary relations, or to a semigroup of (partial) tolerance