We will investigate the properties of regular elements of the complete semigroup of binary relations
satisfying
. For the case where X is a finite set we derive formulas by means of which we can calculate the numbers of regular elements and right units of the respective semigroup.
Keywords:
1. Introduction
Let X be an arbitrary nonempty set and D be an X-semilattice of unions, which means a nonempty set of subsets of the set X that is closed with respect to the set-theoretic operations of unification of elements from D. Let’s denote an arbitrary mapping from X into D by f. For each f there exists a binary relation
on the set X that
satisfies the condition
. Let denote the set of all such
by
. It
is not hard to prove that
is a semigroup with respect to the operation of multiplication of binary relations.
is called a complete semigroup of binary relations defined by a X-semilattice of unions D (see [1] , Item 2.1), ([2] , Item 2.1]).
An empty binary relation or an empty subset of the set X is denoted by
. The form
is used to express that
. Also, in this paper following conditions are used
,
,
,
,
and
. Moreover, following sets are denoted by given symbols:
![]()
And
is an exact lower bound of the set
in the semilattice D.
Definition 1.1. Let
. If
or
for any
, then
is called an idempotent element or called right unit of the semigroup
respectively (see [1] -[3] ).
Definition 1.2. An element
taken from the semigroup
called a regular element of the semigroup
if in
there exists an element
such that
(see [1] -[4] ).
Definition 1.3. We say that a complete X-semilattice of unions D is an XI-semilattice of unions if it satisfies the following two conditions:
1)
for any
;
2)
for any nonempty element Z of D (see [1] , definition 1.14.2), ([2] definition 1.14.2), [5] or [6] .
Definition 1.4. Let D be an arbitrary complete X-semilattice of unions,
and
. If
![]()
then it is obvious that any binary relation
of a semigroup
can always be written in the form
the sequel, such a representation of a binary relation
will be 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:
1)
, for any
and
;
2)
(see [1] , definition 1.11.1), ([2] , definition 1.11.1).
Definition 1.5. We say that a nonempty element T is a nonlimiting element of the set D' if
and a nonempty element T is a limiting element of the set D' if
(see [1] , definition 1.13.1 and definition 1.13.2), ([2] , definition 1.13.1 and definition 1.13.2).
Definition 1.6. The one-to-one mapping
between the complete X-semilattices of unions
and
is called a complete isomorphism if the condition
![]()
is fulfilled for each nonempty subset D1 of the semilattice D' (see [1] , definition 6.3.2), ([2] definition 6.3.2) or [5] ).
Definition 1.7. Let
be some binary relation of the semigroup
. We say that the complete isomorphism
between the complete semilattices of unions Q and D' is a complete
-isomorphism if
1)
;
2)
for
and
for eny
(see [1] , definition 6.3.3), ([2] , definition 6.3.3).
Lemma 1.1. Let
and
be any two sets. Then the number
of all possible mappings of Y into any subset
of the set that Dj such that
can be calculated by the formula
(see [1] , Corollary 1.18.1), ([2] , Corollary 1.18.1).
Lemma 1.2. Let D by a complete X-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
, X and Y- be three such sets, that
. If f is such mapping of the set X, in the set Dj, for which
for some
, then the number s of all those mappings f of the
set X in the set Dj is equal to
(see [1] , Theorem 1.18.2), ([2] , Theorem 1.18.2).
Theorem 1.2. Let
be some finite X-semilattice of unions and
be the family of sets of pairwise nonintersecting subsets of the set X. If
is a mapping of the semilattice D 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 D are represented in the form (*), then among the parameters Pi
there exist such parameters that cannot be empty sets for D. Such sets Pi
are called basis sources, whereas sets Pi
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 [4] ).
Theorem 1.3. Let D be a complete X-semilattice of unions. The semigroup
possesses a right unit iff D is an XI-semilattice of unions (see [1] , Theorem 6.1.3, [2] , Theorem 6.1.3, [7] or [8] ).
Theorem 1.4. Let
. A binary relation
is a regular element of the semigroup
iff the complete X-semilattice of unions
satisfies the following two conditions:
1)
;
2)
is a complete XI-semilattice of unions (see [1] Theorem 6.3.1), ([2] , Theorem 6.3.1).
Theorem 1.5. Let D be a finite X-semilattice of unions and
for some
and
of the semigroup
;
be the set of those elements T 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 XI-semilattice of
unions and for
-isomorphism
of the semilattice
on some X-subsemilattice D' of the semilattice D the following conditions are fulfilled:
1)
for any
;
2)
for any
;
3)
for any element T of the set
(see [1] , Theorem 6.3.3), ([2] , Theorem 6.3.3) or [5] ).
2. Results
Let D be arbitrary X-semilattice of unions and
, which satisfies the following conditions:
(1)
Figure 1 is a graph of semilattice Q, where the semilattice Q satisfies the conditions (1). The symbol
is used to denote the set of all X-semilattices of unions, whose every element is isomorphic to Q.
P7, P6, P5, P4, P3, P2, P1, P0 are pairwise disjoint subsets of the set X and let
be a family sets, also
![]()
is a mapping from the semilattice Q into the family sets
. Then we have following formal equalities of the semilattice Q:
(2)
Note that the elements P1, P2, P3, P6 are basis sources, the element P0, P4, P5, P7 is sources of completenes of the semilattice Q. Therefore
and
(see Theorem 1.2).
Theorem 2.1. Let
. Then Q is XI-semilattice
Proof. Let
,
and
is the exact lower bound of the set Qt in Q. Then from the formal equalities (2) we get that
![]()
We have
,
for all t and
,
,
. The semilattice Q, which has diagram of Figure 1, is XI-semilattice, which follows from the Definition 1.3.
Theorem is proved.
Lemma 2.1. Let
. Then following equalities are true:
![]()
Proof. This Lemma follows directly from the formal equalities (2) of the semilattice Q.
Lemma is proved.
Lemma 2.2. Let
. Then the binary relation
![]()
is the largest right unit of the semigroup
.
Proof. From preposition and from Theorem 2.1 we get that Q is XI-semilattice. To prove this Lemma we will use Lemma 1.2, lemma 2.1, and Theorem 1.3, from where we have that the following binary relation
![]()
is the largest right unit of the semigroup
.
Lemma is proved.
Lemma 2.3. Let
. Binary relation
having quazinormal representation of the form
![]()
where
and
is a regular element of the semigroup
iff for some complete
-isomorphism
of the semilattice Q
on some X-subsemilattice
of the semilattice Q satisfies the following conditions:
![]()
Proof. It is easy to see, that the set
is a generating set of the semilattice Q. Then the following equalities are hold:
![]()
If we follow statement b) of the Theorem 1.5 we get that followings are true:
![]()
From the last conditions we have that following is true:
![]()
![]()
Moreover, the following conditions are true:
![]()
![]()
![]()
![]()
![]()
![]()
The elements
are nonlimiting elements of the sets
,
,
and ![]()
respectively. The proof of condition
,
,
and
comes from the statement c) of the Theorem 1.5
Therefore the following conditions are hold:
![]()
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 Q' and Q are mutually
-isomorphic and
.
Note that,
, where q is the number of automorphism of the semilattice Q.
Theorem 2.2. Let
and
. If X be finite set, and the
XI-semilattice Q and
(see Figure 2) are
-isomorphic, then
![]()
Proof. Assume that
. Then a quasinormal representation of a regular binary relation
has the form
![]()
where
and by Lemma 2.2 satisfies the conditions:
(3)
Father, let
is a mapping the set X in the semilattice Q satisfying the conditions
for all
.
,
,
,
,
and
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 properties (3) we have
, i.e., ![]()
and
by definition of the set
. Therefore
for all
.
2)
. Then by properties (3) we have
, i.e.,
and
by
definition of the set
and
. Therefore
for all
.
By suppose we have that
, i.e.
for some
. If
. Then
.
Therefore
. That is contradict of the equality
, while
,
and
by definition of the semilattice Q. Therefore
for some
.
3)
. Then by properties (3) we have
![]()
i.e.,
and
by definition of the sets
and
. Therefore
for all
.
By suppose we have, that
, i.e.
for some
. If
then
. Therefore
. We have contradict of the equality
, since
.
Therefore
for some
.
4)
. Then by properties (3) we have
, i.e.,
and
by definition of the sets
,
, and
. Therefore
for all
.
By suppose we have, that
, i.e.
for some
. If
. Then
. Therefore
. We have contradict of the equality
, since
.
Therefore
for some
.
5)
. Then by properties (3) we have
, i.e.,
and
by definition of the sets
,
,
,
and
. Therefore
for all
.
By suppose we have, that
, i.e.
for some
. If
. Then
. Therefore
. We have contradict of the equal- ity
, since
.
Therefore
for some
.
6)
. 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 disjoint binary relations exist disjoint ordered systems.
Father, let
![]()
are such mappings, which satisfying the conditions:
7)
for all
;
8)
for all
and
for some
;
9)
for all
and
for some
;
10)
for all
and
for some
;
11)
for all
and
for some
;
12)
for all
.
Now we define a map f of a set X in the semilattice D, which satisfies the condition:
![]()
Father, let
,![]()
. Then binary relation
my be representation by form
![]()
and satisfying the conditions:
![]()
(By suppose
for some
;
for some
;
for some
;
for some
. 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 Lemma 1.1). The number of ordered system
or number idempotent elements of this case we my be calculated by formula
![]()
Theorem is proved.
Corollary 2.1. Let
, If X be a finite set and
be the set of all right units of the semigroup
, then the following formula is true
![]()
Proof: This Corollary directly follows from the Theorem 2.2 and from the [2, 3 Theorem 6.3.7].
Corollary is proved.