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) RR  R (26) RR  R (27) RR (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   R11  R21 1 (34)  R1 R2   R21 R11 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 hRU 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   R21 R11 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   u3u4 u1R1u3   u3R2u4  u4 R3u2   u3u4 u1R1u3  u3R2u4   u1R1u3  u4 R3u2   u4u3  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    u4u3 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 , DR1  U  DR1  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