Introduction

Abstract theory of algebraic structures (sometimes called universal algebra) forms the basis for various applications [1][2][3][4][5][6][7][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 operationsaddition 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 operationsjoin and meetsatisfying 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. 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

        1 2 1 2 3 1 3 1 3 2 2 , | , , R R u u u u u R u u R      (1)

At first, we denote a universe as U and consider a power set of Cartesian square 2 UU  as a collection of binary relations on U . The traditional approach to studying binary relations leads to ordered semigroup

      1 2 1 2 , | , R u u u u 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)

1 R R R 10 I R R U U         (3

) Then, we can rewrite it in alternative form as antisymmetric low for the complement R as in equation ( 4)

    1 R ,| R R I u u u U     (4)

In this case and below we use the notations

      1 2 1 1 2 , | , R u u u u R   (5) 2. Algebraic structure R h Let's consider an algebraic structure   1 R R R R 2 ,    1 2 3 1 2 3 R R R R R R      (6)     1 2 3 1 2 3 R R R R R R     (7)

   

1 2 3 1 2 3 R R R R R R  (8) 1 2 2 1 R R R R    (9) 1 2 2 1 R R R R    (10) R 0 RR  (11) R 1 RR  (12) RR I R R I R  (13) RR 11 R  (14) RR 00 R  (15) R R R 0 0 0 RR  (16) R R R 1 1 1  (17)       1 2 3 1 2 1 3 R R R R R R R       (18)       1 2 3 1 2 1 3 R R R R R R R       (19)       1 2 3 1 2 1 3 R R R R R R R    (20)       2 3 1 2 1 3 1 R R R R R R R    (21)       1 2 3 1 2 1 3 R R R R R R R    (22)       2 3 1 2 1 3 1 R R R R R R R    (23)   1 1 2 1 R R R R    (24)   1 1 2 1 R R R R    (25) R R R  (26) R R R  (27) RR  (28) RR 10  (29) RR 01  (30) 12 R R R R    (31) 12 12 R R R R    (32)   1 11 1 2 1 2 R R R R      (33)   1 11 1 2 1 2 R R R R     (34)

 

1 11 1 2 2 1 R R R R    (35) 1 1 RR    (36) 1 2 1 2 2 1 2 1 R R R R R R R R        (37) 1 2 1 3 2 3 R R R R R R      (38) 1 2 1 3 2 3 R R R R R R      (39) 1 2 1 3 2 3 3 1 3 2 R R R R R R R R R R      (40) 12 12 R R R R   

(41) The typical algebraic structures we can obtain by restriction of structure   R U U h  are as follows:

The bounded lattices of binary relations

  1 R R R 2 , ,0 ,1 UU LO   and   2 R R R 2 , ,1 ,0 UU LO   ; The bounded monoids of binary relations   1 R R R 2 , , ,0 ,1 UU M     ,   2 R R R 2 , , ,0 ,1 UU M     ,   3 R R R 2 , , ,1 ,0 UU M     ,   4 R R R 2 , , ,1 ,0 UU M     and   R R R R 2 , , , ,0 ,1 UU MI   ; The bounded semirings (with multiplicative identity) of binary relations   1 R R R 2 , , , ,0 ,1 UU SR      ,   2 R R R 2 , , , ,1 ,0 UU SR      ,and  R R R 2 , , , ,0 , UU SR I     ;

The Boolean algebras of binary relations

  1 R R R 2 , , , ,0 ,1 UU B     and   2 R R R 2 , , , ,1 ,0 UU B     .

