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.