Generated Sets of the Complete Semigroup Binary Relations Defined by Semilattices of the Class Σ8 (X, n + k + 1)

Abstract

In this article, we study generated sets of the complete semigroups of binary relations defined by X-semilattices unions of the class Σ8 (X, n + k +1) , and find uniquely irreducible generating set for the given semigroups.

Share and Cite:

Diasamidze, Y. , Givradze, O. , Tsinaridze, N. and Tavdgiridze, G. (2018) Generated Sets of the Complete Semigroup Binary Relations Defined by Semilattices of the Class Σ8 (X, n + k + 1). Applied Mathematics, 9, 369-382. doi: 10.4236/am.2018.94028.

1. Introduction

Let X be an arbitrary nonempty set, D is an X-semilattice of unions which is closed with respect to the set-theoretic union of elements from D, f be an arbitrary mapping of the set X in the set D. To each mapping f we put into correspondence a binary relation α f on the set X that satisfies the condition α f = x X ( { x } × f ( x ) ) . The set of all such α f ( f : X D ) is denoted by B X ( D ) . It is easy to prove that B X ( D ) is a semigroup with respect to the operation of multiplication of binary relations, which is called a complete semigroup of binary relations defined by an X-semilattice of unions D.

We denote by Æ an empty binary relation or an empty subset of the set X. The condition ( x , y ) α will be written in the form x α y . Further, let x , y X , Y X , α B X ( D ) , D = Y D Y and T D . We denote by the symbols y α , Y α , V ( D , α ) , X and V ( X , α ) the following sets:

y α = { x X | y α x } , Y α = y Y y α , V ( D , α ) = { Y α | Y D } , X = { Y | Y X } , V ( X , α ) = { Y α | Y X } , D T = { Z D | T Z } , Y T α = { y X | y α = T } .

It is well known the following statements:

Theorem 1.1. Let D = { D , Z 1 , Z 2 , , Z m 1 } be some finite X-semilattice of unions and C ( D ) = { P 0 , P 1 , P 2 , , P m 1 } be the family of sets of pairwise nonintersecting subsets of the set X (the set Æ can be repeated several times). If j is a mapping of the semilattice D on the family of sets C ( D ) which satisfies the conditions

φ = ( D Z 1 Z 2 Z m 1 P 0 P 1 P 2 P m 1 )

and D ^ Z = D \ D Z , then the following equalities are valid:

D = P 0 P 1 P 2 P m 1 , Z i = P 0 T D ^ Z i φ ( T ) . (1.1)

In the sequel these equalities will be called formal.

It is proved that if the elements of the semilattice D are represented in the form (1.1), then among the parameters P i ( 0 < i m 1 ) there exist such parameters that cannot be empty sets for D. Such sets P i are called bases sources, where sets P j ( 0 j m 1 ) , which can be empty sets too are called completeness sources.

It is proved that under the mapping j the number of covering elements of the pre-image of a

bases source is always equal to one, while under the mapping j the number of covering elements of the pre-image of a completeness source either does not exist or is always greater than one (see [1] [2] chapter 11).

Definition 1.1. We say that an element a of the semigroup B X ( D ) is external if α δ β for all δ , β B X ( D ) \ { α } (see [1] [2] Definition 1.15.1).

It is well known, that if B is all external elements of the semigroup B X ( D ) and B is any generated set for the B X ( D ) , then B B (see [1] [2] Lemma 1.15.1).

Definition 1.2. The representation α = T D ( Y T α × T ) of binary relation a is called quasinormal, if T D Y T α = X and Y T α Y T α = for any T , T D ,

T T (see [1] [2] chapter 1.11).

Definition 1.3. Let α , β X × X . Their product δ = α β is defined as follows: x δ y ( x , y X ) if there exists an element z X such that x α z β y (see [1] , chapter 1.3).

2. Result

Let Σ 8 ( X , n + k + 1 ) ( 3 k n ) be a class of all X-semilattices of unions whose every element is isomorphic to an X-semilattice of unions D = { Z 1 , Z 2 , , Z n + k , D } , which satisfies the condition:

Z n + i Z i D , ( i = 1 , 2 , , k ) ; Z j D , ( j = 1 , 2 , , n + k ) ; Z p \ Z q and Z q \ Z p ( 1 p q n + k ) . (see Figure 1).

Figure 1. Diagram of the semilattice D.

It is easy to see that D ˜ = { Z 1 , Z 2 , , Z n + k } is irreducible generating set of the semilattice D.

