|
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.
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
Linking options:
https://www.mathnet.ru/eng/cheb325 https://www.mathnet.ru/eng/cheb/v15/i1/p55
|
Statistics & downloads: |
Abstract page: | 273 | Full-text PDF : | 102 | References: | 64 |
|