Share This Article:

Generating Sets of the Complete Semigroups of Binary Relations Defined by Semilattices of the Class Σ2 (X,4)

Abstract Full-Text HTML XML Download Download as PDF (Size:432KB) PP. 17-27
DOI: 10.4236/am.2018.91002    491 Downloads   799 Views   Citations

ABSTRACT

In this paper, we have studied generating sets of the complete semigroups defined by X-semilattices of the class Σ2(X, 4).

1. Introduction

Let X be an arbitrary nonempty set and D be a nonempty set of subsets of the set X. If D is closed under the union, then D is called a complete X-semilattice of unions. The union of all elements of the set D is denoted by the symbol D .

Let B X be the set of all binary relations on X. It is well known that B X is a semigroup.

Let f be an arbitrary mapping from X into D. Then we denote a binary relation

α f = x X ( { x } × f ( x ) ) for each f. The set of all such binary relations is denoted

by B X ( D ) . It is easy to prove that B X ( D ) is a semigroup with respect to the product operation of binary relations. This semigroup B X ( D ) is called a complete semigroup of binary relations defined by an X-semilattice of unions D. This structure was comprehensively investigated in Diasamidze [1] and [2] . We assume that t , y X , Y X , α B X , T D and D D . Then we denote following sets

y α = { x X | y α x } , Y α = y Y y α ,

V ( D , α ) = { Y α | Y D } , X = { Y | Y X } Y T α = { y X | y α = T } , V ( X , α ) = { Y α | Y X } D t = { Z D | t Z } , B 0 = { α B X ( D ) | V ( X , α ) = D }

Let D = { D , Z 1 , Z 2 , , Z m 1 } be finite X-semilattice of unions and C ( D ) = { P 0 , P 1 , P 2 , , P m 1 } be the family of pairwise nonintersecting subsets of X. If φ = ( D Z 1 Z m 1 P 0 P 1 P m 1 ) is a mapping from D on C ( D ) , then the equalities D = P 0 P 1 P 2 P m 1 and Z i = P 0 T D \ D Z φ ( T ) are valid. These equalities are called formal.

Let D be a complete X-semilattice of unions α B X . Then a representation

of a binary relation α of the form α = T V ( X , α ) ( Y T α × T ) is called quasinormal.

Let P 0 , P 1 , P 2 , , P m 1 be parameters in the formal equalities, β B X ( D ) , β ¯ 2

be mapping from X \ D to D . Then β ¯ = i = 0 m 1 ( P i × t P i t β ) t X \ D ( { t } × β ¯ 2 ( t ) )

is called subquasinormal represantation of β . It can be easily seen that the following statements are true.

a) β ¯ B X ( D ) .

b) i = 0 m 1 ( P i × t P i t β ) β and β = β ¯ for some β ¯ 2 .

c) Subquasinormal represantation of β is quasinormal.

d) β ¯ 1 = ( P 0 P 1 P m 1 P 0 β ¯ P 1 β ¯ P m 1 β ¯ ) is mapping from C ( D ) on D { } .

β ¯ 1 and β ¯ 2 are respectively called normal and complement mappings for β .

Let α B X ( D ) . If α δ β for all δ , β B X ( D ) \ { α } then α is called external element. Every element of the set B 0 = { α B X ( D ) | V ( X , α ) = D } is an external element of B X ( D ) .

Theorem 1. [1] Let X be a finite set and α , β B X ( D ) . If β ¯ is sub- quasinormal representation of β then α β = α β ¯ .

Corollary 1. [1] Let B ˜ B ˜ B X ( D ) . If α δ β ¯ for α B ˜ , δ B ˜ \ { α } , β ¯ B ˜ \ { α } and subquasinormal representation of β B ˜ \ { α } then α δ β .

It is known that the set of all external elements is subset of any generating set of B X ( D ) in [3] .

2. Results

In this work by symbol Σ 2.2 ( X ,4 ) we denote all semilattices D = { Z 3 , Z 2 , Z 1 , D } of the class Σ 2 ( X ,4 ) which the intersection of minimal elements Z 3 Z 2 = . This semilattices graphic is given in Figure 1. By using formal equalities, we have Z 3 Z 2 = P 0 = . So, the formal equalities of the semilattice D has a form

Figure 1. Graphic of semilattice D = { Z 3 , Z 2 , Z 1 , D } which the intersection of minimal elements Z 3 Z 2 = .

D = P 1 P 2 P 3 Z 1 = P 2 P 3 Z 2 = P 1 P 3 Z 3 = P 2 (1)

Let δ , β ¯ B X ( D ) . If quasinormal representation of binary relation δ has a form δ = ( Y 3 δ × Z 3 ) ( Y 2 δ × Z 2 ) ( Y 1 δ × Z 1 ) ( Y 0 δ × D ) then