Let C ( D ) = { P 0 , P 1 , P 2 , , P n + k } be a family of sets, where P 0 , P 1 , P 2 , , P n + k are pairwise disjoint subsets of the set X and φ = ( D Z 1 Z 2 Z n + k P 0 P 1 P 2 P n + k ) is a map

ping of the semilattice D onto the family of sets C ( D ) . Then the formal equalities of the semilattice D have a form:

D = i = 0 n + k P i ; Z j = i = 0 , i j n + k P i , j = 1 , 2 , , n ; Z n + q = i = 0 , i q , n + q n + k P i , q = 1 , 2 , , k . (2.0)

Here the elements P i ( i = 1 , 2 , , n + k ) are bases sources, the element P 0 are sources of completeness of the semilattice D. Therefore | X | n + k (by symbol | X | we denoted the power of a set X), since | P i | 1 ( i = 1 , 2 , , n + k ) (see [1] [2] chapter 11).

In this paper we are learning irreducible generating sets of the semigroup B X ( D ) defined by semilattices of the class Σ 8 ( X , n + k + 1 ) .

Note, that it is well known, when k = 2 , then generated sets of the complete semigroup of binary relations defined by semilattices of the class Σ 8 ( X , 2 + 2 + 1 ) = Σ 8 ( X , 5 ) .

In this paper we suppose, that 3 k n .

Remark, that in this case (i.e. k 3 ), from the formal equalities of a semilattice D follows, that the intersections of any two elements of a semilattice D is not empty.

Lemma 2.0 If D Σ 8 ( X , n + k + 1 ) , then the following statements are true:

a) i = 1 n + k Z i = P 0 ;

b) Z j + 1 \ Z j = P j , j = 1 , 2 , , n 1 ;

c) Z q \ Z n + q = P n + q , q = 1 , , k .

Proof. From the formal equalities of the semilattise D immediately follows the following statements:

i = 1 n + k Z i = P 0 , Z j + 1 \ Z j = ( i = 0 , i j + 1 n + k P i ) \ ( i = 0 , i j n + k P i ) = P j , j = 1 , 2 , , n 1 ; Z q \ Z n + q = ( i = 0 , i q n + k P i ) \ ( i = 0 , i q , n + q n + k P i ) = P n + q , q = 1 , , k .

The statements a), b) and c) of the lemma 2.0 are proved.

Lemma 2.0 is proved.

We denoted the following sets by symbols D 1 , D 2 and D 3 :

D 1 = { Z 1 , Z 2 , , Z k } , D 2 = { Z k + 1 , Z k + 2 , , Z n } , D 3 = { Z n + 1 , Z n + 2 , , Z n + k } .

Lemma 2.1. Let D Σ 8.0 ( X , n + k + 1 ) and α B X ( D ) . Then the following statements are true:

1) Let T , T D 2 D 3 , T T . If T , T V ( D , α ) , then a is external element of the semigroup B X ( D ) ;

2) Let T D 1 , T D 2 D 3 . If T T and T , T V ( D , α ) , then a is external element of the semigroup B X ( D ) .

3) Let T , T D 1 and T T . If T , T V ( D , α ) and k 3 , then a is external element of the semigroup B X ( D ) ;

Proof. Let Z 0 = D and α = δ β for some δ , β B X ( D ) \ { α } . If quasinormal representation of binary relation d has a form

δ = T V ( D , δ ) ( Y T δ × T ) ,

then

α = δ β = T V ( D , δ ) ( Y T δ × T β ) . (2.1)

From the formal equalities (2.0) of the semilattice D we obtain that:

Z 0 β = i = 0 n + k P i β ; Z j β = i = 0 , i j n + k P i β , j = 1 , 2 , , n ; Z n + q β = i = 0 , i q , n + q n + k P i β , q = 1 , 2 , , k . (2.2)

where P i β for any P i ( i = 0 , 1 , 2 , , n + k ) and β B X ( D ) by definition of a semilattice D from the class Σ 8.0 ( X , n + k + 1 ) .

Now, let Z m β = T and Z j β = T for some T T , T , T D 2 D 3 , then from the equalities (2.3) follows that T = P 0 β = T since T and T are minimal elements of the semilattice D and P 0 by preposition. The equality T = T contradicts the inequality T T .

The statement a) of the Lemma 2.1 is proved.

Now, let Z m β = T and Z j β = T , for some T D 1 , T D 2 D 3 and T T , then from the equalities 2.3 follows, that

T = Z j β = Z 0 β = i = 0 n + k P i β , if j = 0 , or T = Z j β = i = 0 , i j n + k P i β , 1 j n , or T = Z n + q β = i = 0 , i q , n + q n + k P i β

