On varieties of algebras of relations with operation of double cylindrofication

D. A. Bredikhin

Čebyševskij sbornik, Tome 15 (2014) no. 1, pp. 55-64.

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 first mathematician who treated algebras of relations from the point of view of universal algebra was Alfred Tarski. In the investigation of algebras of relations, one of the most important directions is the study of those of their properties which can be expressed by identities. This leads us to the consideration of varieties generated by classes of algebras of relations. For any set $\Omega$ of operations on binary relations, let $R\{\Omega\}$ denote the class of all algebras isomprphic to ones whose elements are binary relations and whose operations are members of $\Omega$. Let $Var\{\Omega\}$ be the variety generated by $R\{\Omega\}$. As a rule, operations on relations are defined by formulas of the first-order predicate calculus. These operations are called logical. One of the most important classes of logical operations on relations is the class of Diophantine operations (in other terminology — primitive-positive operations). An operation on relations is called Diophantine if it can be defined by a formula containing in its prenex normal form only existential quantifiers and conjunctions. A Diophantine operation is called atomic if it can be defined by a first order formula containing in its prenex normal form only existential quantifiers. It is clear that such formulas contain only one atomic subformula. Hence atomic operations are unary operations. There exist nine atomic operations (excepting identical). We concentrate our attention on the Diophantine operation of relation product $\circ$ and on the atomic operation of double cylindrification $ \nabla$ that are defined as follows. For any relations $\rho$ and $\sigma$ on $U$, put $$ \rho\circ\sigma=\{(u, v):\, (\exists w) (u, w)\in \rho (w, v)\in \sigma\},\quad \nabla(\rho)=\{(u,v):\,(\exists w,z) (w,z)\in \rho\}. $$ In the paper, the bases of identities for the variety $Var\{\circ, \nabla \}$ is found: an algebra $(A, \cdot, {}^\ast)$ of the type $(2,1)$ belongs to the variety $Var\{\circ, \nabla \}$ if and only if it satisfies the identities: $(xy)z=x(yz)$, $x^{\ast\ast}=x^\ast$, $(x^\ast)^2=x^\ast$, $x^\ast y^\ast=y^\ast x^\ast$, $x^\ast(xy)^\ast=(xy)^\ast y^\ast=(xy)^\ast$, $(xy^\ast z)^\ast=x^\ast y^\ast z^\ast=x^\ast yz$, $xyz^\ast=xyx^\ast z^\ast$, $x^\ast z=x^\ast z^\ast yz$.

Détail

Keywords: algebra of relations, varieties, basis of identities, operations cylindrification.

Bibliographie

[1] Tarski A., “On the calculus of relations”, J. Symbolic Logic, 6 (1941), 73–89 | DOI | MR

[2] Tarski A., “Some methodological results concerning the calculus of relations”, J. Symbolic Logic, 18 (1953), 188–189

[3] Andréka H., Németi I., Sain I., “Algebraic Logic”, Handbook of Philosophical Logic, v. 2, second edition, Kluwer Academic publishers, 2001, 133–247 | MR | Zbl

[4] Schein B. M., “Relation algebras and function semigroups”, Semigroup Forum, 1 (1970), 1–62 | DOI | MR | Zbl

[5] Bredikhin D. A., “O kvazitozhdestvakh algebr otnoshenii s diofantovymi operatsiyami”, Sibirskii mat. zhurn., 1997, no. 1, 29–41 | MR | Zbl

[6] Bredikhin D. A., “Ob algebrakh otnoshenii s diofantovymi operatsiyami”, Doklady Rossiiskoi Akademii Nauk, 360 (1998), 594–595 | MR | Zbl

[7] Böner F., Pöschel F. R., “Clones of operations on binary relations”, Contributions to general algebras, 7 (1991), 50–70

[8] Bredikhin D. A., “Ekvatsionalnaya teoriya algebr otnoshenii s pozitivnymi operatsiyami”, Izvestiya vuzov. Matematika, 1993, no. 3, 23–30 | MR | Zbl

[9] Henkin L., Monk J. D., Tarski A., Cylindric algeras, North-Holland, Amsterdam, 1971, 311 pp. | MR | Zbl

[10] Kuhn S., “The domino relations: flattening a two-dimensional logic”, Journal of Philosophical Logic, 18 (1989), 173–195 | DOI | MR | Zbl

[11] Venema Y., Many-dimensional modal logic, Universiteit van Amsterdam, Amsterdam, 1989, 178 pp.

[12] Schein B. M., “Representation of involuted semigroups by binary relations”, Fundamenta Math., 82 (1974), 121–141 | MR | Zbl

[13] Bredikhin D. A., “On the varieties generated by partially ordered involuted semigroups of binary relations”, Contributions to genera algebra, 13 (2001), 70–77 | MR

[14] Andreka H., Bredikhin D. A., “The equational theory of union-free algebras of relations”, Alg. Univers., 33 (1994), 516–532 | DOI | MR

[15] Bredikhin D. A., “On varieties of partial ordered semigroups of relations with operations of cylindrification”, Izv. Sarat. Univ. N.S. Ser. Math. Mech. Inform., 9:3 (2009), 3–7