δ β ¯ = ( Y 3 δ × Z 3 β ¯ ) ( Y 2 δ × Z 2 β ¯ ) ( Y 1 δ × Z 1 β ¯ ) ( Y 0 δ × D β ¯ )

We denote the set

B 32 = { α B X ( D ) | V ( X , α ) = { Z 3 , Z 2 , D } } B 21 = { α B X ( D ) | V ( X , α ) = { Z 2 , Z 1 , D } } B 31 = { α B X ( D ) | V ( X , α ) = { Z 3 , Z 1 } } B ˜ 32 = { α B 32 | α = ( Y 3 α × Z 3 ) ( Y 2 α × Z 2 ) , Y 3 α Y 2 α = X , Y 3 α Y 2 α = } B ˜ 21 = { α B 21 | α = ( Y 2 α × Z 2 ) ( Y 1 α × Z 1 ) , Y 2 α Y 1 α = X , Y 2 α Y 1 α = }

It is easy to see that

B 0 B 32 = B 0 B 21 = B 0 B 31 = B 21 B 32 = B 31 B 32 = B 21 B 31 = .

Lemma 2. Let D = { Z 3 , Z 2 , Z 1 , D } Σ 2.2 ( X , 4 ) . Then following statements are true for the sets B 0 , B 32 , B ˜ 32 .

a) If α = ( Y 3 α × Z 3 ) ( Y 1 α × Z 1 ) ( Y 0 α × D ) for some Y 3 α , Y 1 α , Y 0 α , then α is product of some elements of the set B 0 .

b) If β 0 = ( Z 3 × Z 3 ) ( ( X \ Z 3 ) × Z 2 ) , then ( B 0 β 0 ) B ˜ 32 = B 32 .

c) If σ 1 = ( Z 2 × Z 2 ) ( ( X \ Z 2 ) × Z 1 ) , then ( B 0 σ 1 ) B ˜ 21 = B 21 .

d) If σ 1 = ( Z 2 × Z 2 ) ( ( X \ Z 2 ) × Z 1 ) , then B 32 σ 1 = B 21 .

e) If σ 0 = ( Z 3 × Z 3 ) ( ( X \ Z 3 ) × Z 1 ) , then B 32 σ 0 = B 31 .

f) Every element of the set B 32 is product of elements of the set B 0 B ˜ 32 .

g) Every element of the set B 21 is product of elements of the set B 0 B ˜ 32 { σ 1 } .

Proof. It will be enough to show only a, b and g. The rest can be similarly seen.

a. Let α = ( Y 3 α × Z 3 ) ( Y 1 α × Z 1 ) ( Y 0 α × D ) for some Y 3 α , Y 1 α , Y 0 α { } , δ , β ¯ B 0 . Then quasinormal representation of δ has a form

δ = ( Y 3 δ × Z 3 ) ( Y 2 δ × Z 2 ) ( Y 1 δ × Z 1 ) ( Y 0 δ × D )

where Y 3 δ , Y 1 δ , Y 0 δ { } . We suppose that

β ¯ = ( P 2 × Z 3 ) ( P 1 × Z 2 ) ( P 3 × Z 1 ) t X \ D ( { t } × β ¯ 2 ( t ) )

where β ¯ 1 = ( P 1 P 2 P 3 Z 2 Z 3 Z 1 ) is normal mapping for β ¯ and β ¯ 2 is com-

plement mapping of the set X \ D on the set D ˜ . So, β ¯ B 0 since V ( X , β ¯ ) = D . From the equalities (2.1) and definition of β ¯

Z 3 β ¯ = P 2 β ¯ = Z 3 Z 2 β ¯ = ( P 1 P 3 ) β ¯ = P 1 β ¯ P 3 β ¯ = Z 2 Z 1 = D Z 1 β ¯ = ( P 2 P 3 ) β ¯ = P 2 β ¯ P 3 β ¯ = Z 3 Z 1 = Z 1 D β ¯ = ( P 1 P 2 P 3 ) β ¯ = P 1 β ¯ P 2 β ¯ P 3 β ¯ = Z 2 D Z 1 = D

δ β ¯ = ( Y 3 δ × Z 3 β ¯ ) ( Y 2 δ × Z 2 β ¯ ) ( Y 1 δ × Z 1 β ¯ ) ( Y 0 δ × D β ¯ ) = ( Y 3 δ × D ) ( Y 2 δ × D ) ( Y 1 δ × D ) ( Y 0 δ × D ) = ( Y 3 δ × D ) ( Y 1 δ × D ) ( ( Y 2 δ Y 0 δ ) × D ) = α .