where j = n + q . For the Z j β = T we consider the following cases:

1) If T = Z 0 β = i = 0 n + k P i β , then we have

P 0 β = P 1 β = = P n + k β = T ,

since T is a minimal element of a semilattice D. On the other hand,

T = Z m β = { i = 0 , i m n + k P i β = i = 0 , i m n + k T = T , if 1 m n ; i = 0 , i q , n + q n + k P i β = i = 0 , i q , n + q n + k T = T , if m = n + q .

But the equality T = T contradicts the inequality T T . Thus we have, that j 0 .

2) Let 1 j n , i.e. T = Z j β = i = 0 , i j n + k P i β , then we have, that

P 0 β = P 1 β = = P j 1 β = P j + 1 β = = P n + k β = T ,

since T is a minimal element of a semilattice D. On the other hand:

T = Z m β = { ( i = 0 n + k P i β ) = ( i = 0 , i j n + k P i β ) P j β = T P j β , if m = 0 ; ( i = 0 , i m n + k P i β ) = ( i = 0 , i m , j n + k P i β ) P j β = T P j β , if 1 m n , m j ; ( i = 0 , i j , n + j n + k P i β ) = T , if m = n + j ; ( i = 0 , i q , n + q n + k P i β ) = ( i = 0 , i q , n + q , j n + k P i β ) P j β = T P j β , if m = n + q , q j .

The equality T = T contradicts the inequality T T . Also, the equality T = T P j β ( P j β D ) contradicts the inequality T T Z for any Z D and T T ( T T , by preposition) by definition of a semilattice D.

3) If j = n + q ( 1 q k ) , i.e. T = Z n + q β = i = 0 , i q , n + q n + k P i β , then we have, that

P 0 β = P 1 β = = P q 1 β = P q + 1 β = = P n + q 1 β = P n + q + 1 β = = P n + k β = T ,

since T is a minimal element of a semilattice D. On the other hand:

T = Z m β = { ( i = 0 , n + k P i β ) = ( i = 0 , i q , n + q n + k P i β ) P q β P n + q β = T P q β P n + q β , if m = 0 ; ( i = 0 , i q n + k P i β ) = ( i = 0 , i q , n + q n + k P i β ) P n + q β = T P n + q β , if 1 m = q n ; ( i = 0 , i m n + k P i β ) = ( i = 0 , i m , q , n + q n + k P i β ) P q β P n + q β = T P q β P n + q β , if 1 m q n ; ( i = 0 , i m , n + k P i β ) = ( i = 0 , i q , n + q n + k P i β ) = ( i = 0 , i , q , n + q , q , n + q n + k P i β ) P q β P n + q = T P q β P n + q , if n + 1 m = n + q n + k , q q since j m .

The equality T = T contradicts the inequality T T . Also, the equality T = T P q β P n + q β , or T = T P n + q β ( P q β , P n + q β D ) contradicts the inequality T T Z for any Z D and T T by definition of a semilattice D.

The statement 2) of the Lemma 2.1 is proved.

Let T , T D 1 and T T . If k 3 and Z j β = T , Z m β = T , then from the formal equalities (2.0) of a semilattice D there exists such an element, that P q Z j and P q Z m , where 0 q m + k . So, from the equalities (2.3) follows that P q β Z j β = T and P q β Z m β = T . Of from this and from the equalities (2.3) we obtain that there exists such an element Z D , for which the equalities T = Z Z and T = Z Z , where Z , Z D . But such elements by definition of a semilattice D do not exist.

The statement c) of the Lemma 2.1 is proved.

Lemma 2.1 is proved.

Lemma 2.2. Let D Σ 8 ( X , n + k + 1 ) and α B X ( D ) . Then the following statements are true:

1) Let V ( D , α ) D 1 , V ( D , α ) D 2 = , V ( D , α ) D 3 = . If | V ( D , α ) D 1 | 2 , then a is external element of the semigroup B X ( D ) ;

2) Let V ( D , α ) D 1 = , V ( D , α ) D 2 , V ( D , α ) D 3 = . If | V ( D , α ) D 2 | 2 , then a is external element of the semigroup B X ( D ) ;

3) Let V ( D , α ) D 1 = , V ( D , α ) D 2 = , V ( D , α ) D 3 . If | V ( D , α ) D 3 | 2 , then a is external element of the semigroup B X ( D ) ;

4) Let V ( D , α ) D 1 = , V ( D , α ) D 2 , V ( D , α ) D 3 , then a is external element of the semigroup B X ( D ) ;