Dual semigroup toR S Let's consider a Boolean isomorphism   F R R  from 1 R B onto 2 R B . We define a binary operation • in accordance with duality principle       1 2 1 2 F R R F R F R  , i.e. we set         1 2 1 2 1 2 3 1 3 1 3 2 2 , | , , R R R R u u u u u R u u R       . (42) Note that   RR 01 F  ,   RR 10 F  ,   RR F I I  and moreover         1 2 1 2 1 2 3 1 3 1 3 2 2 , | , , R R R R u u u u u R u u R       (43)     1 2 3 1 2 3 R R R R R R  (44) RR I R R I R  (45) R R R 1 1 1 RR  (46) R R R 0 0 0  (47)       1 2 3 1 2 1 3 R R R R R R R    (48)       2 3 1 2 1 3 1 R R R R R R R    (49)       1 2 3 1 2 1 3 R R R R R R R    (50)       2 3 1 2 1 3 1 R R R R R R R    (51)   1 11 1 2 2 1 R R R R    (52) 1 2 1 3 2 3 3 1 3 2 R R R R R R R R R R     (      1 1 2 3 2 3 1 1 3 3 2 3 2 3 1 1 3 4 3 2 4 4 3 2 u R R R u u u R u u R R u u u R u u u R u u R u               3 4 1 1 3 3 2 4 4 3 2 3 4 1 1 3 3 2 4 1 1 3 4 3 2 u u u R u u R u u R u u u u R u u R u u R u u R u                    4 3 1 1 3 3 2 4 1 1 3 4 3 2 4 3 1 1 3 3 2 4 3 1 1 3 4 3 2 u u u R u u R u u R u u R u u u u R u u R u u u R u u R u                    4 1 1 2 4 3 1 1 3 4 3 2 4 1 1 2 4 4 3 2 1 1 2 4 3 1 1 3 u u R R u u u R u u R u u u R R u u R u u R R u u u R u                4 1 1 2 4 4 3 2 4 1 1 2 4 3 1 1 3 u u R R u u R u u u R R u u u R u            1 1 2 3 2 4 1 1 2 4 3 1 1 3 u R R R u u u R R u u u R u                  1 1 2 3 2 4 3 1 1 2 4 3 1 1 3 1 1 2 3 2 3 1 1 3 u R R R u u u u R R u u u R u u R R R u u u R u              1 1 1 2 3 2 1 R u R R R u u D    Let's denote a domain of 1 R as   1 1 3 1 1 3 | R D u u u R u U   

and then consider a binary relation

      1 1 1 R 1 2 1 2 R ,1 , | 1 R R R E D u u u D u U D U U U          . Now we can write       1 1 2 3 1 2 3 R ,1 R R R R R R E D  (54) Note that   11 1 1 R 2 3 1 1 3 3 R 2 3 1 1 3 2 1 2 1 R 2 1 1 ,1 RR u R u u u R u u u u u R u u U u D u U u E D u           

and so we obtain

    1 2 3 1 2 3 1 R 1 R R R R R R R  (55) Similarly, we get     2 3 1 2 3 1 R 1 1 R R R R R R R  (56)     1 2 3 1 2 3 1 R 0 R R R R R R R  (57)     2 3 1 2 3 1 R 1 0 R R R R R R R  (58)

In the latter, we have taken into account the following equalities:

  11 11 R R 1 1 , 1 RR E D U D R       11 R 1 R ,1 0 RR E D D U R      11 11 R R 1 1 , 0 RR E D U D R    

Extension of algebraic structure  1 R R R R R 2 ,    2 3 1 2 R 2 3 1 R R R R R R R      1 2 3 R 3 1 2 3 0 R R R R R R R



So we can rewrite (55)-(58) as:

IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018)

    1 2 3 1 2 3 1 R 1 R R R R R R R  (59)     1 2 3 R 3 1 2 3 0 R R R R R R  (60)     2 3 1 2 3 1 R 1 1 R R R R R R R  (61)     2 3 1 2 R 2 3 1 0 R R R R R R R  (62)

Obviously, for all binary relations

1 2 3 , , 2 UU R R R  