b. Let α B 0 β 0 B ˜ 32 . Then α B 0 β 0 or α B ˜ 32 . If α B 0 β 0 then α = δ β 0 for some δ B 0 . In this case we have

δ = ( Y 3 δ × Z 3 ) ( Y 2 δ × Z 2 ) ( Y 1 δ × Z 1 ) ( Y 0 δ × D )

where Y 3 δ , Y 1 δ , Y 0 δ { } . Also

α = δ β 0 = ( Y 3 δ × Z 3 β 0 ) ( Y 2 δ × Z 2 β 0 ) ( Y 1 δ × Z 1 β 0 ) ( Y 0 δ × D β 0 ) = ( Y 3 δ × Z 3 ) ( Y 2 δ × Z 2 ) ( Y 1 δ × Z 1 ) ( Y 0 δ × D ) = ( Y 3 δ × Z 3 ) ( Y 2 δ × Z 2 ) ( ( Y 1 δ Y 0 δ ) × D ) B 32 \ B ˜ 32

is satisfied. So, we have ( B 0 β 0 ) B ˜ 32 B 32 . On the other hand, if α B ˜ 32 B 32 then ( B 0 β 0 ) B ˜ 32 B 32 is satisfied. Conversely, if α B 32 then quasinormal representation of α has a form

α = ( Y 3 α × Z 3 ) ( Y 2 α × Z 2 ) ( Y 0 α × D )

where Y 3 α , Y 2 α , Y 0 α { } or Y 3 α , Y 2 α { } and Y 0 α = . We suppose that Y 3 α , Y 2 α { } . In this case, we have

δ β 0 = ( Y 3 δ × Z 3 β 0 ) ( Y 2 δ × Z 2 β 0 ) ( Y 0 δ × Z 1 β 0 ) = ( Y 3 δ × Z 3 ) ( Y 2 δ × Z 2 ) ( Y 0 δ × D ) = α

for δ = ( Y 3 α × Z 3 ) ( Y 2 α × Z 2 ) ( Y 0 α × Z 1 ) B 0 . So, we have B 32 ( B 0 β 0 ) B ˜ 32 . Now suppose that Y 3 α , Y 2 α { } and Y 0 α = . In this case, we have α B ˜ 32 ( B 0 β 0 ) B ˜ 32 . So, ( B 0 β 0 ) B ˜ 32 = B 32 .

g. From the statement c, we have that ( B 0 β 0 ) B ˜ 32 = B 32 where β 0 B ˜ 32 by definition of β 0 . Thus, every element of the set B 32 is product of elements of the set B 0 B ˜ 32 .

Lemma 3. Let D = { Z 3 , Z 2 , Z 1 , D } Σ 2.2 ( X , 4 ) . If | X \ D | 1 then the following statements are true.

a) If α = X × D then α is product of elements of the set B 0 .

b) If α = X × Z 1 then α is product of elements of the set B 0 .

c) If α = ( Y 3 α × Z 3 ) ( Y 1 α × Z 1 ) for some Y 3 α , Y 1 α , then α is product of elements of the B 0 .

d) If α = ( Y 3 α × Z 3 ) ( Y 0 α × D ) for some Y 3 α , Y 0 α , then α is product of elements of the B 0 .

e) If α = ( Y 2 α × Z 2 ) ( Y 0 α × D ) for some Y 2 α , Y 0 α , then α is product of elements of the B 0 .

f) If α = ( Y 1 α × Z 1 ) ( Y 0 α × D ) for some Y 1 α , Y 0 α , then α is product of elements of the B 0 .

Proof. c. Let quasinormal representation of α has a form α = ( Y 3 α × Z 3 ) ( Y 1 α × Z 1 ) where Y 3 δ , Y 1 δ { } . By definition of the semilattice D, | X | 3 . We suppose that | Y 3 α | 1 and | Y 1 α | 2 . In this case, we suppose that

β ¯ = ( P 2 × Z 3 ) ( ( P 1 P 3 ) × Z 1 ) t X \ D ( { t } × β ¯ 2 ( t ) )

where β ¯ 1 = ( P 1 P 2 P 3 Z 1 Z 3 Z 1 ) is normal mapping for β ¯ and β ¯ 2 is comple-

ment mapping of the set X × D on the set D ˜ \ { Z 3 , Z 1 } = { Z 2 } (by suppose | X \ D | 1 ). So, β ¯ B 0 since V ( X , β ¯ ) = D . Also, Y 3 δ = Y 3 α and Y 2 δ Y 1 δ Y 0 δ = Y 1 δ since | Y 3 δ | 1 , | Y 2 δ | 1 , | Y 1 δ | 1 , | Y 0 δ | 0 . From the equalities (2.1) and definition of β ¯ we obtain that