5) Let V ( D , α ) D 1 , V ( D , α ) D 2 = , V ( D , α ) D 3 . If | V ( D , α ) D 1 | 2 , | V ( D , α ) D 3 | = 1 , or | V ( D , α ) D 1 | = 1 , | V ( D , α ) D 3 | 2 then a is external element of the semigroup B X ( D ) ;

6) Let V ( D , α ) D 1 , V ( D , α ) D 2 , V ( D , α ) D 3 = , then a is external element of the semigroup B X ( D ) ;

7) Let V ( D , α ) D 1 , V ( D , α ) D 2 , V ( D , α ) D 3 , then a is external element of the semigroup B X ( D ) .

Proof. Let a be any element of the semigroup B X ( D ) . It is easy that V ( D , α ) D . We consider the following cases:

Let V ( D , α ) D 1 = , V ( D , α ) D 2 = , V ( D , α ) D 3 = , then V ( D , α ) { D } since V ( D , α ) is subsemilattice of the semilattice D.

1) Let V ( D , α ) D 1 , V ( D , α ) D 2 = , V ( D , α ) D 3 = .

If | V ( D , α ) D 1 | = 1 , then V ( D , α ) { Z j } , or V ( D , α ) { Z j , D } , where j = 1 , 2 , , k , since V ( D , α ) is subsemilattice of the semilattice D.

If | V ( D , α ) D 1 | 2 , then by statement c) of the Lemma 2.1 follows that a is external element of the semigroup B X ( D ) .

2) Let V ( D , α ) D 1 = , V ( D , α ) D 2 , V ( D , α ) D 3 = .

If | V ( D , α ) D 2 | = 1 , then V ( D , α ) { Z j } , or V ( D , α ) { Z j , D } , where j = k + 1 , k + 2 , , n , since V ( D , α ) is a subsemilattice of the semilattice D.

If | V ( D , α ) D 2 | 2 , then by statement a) of the Lemma 2.1 follows that a is external element of the semigroup B X ( D ) .

3) Let V ( D , α ) D 1 = , V ( D , α ) D 2 = , V ( D , α ) D 3 .

If | V ( D , α ) D 3 | = 1 , then V ( D , α ) { Z j } , or V ( D , α ) { Z j , D } , j = n + 1 , n + 2 , , n + k , since V ( D , α ) is subsemilattice of the semilattice D.

If | V ( D , α ) D 3 | 2 , then by statement a) of the Lemma 2.1 follows that a is external element of the semigroup B X ( D ) .

4) Let V ( D , α ) D 1 = , V ( D , α ) D 2 , V ( D , α ) D 3 , then by the statement a) of the Lemma 2.1 follows that a is external element of the semi­group B X ( D ) .

5) Let V ( D , α ) D 1 , V ( D , α ) D 2 = , V ( D , α ) D 3 .

If | V ( D , α ) D 1 | = 1 , | V ( D , α ) D 3 | = 1 , then V ( D , α ) = { Z n + q , Z q } , or V ( D , α ) = { Z n + q , Z q , D } , or V ( D , α ) = { Z n + q , Z j , D } where Z 1 Z j Z k and q = 1 , 2 , , k .

If V ( D , α ) = { Z n + q , Z j , D } where j q , q = 1 , 2 , , k , then by the statement 2) of the Lemma 2.1 follows that a is external element of the semigroup B X ( D ) ;

If | V ( D , α ) D 1 | = 1 , | V ( D , α ) D 3 | 2 , or | V ( D , α ) D 1 | 2 , | V ( D , α ) D 3 | = 1 , then from the statement 1) and 3) of the Lemma 2.1 follows that a is external element of the semigroup B X ( D ) respectively.

6) Let V ( D , α ) D 1 , V ( D , α ) D 2 , V ( D , α ) D 3 = . Then from the statement b) of the Lemma 2.1 follows that a is external element of the semi­group B X ( D ) .

7) Let V ( D , α ) D 1 , V ( D , α ) D 2 , V ( D , α ) D 3 , then by the statement a) of the Lemma 2.1 follows that a is external element of the semi­group B X ( D ) .

Lemma 2.2 is proved.

Now we learn the following subsemilattices of the semilattice D:

A 1 = { { Z n + j , Z j , D } } , where j = 1 , 2 , , k ; A 2 = { { Z j , D } } , where j = 1 , 2 , , n + k ; A 3 = { { Z n + j , Z j } } , where j = 1 , 2 , , k ; A 4 = { { Z j } , { D } } , where j = 1 , 2 , , n + k .

We denoted the following sets by symbols A 0 and B ( A 0 ) :

A 0 = { V ( D , α ) D | V ( D , α ) A 1 A 2 A 3 A 4 } , B ( A 0 ) = { α B X ( D ) | V ( D , α ) A 0 } .

