Chebyshevskii Sbornik
 RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Chebyshevskii Sb.: Year: Volume: Issue: Page: Find

 Chebyshevskii Sb., 2014, Volume 15, Issue 1, Pages 55–64 (Mi cheb325)

On varieties of algebras of relations with operation of double cylindrofication

D. A. Bredikhin

Saratov State Technical University

Abstract: 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$.

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

Full text: PDF file (277 kB)
References: PDF file   HTML file
UDC: 501.1

Citation: D. A. Bredikhin, “On varieties of algebras of relations with operation of double cylindrofication”, Chebyshevskii Sb., 15:1 (2014), 55–64

Citation in format AMSBIB
\Bibitem{Bre14} \by D.~A.~Bredikhin \paper On varieties of algebras of relations with operation of double cylindrofication \jour Chebyshevskii Sb. \yr 2014 \vol 15 \issue 1 \pages 55--64 \mathnet{http://mi.mathnet.ru/cheb325}