Z 3 β ¯ = P 2 β ¯ = Z 3 Z 2 β ¯ = ( P 1 P 3 ) β ¯ = P 1 β ¯ P 3 β ¯ = Z 1 Z 1 = Z 1 Z 1 β ¯ = ( P 2 P 3 ) β ¯ = P 2 β ¯ P 3 β ¯ = Z 3 Z 1 = Z 1 D β ¯ = ( P 1 P 2 P 3 ) β ¯ = P 1 β ¯ P 2 β ¯ P 3 β ¯ = Z 1 Z 3 Z 1 = Z 1

δ β ¯ = ( Y 3 δ × Z 3 β ¯ ) ( Y 2 δ × Z 2 β ¯ ) ( Y 1 δ × Z 1 β ¯ ) ( Y 0 δ × D β ¯ ) = ( Y 3 δ × Z 3 ) ( Y 2 δ × Z 1 ) ( Y 1 δ × Z 1 ) ( Y 0 δ × Z 1 ) = ( Y 3 δ × Z 3 ) ( ( Y 2 δ Y 1 δ Y 0 δ ) × Z 1 ) = α

Now, we suppose that | Y 3 α | 2 and | Y 1 α | 1 . In this case, we suppose that

β ¯ = ( ( P 2 P 3 ) × Z 3 ) ( P 1 × Z 1 ) t X \ D ( { t } × β ¯ 2 ( t ) )

where β ¯ 1 = ( P 1 P 2 P 3 Z 1 Z 3 Z 3 ) is normal mapping for β ¯ and β ¯ 2 is com-

plement mapping of the set X × D on the set D ˜ \ { Z 3 , Z 1 } = { Z 2 } (by suppose | X \ D | 1 ). So, β ¯ B 0 since V ( X , β ¯ ) = D . Also, Y 3 δ Y 1 δ = Y 3 α and Y 2 δ Y 0 δ = Y 1 α since | Y 3 δ | 1, | Y 2 δ | 1, | Y 1 δ | 1, | Y 0 δ | 0 . From the equalities (2.1) and definition of β ¯ we obtain that

Z 3 β ¯ = P 2 β ¯ = Z 3 Z 2 β ¯ = ( P 1 P 3 ) β ¯ = P 1 β ¯ P 3 β ¯ = Z 1 Z 3 = Z 1 Z 1 β ¯ = ( P 2 P 3 ) β ¯ = P 2 β ¯ P 3 β ¯ = Z 3 Z 3 = Z 3 D β ¯ = ( P 1 P 2 P 3 ) β ¯ = P 1 β ¯ P 2 β ¯ P 3 β ¯ = Z 1 Z 3 Z 3 = Z 1

δ β ¯ = ( Y 3 δ × Z 3 β ¯ ) ( Y 2 δ × Z 2 β ¯ ) ( Y 1 δ × Z 1 β ¯ ) ( Y 0 δ × D β ¯ ) = ( Y 3 δ × Z 3 ) ( Y 2 δ × Z 1 ) ( Y 1 δ × Z 3 ) ( Y 0 δ × Z 1 ) = ( ( Y 3 δ Y 1 δ ) × Z 3 ) ( ( Y 2 δ Y 0 δ ) × Z 1 ) = α

Lemma 4. Let D = { Z 3 , Z 2 , Z 1 , D } Σ 2.2 ( X , 4 ) , σ 0 = ( Z 3 × Z 3 ) ( ( X \ Z 3 ) × Z 1 ) and σ 1 = ( Z 2 × Z 2 ) ( ( X \ Z 2 ) × Z 1 ) . If X = D then the following statements are true

a) If α = ( Y 3 α × Z 3 ) ( Y 0 α × D ) for some Y 3 α , Y 0 α { } , then α is product of elements of the B 0 B 32 .

b) If α = ( Y 2 α × Z 2 ) ( Y 0 α × D ) for some Y 2 α , Y 0 α { } , then α is product of elements of the B 32 { σ 1 } .

c) If α = ( Y 1 α × Z 1 ) ( Y 0 α × D ) for some Y 1 α , Y 0 α { } , then α is product of elements of the B 32 { σ 0 , σ 1 } .

Proof. First, remark that Z 3 σ 0 = Z 3 , Z 2 σ 0 = D σ 0 = Z 1 , Z 3 σ 1 = Z 1 , Z 2 σ 1 = Z 2 , D σ 1 = D .

a. Let α = ( Y 3 α × Z 3 ) ( Y 0 α × D ) for some Y 3 α , Y 0 α . In this case, we suppose that

δ = ( Y 3 δ × Z 3 ) ( Y 2 δ × Z 2 ) ( Y 0 δ × D )