By definition of a set B ( A 0 ) follows that any element of the set is external element of the semigroup B X ( D ) .

Lemma 2.3. Let D Σ 8 ( X , n + k + 1 ) . If quasinormal representation of a binary relation a has a form

α = ( Y n + j α × Z n + j ) ( Y j α × Z j ) ( Y 0 α × D ) ,

where Y n + j α , Y j α , Y 0 α { } and j = 1 , 2 , , k , then a is generated by elements of the elements of set B ( A 0 ) .

Proof. 1). Let quasinormal representation of binary relations d and b have a form

δ = ( Y n + j δ × Z n + j ) ( Y j δ × Z j ) ( Y q δ × Z q ) ( Y 0 δ × D ) , β = ( Z n + j × Z n + j ) ( ( Z j \ Z n + j ) × Z j ) ( ( D \ Z j ) × Z q ) ( ( X \ D ) × D ) ,

where Y n + j α , Y j α , Y q α { } , Z 1 Z q Z k , q j , j = 1 , , k .

Z n + j ( Z j \ Z n + j ) ( D \ Z j ) ( X \ D ) = ( P 0 i = 1 , i j , n + j n + k P i ) P n + j P j ( X \ D ) = D ( X \ D ) = X ,

since the representation of a binary relation b is quasinormal and by statement 3) of the Lemma 2.1 binary relations d and b are external elements of the semigroup B X ( D ) . It is easy to see, that:

Z n + j β = Z n + j ,

Z j β = ( P 0 i = 1 , i j n + k P i ) β = ( ( P 0 i = 1 , i j , n + j n + k P i ) P n + j ) β = Z n + j β P n + j β = Z n + j Z j = Z j ,

Z q β = ( P 0 i = 1 , i q n + k P i ) β = Z n + j Z j Z q = D , D β = i = 0 n + k P i β = Z n + j Z j Z q = D

since Z q Z n + j , Z q ( Z j \ Z n + j ) = P n + j , Z q ( D \ Z j ) = P j (see equality (2.0))

α = δ β = ( Y n + j δ × Z n + j β ) ( Y j δ × Z j β ) ( Y q δ × Z q β ) ( Y 0 δ × D β ) = ( Y n + j δ × Z n + j ) ( Y j δ × Z j ) ( Y q δ × D ) ( Y 0 δ × D ) = ( Y n + j δ × Z n + j ) ( Y j δ × Z j ) ( ( Y q δ Y 0 δ ) × D ) = α ,

if Y n + j δ = Y n + j α , Y j δ = Y j α and Y q δ Y 0 δ = Y 0 α . Last equalities are possible since | Y q δ Y 0 δ | 1 ( | Y 0 δ | 0 , by preposition).

Lemma 2.3 is proved.

Lemma 2.4. Let D Σ 8 ( X , n + k + 1 ) . If quasinormal representation of a binary relation a has a form α = ( Y j α × Z j ) ( Y 0 α × D ) , where Y j α , Y 0 α { } , j = 1 , 2 , , n + k , then binary relation a is generated by elements of the elements of set B ( A 0 ) .

Proof. Let quasinormal representation of the binary relations d and b have a form:

δ = ( Y j δ × Z j ) ( Y q δ × Z q ) ( Y 0 δ × D ) , β = ( Z j × Z j ) ( ( D \ Z j ) × Z q ) ( ( X \ D ) × D ) ,

where Y j δ , Y q δ { } and Z 1 Z j Z q Z n + k . Then from the statements a), b) and c) of the Lemma 2.1 follows, that d and b are generated by elements of the set B ( A 0 ) and

Z j β = Z j ,

Z q β = D , since Z q ( D \ Z j ) = P j ,

D β = D ;

δ β = ( Y j δ × Z j β ) ( Y q δ × Z q β ) ( Y 0 δ × D β ) = ( Y j δ × Z j ) ( Y q δ × D ) ( Y 0 δ × D ) = ( Y j δ × Z j ) ( ( Y q δ Y 0 δ ) × D ) = α ,

if Y j δ = Y j α , Y q δ Y 0 δ = Y 0 α and q = 1 , 2 , , n + k . Last equalities are possible since | Y q δ Y 0 δ | 1 ( | Y 0 δ | 0 by preposition).

Lemma 2.4 is proved.

Lemma 2.5. Let D Σ 8 ( X , n + k + 1 ) . If quasinormal representation of a binary relation a has a form α = ( Y n + j α × Z n + j ) ( Y j α × Z j ) , where Y n + j α , Y j α { } , j = 1 , 2 , , k , then binary relation a is generated by elements of the elements of set B ( A 0 ) .

