1. Introduction
In this paper we characterize the elements of the class. This class is the complete -semilattice of unions every elements of which are isomorphic to. So, we characterize the class for each element which is isomorphic to by means of the characteristic family of sets, the characteristic mapping and the generate set of.
Let be an arbitrary nonempty set, recall that the set of all binary relations on is denoted. The binary operation on defined by for and, for some is associative and hence is a semigroup with respect to the operation. This semigroup is called the semigroup of all binary relations on the set. By we denote an empty binary relation or empty subset of the set.
Let be a -semilattice of unions, i.e. a nonempty set of subsets of the set that is closed with respect to the set-theoretic operations of unification of elements from, be an arbitrary mapping from into. To each such a mapping there corresponds a binary relation on the set 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 a -semilattice of unions (see ([1] , Item 2.1), ( [2] , Item 2.1)).
Let, , , , and. We use the notations:
Let, and
In general, a representation of a binary relation of the form is called quasinormal.
Note that for a quasinormal representation of a binary relation, not all sets can be different from an empty set. But for this representation the following conditions are always fulfilled:
a), for any and;
b) (see ( [1] , Definition 1.11.1), ( [2] , Definition 1.11.1)).
Let. is called right unit of the semigroup. If for any. An element taken from the semigroup called a regular element of the semigroup if in there exists an element such that (see [1] - [3] ).
In [1] [2] they show that is regular element of iff is a complete -semilat- tice of unions.
A complete -emilattice of unions is an -emilattice of unions if it satisfies the following two conditions:
(a) for any;
(b) for any nonempty element of (see ( [1] , Definition 1.14.2), ( [2] , Definition 1.14.2) or [4] ). Under the symbol we mean an exact lower bound of the set in the semilattice.
Let be an arbitrary nonempty subset of the complete -semilattice of unions. A nonempty element is a nonlimiting element of the set if and a nonempty element is a limiting element of the set if (see ( [1] , Definition 1.13.1 and Definition 1.13.2), ( [2] , Definition 1.13.1 and Definition 1.13.2)).
Let be some finite -semilattice of unions and be the family of sets of pairwise nonintersecting subsets of the set. If is a mapping of the semilattice on the family of sets which satisfies the condition and for any and, then the following equalities are valid:
In the sequel these equalities will be called formal.
It is proved that if the elements of the semilattice are represented in the form, then among the para-
meters there exist such parameters that cannot be empty sets for. Such sets are called basis sources, whereas sets which can be empty sets too are called completeness sources.
It is proved that under the mapping the number of covering elements of the pre-image of a basis source is always equal to one, while under the mapping 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] , Item 11.4), ( [2] , Item 11.4) or [5] ).
The one-to-one mapping between the complete -semilattices of unions and is called a complete isomorphism if the condition
Is fulfilled for each nonempty subset of the semilattice (see ( [1] , definition 6.3.2), ( [2] , definition 6.3.2) or [6] ) and the complete isomorphism between the complete semilattices of unions and is a complete -isomorphism if (b)
(a);
(b) for and for all (see ( [1] , Definition 6.3.3), ( [2] , Definition 6.3.3)).
Lemma 1.1. Let by a complete -semilattice of unions. If a binary relation of the form is right unit of the semigroup, then is the greatest right
unit of that semigroup (see ( [1] , Lemma 12.1.2), ( [2] , Lemma 12.1.2)).
Theorem 1.1. Let, and―be three such sets, that. If is such
mapping of the set, in the set, for which for some, then the numbers of all those
mappings of the set in the set is equal to (see ( [1] , Theorem 1.18.2), ( [2] , Theorem 1.18.2)).
Theorem 1.2. Let be a finite -semilattice of unions and for some and of the semigroup; be the set of those elements of the semilattice which are nonlimiting elements of the set. Then a binary relation having a quasinormal representation of the form
is a regular element of the semigroup iff the set is a -semilattice of unions and for -isomorphism of the semilattice on some -subsemilattice of the semilat- tice the following conditions are fulfilled:
(a) for any;
(b) for any;
(c) for any element of the set (see ( [1] , Theorem 6.3.3), ( [2] , Theorem 6.3.3) or [6] ).
Theorem 1.3. Let be a complete -emilattice of unions. The semigroup possesses a right unit iff is an -semilattice of unions (see ( [1] , Theorem 6.1.3), ( [2] , Theorem 6.1.3) or [7] ).
2. Results
Let is any -semilattice of unions and, which satisfies the following con- ditions:
(1)
The semilattice, which satisfying the conditions (1) is shown in Figure 1. By the symbol we denote the set of all -semilattices of unions whose every element is isomorphic to.
Let is a family sets, where are pairwise dis- joint subsets of the set and
is a mapping of the semilattice into the family sets. Then for the formal equalities of the semilattice we have a form:
(2)
here the elements are basis sources, the element are sources of completenes of the semilattice. Therefore and.
Theorem 2.1. Let. Then is -semilattice, when.
Proof. Let, and is the exact lower bound of the set in. Then of the formal equalities follows, that
We have and if. So, from the definition -semilattice follows that is not -semilattice.
If (since they are completeness sources), then for all and, ,. Of the last conditions and from the Definition -semilattice follows that is -semilattice. Of the equality follows that
Of the other hand, if then by formal equalities follows that. Therefore, semilattice is -semilattice.
The Theorem is proved.
Lemma 2.1. Let and. Then following equalities are true:
Proof. The given Lemma immediately follows from the formal equalities (2) of the semilattice.
The lemma is proved.
Lemma 2.2. Let and. Then the binary relation
is the largest right unit of the semigroup.
Proof. By preposition and from Theorem 2.1 follows that is -semilattice. Of this, from Lemma 1.1, from Lemma 2.1 and from Theorem 1.3 we have that the binary relation
is the largest right unit of the semigroup.
The lemma is proved.
Lemma 2.3. Let and. Binary relation having quazi-normal representation of the form
where and is a regular element of the semigroup iff for some complete isomorphism of the semilattice on some -subsemilattice (see Figure 2) of the semilattice satisfies the following conditions:
Proof. It is easy to see, that the set is a generating set of the semilattice. Then the following equalities are hold:
By Statement b) of the Theorem 1.2 follows that the following conditions are true:
i.e., the inclusions are always hold. Further, it is to see, that the following conditions are true:
i.e., are nonlimiting elements of the sets, , and respectively. By Statement c) of the Theorem 1.2 it follows, that the conditions, , and are hold. Since, we have and.
Therefore the following conditions are hold:
The lemma is proved.
Definition 2.1. Assume that. Denote by the symbol the set of all regular elements of the semigroup, for which the semilattices and are mutually -isomorphic and.
It is easy to see the number of automorphism of the semilattice is equal to 2.
Theorem 2.2. Let, and. If be finite set, and the -semilattice and are -isomorphic, then
Proof. Assume that. Then a quasinormal representation of a regular binary relation has the form
where and by Lemma 2.3 satisfies the conditions: X
(3)
Let is a mapping the set X in the semilattice satisfying the conditions for all., , , , are the restrictions of the mapping on the sets respectively. It is clear, that the intersection disjoint elements of the set are empty set and.
We are going to find properties of the maps, , , ,.
1). Then by Property (3) we have, i.e., and by definition of the set. Therefore for all.
2). Then by Property (3) we have, i.e., and by definition of the set. Therefore for all.
3). Then by Property (3) we have, i.e., and by definition of the sets and. Therefore for all.
Preposition we have that, i.e. for some. If, then . So by definition of the sets. The condition contradict of the equality, while. Therefore, for some.
4). Then by Property (3) we have, i.e., and by definition of the sets and. Therefore for all.
Preposition we have that, i.e. for some. If, then. So by definition of the sets. The condition contradict of the equality, , while. Therefore, for some.
5). Then by definition quasinormal representation binary relation and by Property (3) we have, i.e. by definition of the sets. Therefore for all.
Therefore for every binary relation exist ordered system. It is obvious that for different binary relations exist different ordered systems.
Let, , , ,
are such mappings, which satisfying the conditions:
for all;
for all;
for all and for some;
for all and for some;
for all.
Now we define a map of a set in the semilattice, which satisfies the following condition:
Now let,. Then binary relation is written in the form
and satisfying the conditions:
From this and by Lemma 2.3 we have that.
Therefore for every binary relation and ordered system exist one to one mapping.
By Theorem 1.1 the number of the mappings are respectively:
(see ( [1] , Corollary 1.18.1), ( [2] , Corollary 1.18.1)).
The number of ordered system or number regular elements can be calculated by the formula
(see ( [1] , Theorem 6.3.5), ( [2] , Theorem 6.3.5)).
The theorem is proved.
Corollary 2.1. Let,. If be a finite set and be the set of all right units of the semigroup, then the following formula is true
Proof: This corollary immediately follows from Theorem 2.2 and from the ( [1] , Theorem 6.3.7) or ( [2] , Theorem 6.3.7).
The corollary is proved.