and

β 1 = ( Z 3 × Z 3 ) ( ( Z 1 \ Z 3 ) × Z 1 ) ( ( X \ Z 1 ) × D )

where Y 3 δ , Y 2 δ { } . It is easy to see that δ B 32 and β 1 is generating by elements of the B 0 by statement b of Lemma 2. Also, Y 3 δ = Y 3 α and Y 2 δ Y 0 δ = Y 0 α since Z 3 β ¯ = Z 3 , Z 2 β ¯ = D β ¯ = D and | Y 3 δ | 1, | Y 2 δ | 1, | Y 0 δ | 0 . So, α is product of elements of the B 0 B 32 . □

Lemma 5. Let

D = { Z 3 , Z 2 , Z 1 , D } Σ 2.2 ( X , 4 )

and

σ 1 = ( Z 2 × Z 2 ) ( ( X \ Z 2 ) × Z 1 ) .

If | X \ D | 1 then S 1 = B 0 B ˜ 32 { σ 1 } is an irreducible generating set for the semigroup B X ( D ) .

Proof. First, we must prove that every element of B X ( D ) is product of elements of S 1 . Let α B X ( D ) and

α = ( Y 3 α × Z 3 ) ( Y 2 α × Z 2 ) ( Y 1 α × Z 1 ) ( Y 0 α × D )

where Y 3 α Y 2 α Y 1 α Y 0 α = X and Y 3 α Y 2 α = , ( 0 i j 3 ) . We suppose

that | V ( X , α ) | = 1 . Then we have V ( X , α ) { { Z 3 } , { Z 2 } , { Z 1 } , { D } } . If

V ( X , α ) { { Z 3 } , { Z 2 } , { Z 1 } } then α = X × Z 3 or α = X × Z 2 or α = X × Z 1 . Quasinormal representations of δ , β 1 , β 2 and β 3 has form

δ = ( Y 3 δ × Z 3 ) ( Y 2 δ × Z 2 ) ( Y 1 δ × Z 1 ) ( Y 0 δ × D ) β 1 = ( D × Z 3 ) ( ( X \ D ) × Z 2 ) β 2 = ( D × Z 2 ) ( ( X \ D ) × Z 1 ) β 3 = ( D × Z 1 ) ( ( X \ D ) × Z 2 )

where Y 3 δ , Y 2 δ , Y 1 δ { } . So, δ B 0 , β 1 B ˜ 32 and β 2 , β 3 B 21 since | X \ D | 1 . From the definition of δ , β 1 , β 2 and β 3 we obtain that

δ β 1 = ( Y 3 δ × Z 3 β 1 ) ( Y 2 δ × Z 2 β 1 ) ( Y 1 δ × Z 1 β 1 ) ( Y 0 δ × D β 1 ) = ( Y 3 δ × Z 3 ) ( Y 2 δ × Z 3 ) ( Y 1 δ × Z 3 ) ( Y 0 δ × Z 3 ) = ( Y 3 δ Y 2 δ Y 1 δ Y 0 δ ) × Z 3 = X × Z 3

δ β 2 = ( Y 3 δ × Z 3 β 2 ) ( Y 2 δ × Z 2 β 2 ) ( Y 1 δ × Z 1 β 2 ) ( Y 0 δ × D β 2 ) = ( Y 3 δ × Z 2 ) ( Y 2 δ × Z 2 ) ( Y 1 δ × Z 2 ) ( Y 0 δ × Z 2 ) = ( Y 3 δ Y 2 δ Y 1 δ Y 0 δ ) × Z 2 = X × Z 2

δ β 3 = ( Y 3 δ × Z 3 β 3 ) ( Y 2 δ × Z 2 β 3 ) ( Y 1 δ × Z 1 β 3 ) ( Y 0 δ × D β 3 ) = ( Y 3 δ × Z 1 ) ( Y 2 δ × Z 1 ) ( Y 1 δ × Z 1 ) ( Y 0 δ × Z 1 ) = ( Y 3 δ Y 2 δ Y 1 δ Y 0 δ ) × Z 1 = X × Z 1

That means, X × Z 1 , X × Z 2 and X × Z 3 are generated by B 0 B ˜ 32 , B 0 B 21 and B 0 B 21 respectively. By using statement g and h of Lemma 3, we have X × Z 1 , X × Z 2 and X × Z 3 are generated by B 0 B ˜ 32 { σ 1 } . On the other hand, if V ( X , α ) = { D } then α = X × D By using statement a of Lemma 3, we have α is product of some elemets of B 0 .

So, S 1 is generating set for the semigroup B X ( D ) . Now, we must prove that S 1 = B 0 B ˜ 32 { σ 1 } is irreducible. Let α S 1 .

