Applied Mathematics
Vol.09 No.01(2018), Article ID:81845,11 pages
10.4236/am.2018.91002
Generating Sets of the Complete Semigroups of Binary Relations Defined by Semilattices of the Class
Bariş Albayrak1, Omar Givradze2, Guladi Partenadze2
1Department of Banking and Finance, School of Applied Sciences, Çanakkale Onsekiz Mart University, Çanakkale, Turkey
2Shota Rustaveli State University, Batumi, Georgia
Copyright © 2018 by authors and Scientific Research Publishing Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).
http://creativecommons.org/licenses/by/4.0/
Received: December 11, 2017; Accepted: January 16, 2018; Published: January 19, 2018
ABSTRACT
In this paper, we have studied generating sets of the complete semigroups defined by X-semilattices of the class
.
Keywords:
Semigroup, Semilattice, Binary Relations, Idempotent Elements
1. Introduction
Let X be an arbitrary nonempty set and D be a nonempty set of subsets of the set X. If D is closed under the union, then D is called a complete X-semilattice of unions. The union of all elements of the set D is denoted by the symbol
.
Let
be the set of all binary relations on X. It is well known that
is a semigroup.
Let f be an arbitrary mapping from X into D. Then we denote a binary relation
for each f. The set of all such binary relations is denoted
by
. It is easy to prove that
is a semigroup with respect to the product operation of binary relations. This semigroup
is called a complete semigroup of binary relations defined by an X-semilattice of unions D. This structure was comprehensively investigated in Diasamidze [1] and [2] . We assume that
,
,
,
and
. Then we denote following sets
Let
be finite X-semilattice of unions and
be the family of pairwise nonintersecting subsets of X. If
is a mapping from D on
, then the equalities
and
are valid. These equalities are called formal.
Let D be a complete X-semilattice of unions
. Then a representation
of a binary relation
of the form
is called quasinormal.
Let
be parameters in the formal equalities,
,
be mapping from
to
. Then
is called subquasinormal represantation of
. It can be easily seen that the following statements are true.
a)
b)
and
for some
.
c) Subquasinormal represantation of
is quasinormal.
d)
is mapping from
on
.
and
are respectively called normal and complement mappings for
.
Let
. If
for all
then
is called external element. Every element of the set
is an external element of
.
Theorem 1. [1] Let
be a finite set and
. If
is sub- quasinormal representation of
then
.
Corollary 1. [1] Let
. If
for
,
,
and subquasinormal representation of
then
.
It is known that the set of all external elements is subset of any generating set of
in [3] .
2. Results
In this work by symbol
we denote all semilattices
of the class
which the intersection of minimal elements
. This semilattices graphic is given in Figure 1. By using formal equalities, we have
. So, the formal equalities of the semilattice D has a form
Figure 1. Graphic of semilattice
which the intersection of minimal elements
.
(1)
Let
. If quasinormal representation of binary relation
has a form
then
We denote the set
It is easy to see that
.
Lemma 2. Let
. Then following statements are true for the sets
.
a) If
for some
, then
is product of some elements of the set
.
b) If
, then
.
c) If
, then
.
d) If
, then
.
e) If
, then
.
f) Every element of the set
is product of elements of the set
.
g) Every element of the set
is product of elements of the set
.
Proof. It will be enough to show only a, b and g. The rest can be similarly seen.
a. Let
for some
,
. Then quasinormal representation of
has a form
where
. We suppose that
where
is normal mapping for
and
is com-
plement mapping of the set
on the set
. So,
since
. From the equalities (2.1) and definition of
b. Let
. Then
or
. If
then
for some
. In this case we have
where
. Also
is satisfied. So, we have
. On the other hand, if
then
is satisfied. Conversely, if
then quasinormal representation of
has a form
where
or
and
. We suppose that
. In this case, we have
for
. So, we have
. Now suppose that
and
. In this case, we have
. So,
.
g. From the statement c, we have that
where
by definition of
. Thus, every element of the set
is product of elements of the set
.
Lemma 3. Let
. If
then the following statements are true.
a) If
then
is product of elements of the set
.
b) If
then
is product of elements of the set
.
c) If
for some
, then
is product of elements of the
.
d) If
for some
, then
is product of elements of the
.
e) If
for some
, then
is product of elements of the
.
f) If
for some
, then
is product of elements of the
.
Proof. c. Let quasinormal representation of
has a form
where
. By definition of the semilattice D,
. We suppose that
and
. In this case, we suppose that
where
is normal mapping for
and
is comple-
ment mapping of the set
on the set
(by suppose
). So,
since
. Also,
and
since
. From the equalities (2.1) and definition of
we obtain that
Now, we suppose that
and
. In this case, we suppose that
where
is normal mapping for
and
is com-
plement mapping of the set
on the set
(by suppose
). So,
since
. Also,
and
since
. From the equalities (2.1) and definition of
we obtain that
Lemma 4. Let
,
and
. If
then the following statements are true
a) If
for some
, then
is product of elements of the
.
b) If
for some
, then
is product of elements of the
.
c) If
for some
, then
is product of elements of the
.
Proof. First, remark that
,
,
,
,
.
a. Let
for some
. In this case, we suppose that
and
where
. It is easy to see that
and
is generating by elements of the
by statement b of Lemma 2. Also,
and
since
,
and
. So,
is product of elements of the
. □
Lemma 5. Let
and
.
If
then
is an irreducible generating set for the semigroup
.
Proof. First, we must prove that every element of
is product of elements of
. Let
and
where
and
,
. We suppose
that
. Then we have
. If
then
or
or
. Quasinormal representations of
and
has form
where
. So,
,
and
since
. From the definition of
and
we obtain that
That means,
and
are generated by
and
respectively. By using statement g and h of Lemma 3, we have
and
are generated by
. On the other hand, if
then
By using statement a of Lemma 3, we have
is product of some elemets of
.
So,
is generating set for the semigroup
. Now, we must prove that
is irreducible. Let
.
If
then
for all
from Lemma 2. So,
for all
. That means,
.
If
then the quasinormal representation of
has form
for some
. Let
for some
.
We suppose that
and
. By definition of
, quasinormal representation of
has form
where
. By using
and
we have
and
are minimal elements of the semilattice
. Also, we have
Since
and
are minimal elements of the semilattice
, this equality is possible only if
,
or
,
. By using formal equalities and
, we obtain
respectively. Let
and
. If
is sub-quasinormal representation of
then
and
where
is normal mapping for
and
is com-
plement mapping of the set
on the set
. From formal equalities, we obtain
and by using
and
, we have
This contradicts with
. So,
.
Now, we suppose that
and
. Similar operations are applied as above, we obtain
.
Now, we suppose that
and
. Similar operations are applied as above, we obtain
.
That means
for any
and
.
If
, then by the definition of
, quasinormal representation of
has a form
. Let
for some
.
We suppose that
and
. By definition of
, quasinormal representation of
has form
where
. By using
and
we have
and
are minimal elements of the semilattice
. Also, we have
From
and
are minimal elements of the semilattice
, this equality is possible only if
,
or
,
. By using formal equalities, we obtain
respectively. Let
and
where
. Then subquasinormal representation of
has one of the form
where
,
,
are normal mapping for
,
is complement mapping of the set
on the set
and
. From formal equalities, we obtain
and by using
, we have
This contradicts with
. So,
.
Now, we suppose that
and
. Similar operations are applied as above, we obtain
.
That means
for any
and
. □
Lemma 6. Let
,
and
. If
then
is irreducible generating set for the semigroup
.
Theorem 7. Let
,
and
. If
is a finite set and
then the following statements are true
a) If
then
b) If
then
Proof. Let
be a group,
and
be partitioning of
X. It is well known that
. If
then we have
If
are any two elements of partitioning of X and
where
and
, then the number of different binary relations
of semigroup
is equal to
(2)
If
are any three elements of partitioning of X and
where
are pairwise different elements of D, then the number of different binary relations
of semigroup
is equal to
(3)
If
are any four elements of partitioning of X and
where
are pairwise different elements of D, then the number of different binary relations
of semigroup
is equal to
(4)
Let
. Quasinormal represantation of
has form
where
. Also,
or
are partitioning of X for
. By using Equations (2.3) and (2.4) we obtain
Let
. Quasinormal represantation of
has form
where
. Also,
are partitioning of X. By using (2.2) we obtain
So, we have
since
. □
Acknowledgements
Sincere thanks to Prof. Dr. Neşet AYDIN for his valuable suggestions.
Cite this paper
Albayrak, B., Givradze, O. and Partenadze, G. (2018) Generating Sets of the Complete Semigroups of Binary Relations Defined by Semilattices of the Class
. Applied Mathematics, 9, 17-27. https://doi.org/10.4236/am.2018.91002
References
- 1. Diasamidze, Y. and Makharadze, S. (2013) Complete Semigroups of Binary Relations. Kriter Yay Nevi, Istanbul.
- 2. Diasamidze, Y., Ayd, N.N. and Erdogan, A. (2016) Generating Set of the Complete Semigroups of Binary Relations. Applied Mathematics, 7, 98-107. https://doi.org/10.4236/am.2016.71009
- 3. Bakuridze, A., Diasamidze, Y. and Givradze, O. Generated Sets of the Complete Semigroups of Binary Relations Defined by Semilattices of the Class Σ1(X, 2)(In Press)