=Paper=
{{Paper
|id=Vol-2212/paper41
|storemode=property
|title=Dual ordered structures of binary relations
|pdfUrl=https://ceur-ws.org/Vol-2212/paper41.pdf
|volume=Vol-2212
|authors=Victor Tsvetov
}}
==Dual ordered structures of binary relations ==
https://ceur-ws.org/Vol-2212/paper41.pdf
Dual ordered structures of binary relations
V P Tsvetov1
1
Samara National Research University, Moskovskoe shosse 34, Samara, Russia, 443086
Abstract. The theory of ordered structures like a (lattice) ordered semigroups is applied to
graphs and automatons as well as to coding, programming and artificial intelligence. In this
paper an algebraic structure on an underlying set of binary relations is considered. The
structure includes the operations of Boolean algebra, inverse and composition. It is defined a
dual semigroup to the binary relations ordered semigroup, and then the general properties of
dual operations are studied.
1. Introduction
Abstract theory of algebraic structures (sometimes called universal algebra) forms the basis for various
applications [1-8]. Semigroups and lattices are the simplest structures but not the least ones.
Let’s recall some definitions:
The semigroup is a set with single binary operation satisfying associative low. A semigroup with
neutral (identity) element is called a monoid;
The semiring is a set with couple of binary operations – addition and multiplication - satisfying
associative lows. There are neutral elements for both of them and addition is commutative. Also
multiplication distributes over addition and multiplication by zero annihilates semiring;
The lattice (as an algebraic structure) is a set with pair of binary operations – join and meet -
satisfying associative lows, commutative lows, and absorption lows. A distributive lattice is a lattice in
which the operations of join and meet distribute over each other. A bounded lattice is a lattice with
neutral elements. The lattice's bottom is a neutral element for the join operation and the lattice's top is
a neutral element for the meet operation;
The lattice (as a poset) is a partial ordered set such that each finite-elements subset has supremum
(join) and infimum (meet). A bounded lattice is a lattice with bottom and top elements;
The ordered semigroup is a semigroup together with a partial order that is compatible with the
semigroup operation i.e. u, v, w u v w u w v u w v w . The bounded semigroup is an
ordered semigroup with bottom and top elements.
It’s well known that any ordered semigroup is isomorphic to a subsemigroup of binary relations
ordered by subset relation. In this paper we deal with a left composition of binary relation as a
semigroup operation, i.e. we set
R1 R2 u1 , u2 | u3 u1 , u3 R1 u3 , u2 R2 (1)
At first, we denote a universe as U and consider a power set of Cartesian square 2U U as a
collection of binary relations on U . The traditional approach to studying binary relations leads to
ordered semigroup SR 2U U , , and bounded distributive lattice LR 2U U , , . In this
way we don’t take into account a complement operation
IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018)
Data Science
V P Tsvetov
R u1 , u2 | u1 , u2 R (2)
However, it’s very convenient to use a complement element. For example, we can write the
trichotomy low for relation R in several forms. First, we can write it as in equation (3)
I R R R 1 1R U U 0R (3)
Then, we can rewrite it in alternative form as antisymmetric low for the complement R as in equation
(4)
R R 1 I R u, u | u U (4)
In this case and below we use the notations 1R , 0 R and I R for complete relation, empty relation
and identity relation respectively. Note that 1R and 0 R are top and bottom elements for lattice LR .
Also we denote the inverse relation of R as
R 1 u2 , u1 | u1 , u2 R (5)
2. Algebraic structure hR
Let’s consider an algebraic structure hR 2U U , , , , ,1 , ,0R ,1R , I R . It’s easy to prove
properties (6)-(41):
R1 R2 R3 R1 R2 R3 (6)
R1 R2 R3 R1 R2 R3 (7)
R1 R2 R3 R1 R2 R3 (8)
R1 R2 R2 R1 (9)
R1 R2 R2 R1 (10)
0R R R (11)
1R R R (12)
IR R R IR R (13)
1R R 1R (14)
0R R 0R (15)
0R R R 0R 0 R (16)
1R 1R 1R (17)
R1 R2 R3 R1 R2 R1 R3 (18)
R1 R2 R3 R1 R2 R1 R3 (19)
R1 R2 R3 R1 R2 R1 R3 (20)
R2 R3 R1 R2 R1 R3 R1 (21)
R1 R2 R3 R1 R2 R1 R3 (22)
R2 R3 R1 R2 R1 R3 R1 (23)
R1 R1 R2 R1 (24)
R1 R1 R2 R1 (25)
RR R (26)
RR R (27)
RR (28)
1R 0R (29)
0R 1R (30)
IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018) 305
Data Science
V P Tsvetov
R1 R2 R1 R 2 (31)
R1 R2 R1 R 2 (32)
R1 R2 R R
1 1 1
1 2 (33)
R1 R2 R11 R21
1
(34)
R1 R2 R21 R11
1
(35)
1
R 1 R (36)
R1 R2 R1 R2 R2 R1 R2 R1 (37)
R1 R2 R1 R3 R2 R3 (38)
R1 R2 R1 R3 R2 R3 (39)
R1 R2 R1 R3 R2 R3 R3 R1 R3 R2 (40)
R1 R2 R1 R2 (41)
The typical algebraic structures we can obtain by restriction of structure hRU U are as follows:
The bounded lattices of binary relations LOR1 2U U , ,0R ,1R and LOR2 2U U , ,1R ,0R
;
The bounded monoids of binary relations M 2 1
R
U U
, , ,0R ,1R , M 2
2
R
U U
, , ,0R ,1R ,
M R3 2U U , , ,1R ,0R , M R4 2U U , , ,1R ,0R and M R 2U U , , , I R ,0R ,1R
;
The bounded semirings (with multiplicative identity) of binary relations
SRR 2 , , , ,0R ,1R , SRR 2 , , , ,1R ,0R , and SRR 2 , , , ,0R , I R
1 U U 2 U U U U
;
The Boolean algebras of binary relations
BR1 2U U , , , ,0R ,1R and
BR2 2U U , , , ,1R ,0R .
3. Dual semigroup to S R
Let’s consider a Boolean isomorphism F R R from BR1 onto BR2 . We define a binary operation •
in accordance with duality principle F R1 R2 F R1 F R2 , i.e. we set
R1 R2 R1 R2 u1 , u2 | u3 u1 , u3 R1 u3 , u2 R2 . (42)
Note that F 0R 1R , F 1R 0R , F I R I R and moreover
R1 R2 R1 R2 u1 , u2 | u3 u1 , u3 R1 u3 , u2 R2 (43)
R1 R2 R3 R1 R2 R3 (44)
IR R R IR R (45)
1R R R 1R 1R (46)
0R 0R 0R (47)
R1 R2 R3 R1 R2 R1 R3 (48)
R2 R3 R1 R2 R1 R3 R1 (49)
R1 R2 R3 R1 R2 R1 R3 (50)
R2 R3 R1 R2 R1 R3 R1 (51)
R1 R2 R21 R11
1
(52)
R1 R2 R1 R3 R2 R3 R3 R1 R3 R2 (53)
IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018) 306
Data Science
V P Tsvetov
By our construction semigroup S R is isomorphic to semigroup S R 2U U , , as well as
monoid MR and semiring SRR are isomorphic to
M R 2U U , , , I R ,1R ,0R and
SR R 2U U , , , ,1R , I R respectively. In such cases, we’ll say that the algebraic structures are
dual.
Now we use the previous definitions to argue the following logical consequences:
u1R1 R2 R3 u2 u3 u1R1u3 u3 R2 R3 u2 u3 u1R1u3 u4 u3R2u4 u4 R3u2
u3u4 u1R1u3 u3R2u4 u4 R3u2 u3u4 u1R1u3 u3R2u4 u1R1u3 u4 R3u2
u4u3 u1R1u3 u3R2u4 u1R1u3 u4 R3u2 u4 u3 u1R1u3 u3R2u4 u3 u1R1u3 u4 R3u2
u4 u1R1 R2u4 u3 u1R1u3 u4 R3u2 u4 u1R1 R2u4 u4 R3u2 u1R1 R2u4 u3 u1R1u3
u4 u1R1 R2u4 u4 R3u2 u4 u1R1 R2u4 u3 u1R1u3
u1R1 R2 R3 u2 u4 u1R1 R2u4 u3 u1R1u3
u1R1 R2 R3 u2 u4u3 u1R1 R2u4 u3 u1R1u3 u1R1 R2 R3 u2 u3 u1R1u3
u1R1 R2 R3 u2 u1 DR 1
Let’s denote a domain of R1 as DR u1 | u3 u1R1u3 U and then consider a binary relation
1
E DR ,1R u1 , u2 | u1 DR u2 U DR U 1R U U . Now we can write
1 1 1
R1 R2 R3 R1 R2 R3 E DR ,1R (54) 1
Note that
u1R1 1R u2 u3 u1R1u3 u31R u2 u3 u1R1u3 u2 U u1 DR1 u2 U u1E DR1 ,1R u2
and so we obtain
R1 R2 R3 R1 R2 R3 R1 1R (55)
Similarly, we get
R2 R3 R1 R2 R3 R1 1R R1 (56)
R1 R2 R3 R1 R2 R3 R1 0R (57)
R2 R3 R1 R2 R3 R1 0R R1 (58)
In the latter, we have taken into account the following equalities:
E 1R , DR1 U DR1 1R R1
1 1
U R 0
E D ,1R D
R1 R1 1 R
E 1 , D U D 0 R
R 1 1 R 1
R1 R1
4. Extension of algebraic structure hR
At first, we denote OR I R and then we consider H R 2U U , , , , , ,1 , ,0R ,1R , OR , I R as an
extension of algebraic structure hR . It is clear that all of the properties (6)-(58) are true for structure
HR .
Let’s rewrite (57)-(58) in the form
R2 R3 R1 R2 0R R2 R3 R1
R1 R2 R3 0R R3 R1 R2 R3
So we can rewrite (55)-(58) as:
IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018) 307
Data Science
V P Tsvetov
R1 R2 R3 R1 R2 R3 R1 1R (59)
R1 R2 R3 0R R3 R1 R2 R3 (60)
R2 R3 R1 R2 R3 R1 1R R1 (61)
R2 R3 R1 R2 0R R2 R3 R1 (62)
U U
Obviously, for all binary relations R1 , R2 , R3 2 we have
R1 R2 R3 R1 R2 R3 (63)
R2 R3 R1 R2 R3 R1 (64)
This is immediate from the inclusions (59)-(62).
Properties like the (55)-(58), (63)-(64) we’ll call the laws of semi-compatibility. Now we are
interested in cases of compatibility (low) of dual operation with each other
R1 R2 R3 R1 R2 R3 R1 R2 R3 (65)
R2 R3 R1 R2 R3 R1 R2 R3 R1 (66)
Note that we won’t find algebraic substructures of H R satisfying (65)-(66). Indeed, from (16),
(17), (46), (47) we obtain
0R 0R 1R 0R 1R 0R 0R 1R (67)
0R 1R 1R 0R 1R 0R 1R 1R (68)
1R 0R 0R 0R 1R 1R 0R 0R (69)
1R 1R 0R 0R 1R 1R 1R 0R (70)
Hence, we have to restrict structure H R to find algebraic substructures satisfying (65)-(66) and we’ll
call them compatible (sub)structures. Let’s consider H R without 0 R or 1R .
We are studying the simplest cases of subsets of 2U U as an underlying set for the operations from
H R below.
Let’s denote the collection of (partial) functions from U to U as U U1 2U U . It’s easy that
U U1 , , , IU U ,0U U is a bounded below submonoid of M R .
We want to prove that U U1 is closed under the dual operation .
At first, we suppose that U contains only one element. In this case U U1 2U U I R ,0R , where
I R is identity function and 0 R is empty function. So U U1 is closed under because 2U U is closed.
Let now U contains more than one element. Suppose R1 , R2 U U1 , but R1 R2 U U1 . Hence, there
are u1 , u2 , u3 U such that u2 u3 and u1 , u R1 u, u2 R2 u1 , u R1 u, u3 R2 for all
u U . However, R1 U U1 and so there is no more than one u0 U satisfying relation u1 , u0 R1 .
Whence u2 u3 u, u2 R2 u, u3 R2 for all u U \ u0 . The latter is in contradiction with
R2 U U1 .
The proof is complete.
Let’s consider the scale of sets U0U U U U U1 , where U U is a collection of total functions and
U 0U is a collection of total bijections from U to U .
We assume U to be a two-element set and denote the cardinality of U u1 , u2 as U . Obviously,
2U U 16 , U U1 9 , U U 4 , U 0U U 2 . Note 1R U U1 , 0R U U1 , 0R U U .
We have simulated some interesting cases of algebraic substructures to check irregularities in (65)-
(66). Table 1 contains statistics on the incompatibility of dual operations.
IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018) 308
Data Science
V P Tsvetov
Table 1. A total amount of incompatibility of and .
R1 , R2 , R3 W R1 R2 R3 R1 R2 R3 R2 R3 R1 R2 R3 R1
W 2U U \ 0R 706 from 3375 706 from 3375
W 2U U \ 1R 706 from 3375 706 from 3375
W U U1 90 from 729 20 from 729
W U U
0 from 64 0 from 64
W U 0R
U
10 from 75 4 from 75
W U U 1R 4 from 75 10 from 75
W U U
0 0 from 8 0 from 8
W U 0R
U
0 0 from 27 0 from 27
W U0U 1R 0 from 27 0 from 27
Cayley tables 2 and 3 describes the dual operations on the set U0U 0R ,1R .
Table 2. A Cayley table for on the set U0U 0R ,1R .
OR IR 0R 1R
OR IR OR 0R 1R
IR OR IR 0R 1R
0R 0R 0R 0R 0R
1R 1R 1R 0R 1R
Table 3. A Cayley table for on the set U0U 0R ,1R .
OR IR 0R 1R
OR OR IR 0R 1R
IR IR OR 0R 1R
0R 0R 0R 0R 1R
1R 1R 1R 1R 1R
The cases of incompatibility on the set U0U 0R ,1R are listed below apart from (67)-(70).
R1 R2 R3 R1 R2 R3 :
1R I R 0R 0R 1R 1R I R 0R
1R OR 0R 0R 1R 1R OR 0R
0R I R 1R 0R 1R 0R I R 1R
0R OR 1R 0R 1R 0R OR 1R
R2 R3 R1 R2 R3 R1 :
0R I R 1R 0R 1R 0R I R 1R
0R OR 1R 0R 1R 0R OR 1R
1R I R 0R 0R 1R 1R I R 0R
1R OR 0R 0R 1R 1R OR 0R
IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018) 309
Data Science
V P Tsvetov
It’s easy to see that U 0U , , OR and U 0U , , I R are abelian groups. Moreover,
U0U 0R , , , ,1 , ,0R , OR , I R is a bounded below compatible algebraic structure and
U0U 1R , , , ,1 , ,1R , OR , I R is a bounded above compatible algebraic structure.
Let’s give other examples.
Let F1 U U1 be a set of partial and total functions are listed as OR u1 , u2 , u2 , u1 ,
I R u1 , u1 , u2 , u2 , 0R , f1 u1 , u1 , f 2 u1 , u2 , f 3 u2 , u1 , f 4 u2 , u3 .
Cayley tables 4 and 5 describes the dual operations on the F1 .
Table 4. A Cayley table for on the set F1 .
OR IR 0R f1 f2 f3 f4
OR IR OR 0R f3 f4 f1 f2
IR OR IR 0R f1 f2 f3 f4
0R 0R 0R 0R 0R 0R 0R 0R
f1 f2 f1 0R f1 f2 0R 0R
f2 f1 f2 0R 0R 0R f1 f2
f3 f4 f3 0R f3 f4 0R 0R
f4 f3 f4 0R 0R 0R f3 f4
Table 5. A Cayley table for on the set F1 .
OR IR 0R f1 f2 f3 f4
OR OR IR 0R f1 f2 f3 f4
IR IR OR 0R f3 f4 f1 f2
0R 0R 0R 0R 0R 0R 0R 0R
f1 f1 f2 0R 0R 0R f1 f2
f2 f2 f1 0R f1 f2 0R 0R
f3 f3 f4 0R 0R 0R f3 f4
f4 f4 f3 0R f3 f4 0R 0R
It’s easy to see that F1 , , , ,1 , ,0R , OR , I R is a bounded below compatible algebraic
structure.
Now let F2 U U be a set of total functions are listed as OR , I R , g1 u1 , u1 , u2 , u1 ,
g2 u1 , u2 , u2 , u2 .
Cayley tables 6 and 7 describes the dual operations on the F2 .
Table 6. A Cayley table for on the set F2 .
OR IR g1 g2
OR IR OR g1 g2
IR OR IR g1 g2
g1 g1 g1 g2
g1 g1 g2
IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018) 310
Data Science
V P Tsvetov
Table 7. A Cayley table for on the set F2 .
OR IR g1 g2
OR OR IR g1 g2
IR IR OR g1 g2
g1 g1 g2 g1 g2
g2 g2 g1 g1 g2
In this case F2 , , , ,1 , , OR , I R is unbounded compatible algebraic structure. Taking into
account (42)-(43) we can write
R1 R2 R3 R1 R2 R3 R1 R2 R3 R1 R2 R3 (71)
R2 R3 R1 R2 R3 R1 R2 R3 R1 R2 R3 R1 (72)
Let’s denote the sets of relations are complement of functions from F1 and F2 as
F1 OR , I R ,1R , f1 , f 2 , f 3 , f 4 and F O , I , g , g . In accordance with (71)-(72) we get ordered
2 R R 1 2
(not bounded and not lattice) compatible algebraic structures F1 , , , ,1 , ,1R , OR , I R and
F2 , , , , OR , I R .
Of cause, the list of examples can be continued.
5. Conclusion
We have studied non-traditional algebraic structures on the underlying set of binary relations. Starting
from left composition, inclusion and Boolean isomorphism we defined dual ordered semigroups. Then
we extended them to the more general ordered algebraic structure with a couple of dual operations.
We have proved that these operations satisfy the semi-compatibility laws. This is notable and
important fact. We paid special attention to the algebraic substructures satisfying the compatibility
laws. So we have considered interesting examples of compatible algebraic structures.
The results will be useful for graphs and automatons as well as for coding, programming and
artificial intelligence.
References
[1] Clifford A H and Preston G B 1961 The Algebraic Theory of Semigroups Mathematical
Surveys and Monographs 7(1)
[2] Clifford A H and Preston G B 1967 The Algebraic Theory of Semigroups Mathematical
Surveys and Monographs 7(2)
[3] Birkhoff G 1967 Lattice Theory (Providence RI: American Mathematical Society)
[4] Fuchs L 1963 Partially Ordered Algebraic Systems (Oxford: Pergamon Press)
[5] Ershov A P 1982 Abstract computability in algebraic systems Proc. Int. Symp. Algorithms in
Modern Mathematics and its Applications (Novosibirsk: Computing Center of the Siberian
Branch of the USSR Academy of Sciences) 2 194-299
[6] Chernov V M 2015 Quasiparallel algorithm for error-free convolution computation using
reduced Mersenne-Lucas codes Computer Optics 39(2) 241-248 DOI: 10.18287/
0134-2452-2015-39-2-241-248
[7] Chernov V M 2018 Calculation of Fourier-Galois transforms in reduced binary number systems
Computer Optics 42(3) 495-500 DOI: 10.18287/ 0134-2452-2018-42-3-495-500
[8] Makhortov S D and Shurlin M D 2013 LP-Structures analysis: substantiation of refactoring in
object-oriented programming Automation and Remote Control 74(7) 1211-1217
IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018) 311