If α B 0 then α σ τ for all σ , τ B X ( D ) \ { α } from Lemma 2. So, α σ τ for all σ , τ S 1 \ { α } . That means, α B 0 .

If α B ˜ 32 then the quasinormal representation of α has form α = ( Y 3 α × Z 3 ) ( Y 2 α × Z 2 ) for some Y 3 α , Y 2 α . Let α = δ β for some δ , β S 1 \ { α } .

We suppose that δ B 0 \ { α } and β S 1 \ { α } . By definition of B 0 , quasinormal representation of δ has form

δ = ( Y 3 δ × Z 3 ) ( Y 2 δ × Z 2 ) ( Y 1 δ × Z 1 ) ( Y 0 δ × D )

where Y 3 δ , Y 2 δ , Y 1 δ { } . By using Z 3 Z 1 D and Z 2 D we have Z 3 β and Z 2 β are minimal elements of the semilattice { Z 3 β , Z 2 β , Z 1 β , D β } . Also, we have

( Y 3 α × Z 3 ) ( Y 2 α × Z 2 ) = α = δ β = ( Y 3 δ × Z 3 β ) ( Y 2 δ × Z 2 β ) ( Y 1 δ × Z 1 β ) ( Y 0 δ × D β )

Since Z 3 and Z 2 are minimal elements of the semilattice { Z 3 , Z 2 , D } , this equality is possible only if Z 3 = Z 3 β , Z 2 = Z 2 β or Z 3 = Z 2 β , Z 2 = Z 3 β . By using formal equalities and P 3 β , P 2 β , P 1 β D , we obtain

Z 3 = Z 3 β = P 2 β and Z 2 = Z 2 β = P 1 β = P 3 β Z 2 = Z 3 β = P 2 β and Z 3 = Z 2 β = P 1 β = P 3 β

respectively. Let Z 3 = P 2 β and Z 2 = P 1 β = P 3 β . If β ¯ is sub-quasinormal representation of β then δ β = δ β ¯ and

β ¯ = ( ( P 1 P 3 ) × Z 2 ) ( P 2 × Z 3 ) t X \ D ( { t } × β ¯ 2 ( t ) )

where β ¯ 1 = ( P 1 P 2 P 3 Z 2 Z 3 Z 2 ) is normal mapping for β ¯ and β ¯ 2 is com-

plement mapping of the set X × D on the set D ˜ = { Z 3 , Z 2 , Z 1 } . From formal equalities, we obtain

β ¯ = ( Z 2 × Z 2 ) ( Z 3 × Z 3 ) t X \ D ( { t } × β ¯ 2 ( t ) ) S 1 \ { α }

and by using Z 1 Z 2 , Z 3 Z 2 = D and | Y 1 δ Y 0 δ | 1 , we have

δ β ¯ = ( Y 3 δ × Z 3 β ¯ ) ( Y 2 δ × Z 2 β ¯ ) ( Y 1 δ × Z 1 β ¯ ) ( Y 0 δ × D β ¯ ) = ( Y 3 δ × Z 3 ) ( Y 2 δ × Z 2 ) ( Y 1 δ × D ) ( Y 0 δ × D ) = ( Y 3 δ × Z 3 ) ( Y 2 δ × Z 2 ) ( ( Y 1 δ Y 0 δ ) × D ) α

This contradicts with α = δ β . So, δ B 0 \ { α } .

Now, we suppose that δ B ˜ 32 \ { α } and β S 1 \ { α } . Similar operations are applied as above, we obtain δ B ˜ 32 \ { α } .

Now, we suppose that δ = σ 1 and β S 1 \ { α } . Similar operations are applied as above, we obtain δ σ 1 .

That means α δ β for any α B ˜ 32 and δ , β S 1 \ { α } .

If α = σ 1 , then by the definition of σ 1 , quasinormal representation of α has a form α = ( Z 2 × Z 2 ) ( ( X \ Z 2 ) × Z 1 ) . Let α = δ β for some δ , β S 1 \ { σ 1 } .

We suppose that δ B 0 \ { σ 1 } and β S 1 \ { σ 1 } . By definition of B 0 , quasinormal representation of δ has form

δ = ( Y 3 δ × Z 3 ) ( Y 2 δ × Z 2 ) ( Y 1 δ × Z 1 ) ( Y 0 δ × D )

where Y 3 δ , Y 2 δ , Y 1 δ { } . By using Z 3 Z 1 D and Z 2 D we have Z 3 β and Z 2 β are minimal elements of the semilattice { Z 3 β , Z 2 β , Z 1 β , D β } . Also, we have