Proof. Let quasinormal representation of a binary relations d, b have a form

δ = ( Y n + j δ × Z n + j ) ( Y q δ × Z q ) ( Y 0 δ × D ) , β = ( Z n + j × Z n + j ) ( ( D \ Z n + j ) × Z j ) ( ( X \ D ) × D ) ,

where Y n + j δ , Y q δ { } , j q and j = 1 , 2 , , k . Then from the Lemma 2.2 follows that b is generated by elements of the set B ( A 0 ) , δ B ( A 0 ) and

Z n + j β = Z n + j ,

Z q β = Z n + j Z j = Z j , since Z q Z n + j , Z q ( D \ Z n + j ) = P n + j , j q (see equality(2.0))

D β = Z j since D ( X \ D ) = ,

δ β = ( Y n + j δ × Z n + j β ) ( Y q δ × Z q β ) ( Y 0 δ × D ) = ( Y n + j δ × Z n + j ) ( Y q δ × Z j ) ( Y 0 δ × Z j ) = ( Y n + j δ × Z n + j ) ( ( Y q δ Y 0 δ ) × Z j ) = α ,

if Y n + j δ = Y n + j α and Y q δ Y 0 δ = Y j α . Last equalities are possible since | Y q δ Y 0 δ | 1 ( | Y 0 δ | 0 by preposition).

Lemma 2.5 is proved.

Lemma 2.6. Let D Σ 8 ( X , n + k + 1 ) . Then the following statements are true:

1) If quasinormal representation of a binary relation a has a form α = X × Z j ( j = 1 , 2 , , k ) , then binary relation a is generated by elements of the set B ( A 0 ) .

2) If quasinormal representation of a binary relation a has a form α = X × D , then binary relation a is generated by elements of the set B ( A 0 ) .

Proof. 1) Let T D \ ( D 2 D 3 ) . If quasinormal representation of a binary relations d, b have a form

δ = ( Y j δ × Z j ) ( Y 0 δ × D ) , β = ( Z n + j × Z n + j ) ( ( Z j \ Z n + j ) × Z j ) ( ( X \ D ) × D ) ,

where Y j δ , Y 0 δ { } , j = 1 , 2 , , k

Z n + j ( Z j \ Z n + j ) ( X \ D ) = ( i = 0 , i j , n + j n + k P i ) ( P j P n + j ) ( X \ D ) = D ( X \ D ) = X

(see equalities (2.0) and (2.1)), then from the Lemma 2.4 follows that d is generated by elements of the set B ( A 0 ) and from the Lemma 2.3 element b is generated by elements of the set B ( A 0 ) and

Z j β = Z n + j Z j = Z j ,

D β = Z j , since D ( X \ D ) = ,

δ β = ( Y j δ × Z j β ) ( Y 0 δ × D β ) = ( Y j δ × Z j ) ( Y 0 δ × Z j ) = X × Z j = α ,

since representation of a binary relation d is quasinormal.

The statement a) of the lemma 2.6 is proved.

2) Let quasinormal representation of a binary relation d have a form

δ = ( Z n + j × Z q ) ( ( X \ Z n + j ) × D ) ,

where j q , then from the Lemma 2.4 follows that d is generated by elements of the set B ( A 0 ) and

Z q δ = ( i = 0 , i q n + k P i ) δ = ( i = 0 , i q n + k P i δ ) = Z q D = D , D δ = D , since j q , Z q δ Z n + 1 and Z q δ ( X \ Z n + 1 ) ;

δ δ = ( Z n + j × Z q δ ) ( ( X \ Z n + j ) × D δ ) = ( Z n + j × D ) ( ( X \ Z n + j ) × D ) = X × D = α ,

since representation of a binary relation d is quasinormal.

The statement b) of the lemma 2.6 is proved.

Lemma 2.6 is proved.

Lemma 2.7. Let D Σ 8 ( X , n + k + 1 ) . Then the following statements are true:

a) If | X \ D | 1 and T D 2 D 3 , then binary relation α = X × T is generated by elements of the elements of set B ( A 0 ) ;

b) If X = D and T D 2 D 3 , then binary relation α = X × T is external element for the semigroup B X ( D ) .

Proof. 1) If quasinormal representation of a binary relation d has a form

δ = ( Y 0 δ × D ) j = k + 1 n + k ( Y j δ × Z j ) ,

where Y j δ for all j = k + 1 , k + 2 , , n + k , then δ B ( A 0 ) \ { α } . Let quasinormal representation of a binary relations b have a form