we have

    1 2 3 1 2 3 R R R R R R  (63)     2 3 1 2 3 1 R R R R R R  (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

    1 2 3 1 2 3 1 2 3 R R R R R R R R R  (65)     2 3 1 2 3 1 2 3 1 R R R R R R R R R



(66) Note that we won't find algebraic substructures of R H satisfying (65)-(66). Indeed, from ( 16), ( 17), ( 46), (47) we obtain Let's denote the collection of (partial) functions from U to U as

    R R R R R R R R 0 0 1 0 1 0 0 1    (67)     R R R R R R R R 0 1 1 0 1 0 1 1    (68)     R R R R R R R R 1 0 0 0 1 1 0 0    (69)     R R R R R R R R 1 1 0 0 1 1 1 0   (70)1 2 U U U U    . It's easy that   1 , , , ,0 U U U U U UI     is a bounded below submonoid of R M .

We want to prove that 1 U U  is closed under the dual operation .

At first, we suppose that U contains only one element. In this case

  1 R R 2 ,0 U U U UI   

, where R I is identity function and R 0 is empty function. So

1 U U  is closed under because 2 UU  is closed. Let now U contains more than one element. Suppose 1 2 1 , U R R U   , but 1 2 1 U R R U  

. Hence, there are 1 2 3

,,

u u u U  such that 23 uu  and             1 1 2 2 1 1 3 2 , , , , u u R u u R u u R u u R        for all uU  . However, 11 U RU  

and so there is no more than one U is a collection of total bijections from U to U .

0 uU  satisfying relation   1 0 1 , u u R  . Whence     2 3 2 2 3 2 ,, u u u u R u u R      for all   0 \ u U u    .

We assume U to be a two-element set and denote the cardinality of

  12 , U u u  as U . Obviously, 2 16 UU   , 1 9 U U   , 4 U U  , 0 2 U UU  . Note R1 1 U U   , R1 0 U U   , R 0 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. Table 1. A total amount of incompatibility of and .

1 2 3 ,, R R R W      1 2 3 1 2 3 R R R R R R      2 3 1 2 3 1 R R R R R R   R 2 \ 0 UU W  

706 from 3375 706 from 3375

  0 R R 0 ,1 U U  . R O R I R 0 R 1 R O R I R O R 0 R 1 R I R O R I R 0 R 1 R 0 R 0 R 0 R 0 R 0 R 1 R 1 R 1 R 0 R 1  0 R R 0 ,1 U U  . R O R I R 0 R 1 R O R O R I R 0 R 1 R I R I R O R 0 R 1 R 0 R 0 R 0 R 0 R 1 R 1 R 1 R 1 R 1 R 1 The cases of incompatibility on the set   0 R R 0 ,1 U U  are listed below apart from (67)-(70).     1 2 3 1 2 3 R R R R R R  :     R R R R R R R R 1 0 0 1 1 0 II        R R R R R R R R 1 0 0 1 1 0 OO        R R R R R R R R 0 1 0 1 0 1 II        R R R R R R R R 0 1 0 1 0 1 OO        2 3 1 2 3 1 R R R R R R  :     R R R R R R R R 0 1 0 1 0 1 II        R R R R R R R R 0 1 0 1 0 1 OO        R R R R R R R R 1 0 0 1 1 0 II        R R R R R R R R 1 0 0 1 1 0 OO    IV International      R 1 2 2 1 , , , O u u u u  ,       R 1 1 2 2

, , ,

I u u u u  , R 0 ,     1 1 1 , f u u  ,     2 1 2 , f u u  ,     3 2 1 , f u u  ,     4 2 3 , f u u  .

Cayley tables 4 and 5 describes the dual operations on the 1 F . Table 4. A Cayley table for on the set

1 F . R O R I R 0 1 f 2 f 3 f 4 f R O R I R O R 0 3 4 f 1 f 2 f R I R O R I R 0 1 f 2 f 3 f 4 f R 0 R 0 R 0 R 0 R 0 R 0 R 0 R 0 1 f 2 f 1 f R 0 1 f 2 f R 0 R 0 2 f 1 f 2 f R 0 R 0 R 0 1 f 2 f 3 f 4 f 3 f R 0 3 f 4 f R 0 R 0 4 f 3 f 4 f R 0 R 0 R 0 3 f f Table 5. A Cayley table for on the set 1 F . R O R I R 0 1 f 2 f 3 f 4 f R O R O R I R 0 1 f 2 f 3 f 4 f R I R I R O R 0 3 f 4 f 1 f 2 f R 0 R 0 R 0 R 0 R 0 R 0 R 0 R 0 1 f 1 f 2 f R 0 R 0 R 0 1 f 2 f 2 f 2 f 1 f R 0 1 f 2 f R 0 R 0 3 f 3 f 4 f R 0 R 0 R 0 3 f 4 f 4 f 4 f 3 f R 0 3 f 4 f R 0 R 0 It's easy to see that   1 1 R R R , , , , , ,0 , , F O I   is a bounded below compatible algebraic structure. Now let 2 U FU  be a set of total functions are listed as R O , R I ,       1 1 1 2 1 , , , g u u u u  ,       2 1 2 2 2

, , , g u u u u  .

Cayley tables 6 and 7 describes the dual operations on the 2 F . Table 6. A Cayley table for on the set

F . R O R I 1 g 2 g R O R I R O 1 g 2 g R I R O R I 1 g 2 g 1 g 1 g 1 g 2 g 1 g 1 g 2 g Table 7. A Cayley table for on the set 2 F . R O R I 1 g 2 g R O R O R I 1 g 2 g R I R I RO        1 2 3 1 2 3 1 2 3 1 2 3 R R R R R R R R R R R R    (71)         2 3 1 2 3 1 2 3 1 2 3 1 R R R R R R R R R R R R   (72)

Let's denote the sets of relations are complement of functions from Of cause, the list of examples can be continued.

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.