( Z 2 × Z 2 ) ( ( X \ Z 2 ) × Z 1 ) = α = δ β = ( Y 3 δ × Z 3 β ) ( Y 2 δ × Z 2 β ) ( Y 1 δ × Z 1 β ) ( Y 0 δ × D β )

From Z 2 and Z 1 are minimal elements of the semilattice { Z 2 , Z 1 , D } , this equality is possible only if Z 2 = Z 3 β , Z 1 = Z 2 β or Z 2 = Z 2 β , Z 1 = Z 3 β . By using formal equalities, we obtain

Z 2 = Z 3 β = P 2 β and Z 1 = Z 2 β = P 1 β P 3 β Z 1 = Z 3 β = P 2 β and Z 2 = Z 2 β = P 1 β = P 3 β

respectively. Let Z 2 = P 2 β and Z 1 = P 1 β P 3 β where P 1 β , P 3 β { Z 3 , Z 1 } . Then subquasinormal representation of β has one of the form

β ¯ 1 = ( P 1 × Z 3 ) ( P 2 × Z 2 ) ( P 3 × Z 1 ) t X \ D ( { t } × β ¯ 2 ( t ) )

β ¯ 2 = ( P 3 × Z 3 ) ( P 2 × Z 2 ) ( P 1 × Z 1 ) t X \ D ( { t } × β ¯ 2 ( t ) )

β ¯ 3 = ( P 2 × Z 2 ) ( ( P 1 P 3 ) × Z 1 ) t X \ D ( { t } × β ¯ 2 ( t ) )

where

β ¯ 1 1 = ( P 1 P 2 P 3 Z 3 Z 2 Z 1 ) , β ¯ 1 2 = ( P 1 P 2 P 3 Z 1 Z 2 Z 3 ) , β ¯ 1 3 = ( P 1 P 2 P 3 Z 1 Z 2 Z 1 )

are normal mapping for β ¯ , β ¯ 2 is complement mapping of the set X × D on the set D ˜ = { Z 3 , Z 2 , Z 1 } and δ β = δ β ¯ i . From formal equalities, we obtain

β ¯ 1 = ( ( Z 2 \ Z 1 ) × Z 3 ) ( ( Z 1 \ Z 2 ) × Z 2 ) ( ( Z 2 \ Z 1 ) × Z 1 ) t X \ D ( { t } × β ¯ 2 ( t ) )

β ¯ 2 = ( ( Z 2 Z 1 ) × Z 3 ) ( ( Z 1 \ Z 2 ) × Z 2 ) ( ( Z 2 \ Z 1 ) × Z 1 ) t X \ D ( { t } × β ¯ 2 ( t ) )

β ¯ 3 = ( ( Z 1 \ Z 2 ) × Z 2 ) ( Z 2 × Z 1 ) t X \ D ( { t } × β ¯ 2 ( t ) )

and by using | Y 1 δ Y 0 δ | 1 , we have

δ β ¯ 1 = δ β ¯ 2 = δ β ¯ 3 = ( Y 3 δ × Z 3 β ¯ 1 ) ( Y 2 δ × Z 2 β ¯ 1 ) ( Y 1 δ × Z 1 β ¯ 1 ) ( Y 0 δ × D β ¯ 1 ) = ( Y 3 δ × Z 2 ) ( Y 2 δ × Z 1 ) ( Y 1 δ × D ) ( Y 0 δ × D ) = ( Y 3 δ × Z 2 ) ( Y 2 δ × Z 1 ) ( ( Y 1 δ Y 0 δ ) × D ) α

This contradicts with α = δ β . So, δ B 0 \ { σ 1 } .

Now, we suppose that δ B ˜ 32 \ { σ 1 } and β S 1 \ { σ 1 } . Similar operations are applied as above, we obtain δ B ˜ 32 \ { σ 1 } .

That means α δ β for any α B ˜ 32 and δ , β S 1 \ { α } . □

Lemma 6. Let D = { Z 3 , Z 2 , Z 1 , D } Σ 2.2 ( X , 4 ) , σ 0 = ( Z 3 × Z 3 ) ( ( X \ Z 3 ) × Z 1 ) and σ 1 = ( Z 2 × Z 2 ) ( ( X \ Z 2 ) × Z 1 ) . If X = D then S 2 = B 0 B ˜ 32 { σ 0 , σ 1 } is irreducible generating set for the semigroup B X ( D ) .

Theorem 7. Let D = { Z 3 , Z 2 , Z 1 , D } Σ 2.2 ( X , 4 ) , σ 0 = ( Z 3 × Z 3 ) ( ( X \ Z 3 ) × Z 1 ) and σ 1 = ( Z 2 × Z 2 ) ( ( X \ Z 2 ) × Z 1 ) . If X is a finite set and | X | = n then the following statements are true