β = ( D × T ) t X \ D ( { t } × f ( t ) ) , where f is any mapping of the set X \ D in the set ( D 2 D 3 ) \ { T } . It is easy to see, that β α and two elements of the set D 2 D 3 belong to the semilattice V ( D , β ) , i.e. δ B ( A 0 ) \ { α } . In this case we have that Z j β = T for all j = k + 1 , k + 2 , , n + k .

δ β = δ = ( Y 0 δ × D β ) j = k + 1 n + k ( Y j δ × Z j β ) = ( Y 0 δ × T ) j = k + 1 n + k ( Y j δ × T ) = ( ( Y 0 δ j = k + 1 n + k Y j δ ) × T ) = X × T = α ,

since the representation of a binary relation d is quasinormal. Thus, the element a is generated by elements of the set B ( A 0 ) .

The statement a) of the lemma 2.7 is proved.

2) Let X = D , α = X × T , for some T D 2 D 3 and α = δ β for some δ , β B X ( D ) \ { α } . Then we obtain that Z j β = T since T is a minimal element of the semilattice D.

Now, let subquasinormal representations β ¯ of a binary relation b have a form

β ¯ = ( ( i = 0 n + k P i ) × T ) t X \ D ( { t } × β ¯ 2 ( t ) ) ,

where β ¯ 1 = ( P 0 P 1 P 2 P n + k T T T T ) is normal mapping. But complement mapping β ¯ 2 is empty, since X \ D = , i.e. in the given case, subquasinormal representation β ¯ of a binary relation b is defined uniquely. So, we have that β = β ¯ = X × T = α (see property 2) in the case 1.1), which contradict the condition, that β B X ( D ) \ { α } .

Therefore, if X = D and α = X × T , for some T D 2 D 3 , then a is external element of the semigroup B X ( D ) .

The statement 2) of the Lemma 2.7 is proved.

Lemma 2.7 is proved.

Theorem 2.1. Let D Σ 8 ( X , n + k + 1 ) , k 3 , and

D 1 = { Z 1 , Z 2 , , Z k } , D 2 = { Z k + 1 , Z k + 2 , , Z n } , D 3 = { Z n + 1 , Z n + 2 , , Z n + k } ;

A 1 = { { Z n + q , Z q , D } } , where q = 1 , 2 , , k ;

A 2 = { { Z j , D } } , where j = 1 , 2 , , n + k ;

A 3 = { { Z n + j , Z j } } , where j = 1 , 2 , , k ;

A 4 = { { Z j } , { D } } , where j = 1 , 2 , , n + k ;

A 0 = { V ( D , α ) D | V ( D , α ) A 1 A 2 A 3 A 4 } ,

B ( A 0 ) = { α B X ( D ) | V ( D , α ) A 0 } ,

B 0 = { X × T | T D 2 D 3 }

Then the following statements are true:

1) If | X \ D | 1 , then the S 0 = B ( A 0 ) is irreducible generating set for the semigroup B X ( D ) ;

2) If X = D , then the S 1 = B 0 B ( A 0 ) is irreducible generating set for the semigroup B X ( D ) .

Proof. Let D Σ 8 ( X , n + k + 1 ) , k 3 and | X \ D | 1 . First, we proved that every element of the semigroup B X ( D ) is generated by elements of the set S 0 . Indeed, let a be an arbitrary element of the semigroup B X ( D ) . Then quasinormal representation of a binary relation a has a form

α = ( Y 0 α × D ) i = 1 n + k ( Y i α × Z i ) ,

where i = 0 n + k Y i α = X and Y i α Y j α = ( 0 i j n + k ) . For the V ( X , α ) we consider the following cases:

1) If V ( X , α ) A 1 A 2 A 3 A 4 , then α B ( A 0 ) S 0 by definition of a set S 0 .

Now, let V ( X , α ) A 1 A 2 A 3 A 4 .

2) If V ( X , α ) A 1 , then quasinormal representation of a binary relation a has a form α = ( Y n + j α × Z n + j ) ( Y j α × Z j ) ( Y 0 α × D ) , where Y n + j α , Y j α , Y 0 α { } ( j = 1 , 2 , , k ) and from the Lemma 2.3 follows that a is generated by elements of the elements of set B ( A 0 ) S 0 by definition of a set S 0 .

3) If V ( X , α ) A 2 , then quasinormal representation of a binary relation a has a form α = ( Y j α × Z j ) ( Y 0 α × D ) , where Y j α , Y 0 α { } , j = 1 , 2 , , n + k and from the Lemma 2.4 follows that a is generated by elements of the elements of set B ( A 0 ) S 0 by definition of a set S 0 .

