On semigroups of relations with the operation of left and right rectangular products

D. A. Bredikhin

Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 20 (2020) no. 3, pp. 280-289

Résumé

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 $\subseteq$ algebras) of relations with operations from $\Omega$ is denoted by $\mathrm{R}\{\Omega\}$ ($R\{\Omega,\subseteq\}$). 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 $\ast$ and $\star$, defined by the following formulas $\rho\ast\sigma=\{(u,v): (\exists s,t,w) (u,s)\in \rho \wedge (t,w)\in \sigma\}$ and $\rho\star\sigma=\{(u,v): (\exists s,t,w) (s,t)\in \rho \wedge (w,v)\in \sigma\}$ respectively. The axiom systems for the classes $\mathrm{R}\{\ast\}$, $\mathrm{R}\{\ast,\subseteq\}$, $\mathrm{R}\{\star\}$, $\mathrm{R}\{\star,\subseteq\}$, and bases of quasi-identities and identities for quasi-varieties and varieties generated by these classes are found.