Dual ordered structures of binary relations

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.

-

R1 ( 1 ) ordered semigroup SR  2UU , , 

and bounded distributive lattice LR  2UU ,, . In this way we don’t take into account a complement operation

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 )

IR 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  IR u,u|uU ( 4 )

In this case and below we use the notations 1R , 0R and IR for complete relation, empty relation and identity relation respectively. Note that 1R and 0R 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,IR  . It’s easy to prove properties ( 6 )-(41):

R1 R2 R3  R1 R2R3 R1 R2 R3  R1 R2R3

R1 R2 R3  R1 R2 R3

R1 R2  R2 R1 R1 R2  R2 R1 0R R  R 1R R  R IR R  R IR  R 1R R 1R 0R R  0R 0R R  R 0R  0R

1R 1R 1R R1 R2 R3  R1 R2R1 R3 R1 R2 R3  R1 R2R1 R3

R1 R2 R3  R1 R2R1 R 

3 R2 R3 R1  R2 R1R3 R1 R1 R2 R3  R1 R2R1 R 

3 R2 R3 R1  R2 R1R3 R1

R1 R1 R2  R1 R1 R1 R2  R1

RR  R RR  R

R  R 1R  0R 0R 1R IV International Conference on "Information Technologyand Nanotechnology" (ITNT-2018) ( 6 ) ( 7 ) ( 8 ) (9) (10) (11) (12) (13) (14) (15) (16) (17) (18) (19) (20) (21) (22) (23) (24) (25) (26) (27) (28) (29) (30)

R1 R2  R1 R2

R1 R2  R1 R2 R1 R21  R11 R21 R1 R21  R11 R21 R1 R21  R21 R11

R1  R1 R1  R2  R1 R2  R2  R1 R2  R1

R1  R2  R1 R3  R2 R3

R1  R2  R1 R3  R2 R3 R1  R2  R1 R3  R2 R3 R3 R1  R3 R2

R1  R2  R1  R2 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 MR1  2UU,,,0R,1R  , MR2  2UU,,,0R,1R  , MR3  2UU,,,1R,0R  , MR4  2UU,,,1R,0R  and MR  2UU, ,,IR,0R,1R  ;

The bounded semirings (with multiplicative identity) of binary relations SRR1  2UU,,,,0R,1R  , SRR2  2UU,,,,1R,0R  , and SRR  2UU,, ,,0R,IR  ;

The Boolean algebras of binary relations BR1  2UU,,, ,0R,1R  and BR2  2UU,,, ,1R,0R  .

3. Dual semigroup to SR

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.

Note that F0R  1R , F1R   0R , F IR   IR and moreover

R1 R2  R1 R2 u1,u2|u3 u1,u3R1 u3,u2R2

R1 R2 R3  R1 R2 R3

IR R  R IR  R 1R R  R 1R 1R

0R 0R  0R R1 R2 R3  R1 R2R1 R3 R2 R3 R1  R2 R1R3 R1 R1 R2 R3 R1 R2R1 R3 R2 R3 R1 R2 R1R3 R1

R1 R21  R21 R11

R1  R2  R1 R3  R2 R3 R3 R1  R3 R2 IV International Conferenceon "Information Technologyand Nanotechnology" (ITNT-2018) (31) (32) (33) (34) (35) (36) (37) (38) (39) (40) (41) (42) (43) (44) (45) (46) (47) (48) (49) (50) (51) (52) (53)

Note that

and so we obtain

Similarly, we get

By our construction semigroup SR is isomorphic to semigroup SR  2UU, , as well as monoid MR and semiring SRR are isomorphic to MR  2UU, ,,IR,1R,0R  and SRR  2UU,, ,,1R,IR  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 u4R3u2 u3u4 u1R1u3 u3R2u4 u4R3u2 u3u4 u1R1u3 u3R2u4u1R1u3 u4R3u2 u4u3 u1R1u3 u3R2u4u1R1u3 u4R3u2 u4 u3 u1R1u3 u3R2u4u3 u1R1u3 u4R3u2 u4 u1R1 R2u4 u3 u1R1u3 u4R3u2 u4 u1R1 R2u4 u4R3u2u1R1 R2u4 u3 u1R1u3 u4 u1R1 R2u4 u4R3u2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DR1 

Let’s denote a domain of R1 as DR1 u1 |u3 u1R1u3U and then consider a binary relation EDR1,1R  u1,u2|u1 DR1 u2 U DR1 U 1R U U . Now we can write

R1 R2 R3  R1 R2 R3 EDR1,1R  u1R1 1Ru2  u3 u1R1u3 u31Ru2  u3 u1R1u3 u2 U u1 DR1 u2 U u1EDR1,1R u2 R1 R2 R3  R1 R2 R3 R1 1R R2 R3 R1  R2 R3 R11R R1 R1 R2 R3  R1 R2 R3 R1 0R

E1R,DR11 U DR11 1R R1 EDR1 ,1R  DR U  R1 0R

1 E1R,DR 1 U DR 1  0R R1 1 1 (54) (55) (56) (57) (58) R2 R3 R1  R2 R3 R10R R1

In the latter, we have taken into account the following equalities: 4. Extension of algebraic structure hR At first, we denote OR  IR and then we consider HR  2UU,,, , , ,1,,0R,1R,OR,IR  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:  R2 R3  R1  R2 0R  R  R3 2 Obviously, for all binary relations R1, R2 , R3  2UU we have

R1  R2 R3    R1

R2  R3  R1 1R R1  R2 R3   0R R3   R1  R2 R3  R1  R  R3 2

R1  1R

R2  R3

R1 R 

1 R1  R2 R3    R1

R2  R3

R 

1

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  IR ,0R , where I R is identity function and 0R 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  R  u,u2   R2   u1,u  R  u,u3   R  for all 1 1 2 u U . However, R1 UU1 and so there is no more than one u0 U satisfying relation u1,u0   R . 1 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  UU  UU1 , where U U is a collection of total functions and U0U 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 , UU  4 , U0U  U  2 . Note 1R UU1 , 0R UU1 , 0R UU .

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. (59) (60) (61) (62) (63) (67) (68) DataScience VPTsvetov

It’s easy to see that

U0U , ,OR  and

U0U , , IR  are abelian groups.

Moreover,

U0U 0R ,, , ,1 , ,0R ,OR , IR  is a bounded below compatible algebraic structure and U0U 1R ,, , ,1 , ,1R ,OR , IR  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  ,

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 F .

2 is a bounded below compatible algebraic

In this case

F ,, , ,1 , ,OR , IR  is unbounded compatible algebraic structure. Taking into 2 account (42)-(43) we can write

R1  R2 R3    R1 R2  R3  R1 R2 R3   R1 R2  R3  R2 R3  R  R2 R3 R   R2 R3  R1  R2 R3 R1 

1 1 Let’s denote the sets of relations are complement of functions from F  OR , IR ,1R , f1, f2, f3, f4 and F2  OR , IR , g1, g2. In accordance with (71)-(72) we get ordered 1 (not bounded and not lattice) compatible algebraic structures F ,, , ,1 , ,1R ,OR , IR  1 and (71) (72)

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