a) If | X \ D | 1 then | B 0 B ˜ 32 { σ 1 } | = 4 n 3 n + 1 + 2 n + 2 2

b) If X = D then | B 0 B ˜ 32 { σ 0 , σ 1 } | = 4 n 3 n + 1 + 2 n + 2 1

Proof. Let

S n = { φ i | φ i : M = { 1,2, , n } M = { 1,2, , n } , onetoonemapping }

be a group, φ i 1 , φ i 2 , , φ i m S n ( m n ) and Y φ 1 , Y φ 2 , , Y φ m be partitioning of

X. It is well known that k n m = | { Y φ 1 , Y φ 2 , , Y φ m } | = i = 1 m ( 1 ) m + i ( i 1 ) ! ( m i ) ! . If m = 2 , 3 , 4

then we have

k n 2 = 2 n 1 1 k n 3 = 1 2 3 n 1 2 n 1 + 1 2 k n 4 = 1 6 4 n 1 1 2 3 n 1 + 1 2 2 n 1 1 6

If Y φ 1 , Y φ 2 are any two elements of partitioning of X and β ¯ = ( Y φ 1 × T 1 ) ( Y φ 2 × T 2 ) where T 1 , T 2 D and T 1 T 2 , then the number of different binary relations β ¯ of semigroup B X ( D ) is equal to

2 k n 2 = 2 n 2 (2)

If Y φ 1 , Y φ 2 , Y φ 3 are any three elements of partitioning of X and β ¯ = ( Y φ 1 × T 1 ) ( Y φ 2 × T 2 ) ( Y φ 3 × T 3 ) where T 1 , T 2 , T 3 are pairwise different elements of D, then the number of different binary relations β ¯ of semigroup B X ( D ) is equal to

6 k n 3 = 3 n 3 2 n + 3 (3)

If Y φ 1 , Y φ 2 , Y φ 3 , Y φ 4 are any four elements of partitioning of X and β ¯ = ( Y φ 1 × T 1 ) ( Y φ 2 × T 2 ) ( Y φ 3 × T 3 ) ( Y φ 4 × T 4 ) where T 1 , T 2 , T 3 , T 4 are pairwise different elements of D, then the number of different binary relations β ¯ of semigroup B X ( D ) is equal to

24 k n 4 = 4 n 4 3 n + 3 2 n 4 (4)

Let α B 0 . Quasinormal represantation of α has form

α = ( Y 3 α × Z 3 ) ( Y 2 α × Z 2 ) ( Y 1 α × Z 1 ) ( Y 0 α × D )

where Y 3 α , Y 2 α , Y 1 α { } . Also, Y 3 α , Y 2 α , Y 1 α or Y 3 α , Y 2 α , Y 1 α , Y 0 α are partitioning of X for | X | 4 . By using Equations (2.3) and (2.4) we obtain

| B 0 | = 4 n 3 n + 1 + 3 2 n 1

Let α B ˜ 32 . Quasinormal represantation of α has form α = ( Y 3 α × Z 3 ) ( Y 2 α × Z 2 ) where Y 3 α , Y 2 α { } . Also, Y 3 α , Y 2 α are partitioning of X. By using (2.2) we obtain

| B ˜ 32 | = 2 n 2

So, we have

| B 0 B ˜ 32 { σ 1 } | = 4 n 3 n + 1 + 2 n + 2 2 | B 0 B ˜ 32 { σ 0 , σ 1 } | = 4 n 3 n + 1 + 2 n + 2 1

since B 0 B ˜ 32 = B 0 { σ 0 , σ 1 } = B ˜ 32 { σ 0 , σ 1 } = . □

Acknowledgements

Sincere thanks to Prof. Dr. Neşet AYDIN for his valuable suggestions.

Conflicts of Interest

The authors declare no conflicts of interest.

Cite this paper

Albayrak, B. , Givradze, O. and Partenadze, G. (2018) Generating Sets of the Complete Semigroups of Binary Relations Defined by Semilattices of the Class Σ2 (X,4). Applied Mathematics, 9, 17-27. doi: 10.4236/am.2018.91002.

References

[1] Diasamidze, Y. and Makharadze, S. (2013) Complete Semigroups of Binary Relations. Kriter Yay Nevi, Istanbul.
[2] Diasamidze, Y., Ayd, N.N. and Erdogan, A. (2016) Generating Set of the Complete Semigroups of Binary Relations. Applied Mathematics, 7, 98-107. https://doi.org/10.4236/am.2016.71009
[3] Bakuridze, A., Diasamidze, Y. and Givradze, O. Generated Sets of the Complete Semigroups of Binary Relations Defined by Semilattices of the Class Σ1(X, 2)(In Press)

  
comments powered by Disqus

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.