Chebyshevskii Sbornik
General information
Latest issue

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Chebyshevskii Sb.:

Personal entry:
Save password
Forgotten password?

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
Received: 07.02.2014

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
\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

Linking options:

    SHARE: FaceBook Twitter Livejournal

    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Number of views:
    This page:169
    Full text:71

    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021