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 on the set X that satisfies the condition . The set of all such ( ) is denoted by . It is easy to prove that 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 will be written in the form . Further, let , , , and . We denote by the symbols , , , and the following sets:
It is well known the following statements:
Theorem 1.1. Let be some finite X-semilattice of unions and 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 which satisfies the conditions
and , then the following equalities are valid:
(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 there exist such parameters that cannot be empty sets for D. Such sets are called bases sources, where sets , 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 is external if for all (see [1] [2] Definition 1.15.1).
It is well known, that if B is all external elements of the semigroup and is any generated set for the , then (see [1] [2] Lemma 1.15.1).
Definition 1.2. The representation of binary relation a is called quasinormal, if and for any ,
(see [1] [2] chapter 1.11).
Definition 1.3. Let . Their product is defined as follows: if there exists an element such that (see [1] , chapter 1.3).
2. Result
Let be a class of all X-semilattices of unions whose every element is isomorphic to an X-semilattice of unions , which satisfies the condition:
(see Figure 1).
Figure 1. Diagram of the semilattice D.
It is easy to see that is irreducible generating set of the semilattice D.
Let be a family of sets, where are pairwise disjoint subsets of the set X and is a map
ping of the semilattice D onto the family of sets . Then the formal equalities of the semilattice D have a form:
(2.0)
Here the elements are bases sources, the element are sources of completeness of the semilattice D. Therefore (by symbol we denoted the power of a set X), since (see [1] [2] chapter 11).
In this paper we are learning irreducible generating sets of the semigroup defined by semilattices of the class .
Note, that it is well known, when , then generated sets of the complete semigroup of binary relations defined by semilattices of the class .
In this paper we suppose, that .
Remark, that in this case (i.e. ), 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 , then the following statements are true:
a)
b)
c)
Proof. From the formal equalities of the semilattise D immediately follows the following statements:
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 , and :
Lemma 2.1. Let and . Then the following statements are true:
1) Let . If , then a is external element of the semigroup ;
2) Let , . If and , then a is external element of the semigroup .
3) Let and . If and , then a is external element of the semigroup ;
Proof. Let and for some . If quasinormal representation of binary relation d has a form
,
then
. (2.1)
From the formal equalities (2.0) of the semilattice D we obtain that:
(2.2)
where for any and by definition of a semilattice D from the class .
Now, let and for some , , then from the equalities (2.3) follows that since T and are minimal elements of the semilattice D and by preposition. The equality contradicts the inequality .
The statement a) of the Lemma 2.1 is proved.
Now, let and , for some , and , then from the equalities 2.3 follows, that
, if , or , , or
where . For the we consider the following cases:
1) If , then we have
,
since is a minimal element of a semilattice D. On the other hand,
But the equality contradicts the inequality . Thus we have, that .
2) Let , i.e. , then we have, that
,
since is a minimal element of a semilattice D. On the other hand:
The equality contradicts the inequality . Also, the equality contradicts the inequality for any and ( , by preposition) by definition of a semilattice D.
3) If , i.e. , then we have, that
,
since is a minimal element of a semilattice D. On the other hand:
The equality contradicts the inequality . Also, the equality , or contradicts the inequality for any and by definition of a semilattice D.
The statement 2) of the Lemma 2.1 is proved.
Let and . If and , , then from the formal equalities (2.0) of a semilattice D there exists such an element, that and , where . So, from the equalities (2.3) follows that and . Of from this and from the equalities (2.3) we obtain that there exists such an element , for which the equalities and , where . 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 and . Then the following statements are true:
1) Let . If , then a is external element of the semigroup ;
2) Let . If , then a is external element of the semigroup ;
3) Let . If , then a is external element of the semigroup ;
4) Let , then a is external element of the semigroup ;
5) Let . If , , or , then a is external element of the semigroup ;
6) Let , then a is external element of the semigroup ;
7) Let , then a is external element of the semigroup .
Proof. Let a be any element of the semigroup . It is easy that . We consider the following cases:
Let , then since is subsemilattice of the semilattice D.
1) Let .
If , then , or , where , since is subsemilattice of the semilattice D.
If , then by statement c) of the Lemma 2.1 follows that a is external element of the semigroup .
2) Let .
If , then , or , where , since is a subsemilattice of the semilattice D.
If , then by statement a) of the Lemma 2.1 follows that a is external element of the semigroup .
3) Let .
If , then , or , , since is subsemilattice of the semilattice D.
If , then by statement a) of the Lemma 2.1 follows that a is external element of the semigroup .
4) Let , then by the statement a) of the Lemma 2.1 follows that a is external element of the semigroup .
5) Let .
If , then , or , or where and .
If where , then by the statement 2) of the Lemma 2.1 follows that a is external element of the semigroup ;
If , or , then from the statement 1) and 3) of the Lemma 2.1 follows that a is external element of the semigroup respectively.
6) Let . Then from the statement b) of the Lemma 2.1 follows that a is external element of the semigroup .
7) Let , then by the statement a) of the Lemma 2.1 follows that a is external element of the semigroup .
Lemma 2.2 is proved.
Now we learn the following subsemilattices of the semilattice D:
We denoted the following sets by symbols and :
By definition of a set follows that any element of the set is external element of the semigroup .
Lemma 2.3. Let . If quasinormal representation of a binary relation a has a form
where and , then a is generated by elements of the elements of set .
Proof. 1). Let quasinormal representation of binary relations d and b have a form
where .
,
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 . It is easy to see, that:
since (see equality (2.0))
if , and . Last equalities are possible since ( , by preposition).
Lemma 2.3 is proved.
Lemma 2.4. Let . If quasinormal representation of a binary relation a has a form , where , , then binary relation a is generated by elements of the elements of set .
Proof. Let quasinormal representation of the binary relations d and b have a form:
where and . 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 and
, since
if , and . Last equalities are possible since ( by preposition).
Lemma 2.4 is proved.
Lemma 2.5. Let . If quasinormal representation of a binary relation a has a form , where , , then binary relation a is generated by elements of the elements of set .
Proof. Let quasinormal representation of a binary relations d, b have a form
where , and . Then from the Lemma 2.2 follows that b is generated by elements of the set , and
, since , (see equality(2.0))
since
if and . Last equalities are possible since ( by preposition).
Lemma 2.5 is proved.
Lemma 2.6. Let . Then the following statements are true:
1) If quasinormal representation of a binary relation a has a form , then binary relation a is generated by elements of the set .
2) If quasinormal representation of a binary relation a has a form , then binary relation a is generated by elements of the set .
Proof. 1) Let . If quasinormal representation of a binary relations d, b have a form
where ,
(see equalities (2.0) and (2.1)), then from the Lemma 2.4 follows that d is generated by elements of the set and from the Lemma 2.3 element b is generated by elements of the set and
, since
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
where , then from the Lemma 2.4 follows that d is generated by elements of the set and
, since and
,
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 . Then the following statements are true:
a) If and , then binary relation is generated by elements of the elements of set ;
b) If and , then binary relation is external element for the semigroup .
Proof. 1) If quasinormal representation of a binary relation d has a form
,
where for all , then . Let quasinormal representation of a binary relations b have a form
, where f is any mapping of the set in the set . It is easy to see, that and two elements of the set belong to the semilattice , i.e. . In this case we have that for all .
since the representation of a binary relation d is quasinormal. Thus, the element a is generated by elements of the set .
The statement a) of the lemma 2.7 is proved.
2) Let , , for some and for some . Then we obtain that since T is a minimal element of the semilattice D.
Now, let subquasinormal representations of a binary relation b have a form
,
where is normal mapping. But complement mapping is empty, since , i.e. in the given case, subquasinormal representation of a binary relation b is defined uniquely. So, we have that (see property 2) in the case 1.1), which contradict the condition, that .
Therefore, if and , for some , then a is external element of the semigroup .
The statement 2) of the Lemma 2.7 is proved.
Lemma 2.7 is proved.
Theorem 2.1. Let , , and
Then the following statements are true:
1) If , then the is irreducible generating set for the semigroup ;
2) If , then the is irreducible generating set for the semigroup .
Proof. Let , and . First, we proved that every element of the semigroup is generated by elements of the set . Indeed, let a be an arbitrary element of the semigroup . Then quasinormal representation of a binary relation a has a form
,
where and . For the we consider the following cases:
1) If , then by definition of a set .
Now, let .
2) If , then quasinormal representation of a binary relation a has a form , where and from the Lemma 2.3 follows that a is generated by elements of the elements of set by definition of a set .
3) If , then quasinormal representation of a binary relation a has a form , where , and from the Lemma 2.4 follows that a is generated by elements of the elements of set by definition of a set .
4) If , then quasinormal representation of a binary relation a has a form , where , and from the Lemma 2.5 follows that a is generated by elements of the elements of set by definition of a set .
Now, let , then quasinormal representation of a binary relation a has a form , or , where .
5) If , then from the statement b) of the Lemma 2.6 follows that binary relation a is generated by elements of the set .
6) If , where , 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 .
Thus, we have that is a generating set for the semigroup .
If , then the set is an irreducible generating set for the semigroup since, is a set external elements of the semigroup .
The statement a) of the Theorem 2.1 is proved.
Now, let . First, we proved that every element of the semigroup is generated by elements of the set . 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 .
If , where , then from the statement a) of the Lemma 2.7 follows that binary relation a is generated by elements of the set .
If , where , then from the statement b) of the Lemma 2.6 follows that binary relation is external element for the semigroup .
Thus, we have that is a generating set for the semigroup .
If , then the set is an irreducible generating set for the semigroup since is a set external elements of the semigroup .
The statement b) of the Theorem 2.1 is proved.
Theorem 2.1 is proved.
Corollary 2.1. Let and
Then the following statements are true:
1) If , then is the uniquely defined generating set for the semigroup ;
2) If , then is the uniquely defined generating set for the semigroup .
Proof. It is well known, that if B is all external elements of the semigroup and is any generated set for the , then (see [1] [2] Lemma 1.15.1). From this follows that the sets and are defined uniquely, since they are sets external elements of the semigroup .
Corollary 2.1 is proved.
It is well-known, that if B is all external elements of the semigroup and is any generated set for the , then (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 . This generating set is uniquely defined, since they are defined by elements of the external elements of the semigroup .