4) If V ( X , α ) A 3 , then quasinormal representation of a binary relation a has a form α = ( Y n + j α × Z n + j ) ( Y j α × Z j ) , where Y n + j α , Y j α { } , j = 1 , 2 , , k and from the Lemma 2.5 follows that a is generated by elements of the elements of set B ( A 0 ) S 0 by definition of a set S 0 .

Now, let V ( X , α ) A 4 , then quasinormal representation of a binary relation a has a form α = X × D , or α = X × Z j , where j = 1 , 2 , , n + k .

5) If α = X × D , then from the statement b) of the Lemma 2.6 follows that binary relation a is generated by elements of the set B ( A 0 ) .

6) If α = X × Z j , where j = 1 , 2 , , n + k , then from the statement a) of the Lemma 2.6 and 2.7 follows that binary relation a is generated by elements of the set B ( A 0 ) .

Thus, we have that S 0 is a generating set for the semigroup B X ( D ) .

If | X \ D | 1 , then the set S 0 is an irreducible generating set for the semigroup B X ( D ) since, S 0 is a set external elements of the semigroup B X ( D ) .

The statement a) of the Theorem 2.1 is proved.

Now, let X = D . First, we proved that every element of the semigroup B X ( D ) is generated by elements of the set S 1 . The cases 1), 2), 3), 4) and 5) are proved analogously of the cases 1), 2), 3), 4) and 5 given above and consider case, when V ( X , α ) A 1 .

If V ( X , α ) = Z j , where j = 1 , 2 , , k , then from the statement a) of the Lemma 2.7 follows that binary relation a is generated by elements of the set B ( A 0 ) .

If V ( X , α ) = Z j , where Z j D 2 D 3 , then from the statement b) of the Lemma 2.6 follows that binary relation α = X × T is external element for the semigroup B X ( D ) .

Thus, we have that S 1 is a generating set for the semigroup B X ( D ) .

If X = D , then the set S 1 is an irreducible generating set for the semigroup B X ( D ) since S 1 is a set external elements of the semigroup B X ( D ) .

The statement b) of the Theorem 2.1 is proved.

Theorem 2.1 is proved.

Corollary 2.1. Let D Σ 8 ( X , n + k + 1 ) ( k 3 ) and

D 1 = { Z 1 , Z 2 , , Z k } , D 2 = { Z k + 1 , Z k + 2 , , Z n } , D 3 = { Z n + 1 , Z n + 2 , , Z n + k } ;

A 1 = { { Z n + q , Z q , D } } , where q = 1 , 2 , , k ;

A 2 = { { Z j , D } } , where j = 1 , 2 , , n + k ;

A 3 = { { Z n + j , Z j } } , where j = 1 , 2 , , k ;

A 4 = { { Z j } , { D } } , where j = 1 , 2 , , n + k ;

A 0 = { V ( D , α ) D | V ( D , α ) A 1 A 2 A 3 A 4 } ,

B ( A 0 ) = { α B X ( D ) | V ( D , α ) A 0 } ,

B 0 = { X × T | T D 2 D 3 }

Then the following statements are true:

1) If | X \ D | 1 , then S 0 = B ( A 0 ) is the uniquely defined generating set for the semigroup B X ( D ) ;

2) If X = D , then S 1 = B 0 B ( A 0 ) is the uniquely defined generating set for the semigroup B X ( D ) .

Proof. It is well known, that if B is all external elements of the semigroup B X ( D ) and B is any generated set for the B X ( D ) , then B B (see [1] [2] Lemma 1.15.1). From this follows that the sets S 0 = B ( A 0 ) and S 1 = B 0 B ( A 0 ) are defined uniquely, since they are sets external elements of the semigroup B X ( D ) .

Corollary 2.1 is proved.

It is well-known, that if B is all external elements of the semigroup B X ( D ) and B is any generated set for the B X ( D ) , then B B (Definition 1.1).

In this article, we find irredusible generating set for the complete semigroups of binary relations defined by X-semilattices of unions of the class Σ 8 ( X , n + k + 1 ) ( k 3 ) . This generating set is uniquely defined, since they are defined by elements of the external elements of the semigroup B X ( D ) .

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1] Diasamidze, Y. and Makharadze, S. (2013) Complete Semigroups of Binary Relations. Kriter, Turkey, 1-519.
[2] Я. И. Диасамидзе, Ш. И. Махарадзе (2017) Полные полугруппы бинарных отношений. Lambert Academic Publishing, 1-692.

Copyright © 2024 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.