Izvestiya of Saratov University.

Mathematics. Mechanics. Informatics

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)

For citation:

Bredikhin D. A. On Semigroups of Relations with the Operation of Left and Right Rectangular Products. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2020, vol. 20, iss. 3, pp. 280-289. DOI: 10.18500/1816-9791-2020-20-3-280-289, EDN: FOREBX

This is an open access article distributed under the terms of Creative Commons Attribution 4.0 International License (CC-BY 4.0).
Published online: 
Full text:
(downloads: 409)
Article type: 

On Semigroups of Relations with the Operation of Left and Right Rectangular Products

Bredikhin Dmitry Aleksandrovich, Yuri Gagarin State Technical University of Saratov

A set of binary relations closed with respect to some collection of operations on relations forms an algebra called an algebra of relations. The class of all algebras (partially ordered algebras) isomorphic to algebras (partially ordered by set-theoretic inclusion ⊆ algebras) of relations with operations from Ω is denoted by R{Ω} (R{Ω, ⊆}). An operation on relations is called primitive-positive if it can be defined by a formula of the first-order predicate calculus containing only existential quantifiers and conjunctions in its prenex normal form. We consider algebras of relations with associative primitive-positive operations ∗ and ⋆, defined by the following formulas ρ ∗ σ = {(u, v) : (∃ s, t, w) (u, s) ∈ ρ ∧ (t, w) ∈ σ} и ρ ⋆ σ = {(u, v) : (∃ s, t, w) (s, t) ∈ ρ ∧ (w, v)  σ} respectively. The axiom systems for the classes R{∗}, R{∗, ⊆}, R{⋆}, R{⋆, ⊆}, and bases of quasi-identities and identities for quasi-varieties and varieties generated by these classes are found.

  1. Schein B. M. Relation algebras and function semigroups. Semigroup Forum, 1970, vol. 1, pp. 1–62.
  2. Boner P., Poschel F. R. Clones of operations on binary relations. Contributions to general algebra, 1991, vol. 7, pp. 50–70.
  3. Bredikhin D. A. On quasi-identities of algebras of relations with Diophantine operations. Sib. Math. J., 1997, vol. 38, pp. 23–33. DOI: https://doi.org/10.1007/BF02674896
  4. Bredikhin D. A. On algebras of relations with Diophantine operations. Dokl. Math., 1998, vol. 57, no. 3, pp. 435–436.
  5. Bredikhin D. A. On relation algebras with general superpositions. Algebraic Logic, 1998, vol. 54, pp. 111–124.
  6. Tarski A. On the calculus of relations. J. Symbolic Logic, 1941, vol. 6, pp. 73–89.
  7. Tarski A. Contributions to the theory of models, III. Proc. Konikl. Nederl. Akad. Wet., 1956, vol. 58, pp. 56–64.
  8. Lyndon R. C. The representation of relation algebras, II. Ann. Math., 1956, vol. 63, no. 2, pp. 294–307. DOI: https://doi.org/10.2307/1969611
  9. Wagner V. V. Restrictiv semigroups. Izv. Vyssh. Uchebn. Zaved. Mat., 1962, no. 6, pp. 19–27 (in Russian).