Applied Mathematics
Vol.07 No.01(2016), Article ID:63138,10 pages
10.4236/am.2016.71009
Generating Set of the Complete Semigroups of Binary Relations
Yasha Diasamidze1, Neset Aydin2, Ali Erdoğan3
1Shota Rustavelli University, Batumi, Georgia
2Çanakkale Onsekiz Mart University, Çanakkale, Turkey
3Hacettepe University, Ankara, Turkey
Copyright © 2016 by authors and Scientific Research Publishing Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY).
http://creativecommons.org/licenses/by/4.0/
Received 16 December 2015; accepted 25 January 2016; published 28 January 2016
ABSTRACT
Difficulties encountered in studying generators of semigroup of binary relations defined by a complete X-semilattice of unions D arise because of the fact that they are not regular as a rule, which makes their investigation problematic. In this work, for special D, it has been seen that the semigroup
, which are defined by semilattice D, can be generated by the set
.
Keywords:
Semigroups, Binary Relation, Generated Set, Generators
1. Introduction
Theorem 1. 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:
(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, 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 com- pleteness source either does not exist or is always greater than one (see [1] , Chapter 11). Some positive results in this direction can be found in [2] -[6] .
Let be parameters in the formal equalities,
and
(2)
(3)
The representation of the binary relation of the form
and
will be called subquasinormal and maximal subquasinormal.
If and
are the subquasinormal and maximal subquasinormal representations of the binary relation
, then for the binary relations
and
the following statements are true:
a)
b)
c) the subquasinormal representation of the binary relation is quasinormal;
d) if
then is a mapping of the family of sets
in the X-semilattice of unions
.
e) if is a mapping satisfying the condition
for all
, then
2. Results
Proposition 2. Let. Then
Proof. It is easy to see the inclusion holds, since
. If
, then
for some
. So,
since
and
.Then
for some k
i.e.
and
. For the last conditionfollows that
. We have
and
. Therefore, the inclusion
is true. Of this and by inclusion
follows that the equality
holds. ,
Corollary 1. If and
, then
.Proof. We have
and
. Of this follows that
since
. ,
Let the X-semilattice of unions given by the diagram of Figure 1. Formal equalities of the given semilattice have a form:
Figure 1. Diagram of D.
(4)
The parameters P1, P2, P3 are basis sources and the parameters are completeness sources, i.e.
.
Example 3. Let,
,
,
,
. Then for the for-
mal equalities of the semilattice D follows that,
,
,
,
,
, and
Then we have:
Theorem 4. Let the X-semilattice of unions given by the diagram of Figure 1,
and
. Then the set B is generating set of the semigroup
.
Proof. It is easy to see that since
and
. Now, let
be any binary rela- tion of the semigroup
;
,
and
. Then the equality
(
is subquasinormal representation of a binary relation
) is true. By assumption
, i.e. the quasinormal representation of a binary relation
have a form
Of this follows that
(5)
For the binary relation we consider the following case.
a) Let. Then
, where
. By element T we consider the following cases:
1.. In this case suppose that
and are mapping of the set
on the set
. Then
(6)
where, then it is easy to see, that
since
. From the formal equality and equalities (6) and (5) we have:
since.
2.. In this case suppose that
and are mapping of the set
in the set D. Then
(7)
where, then it is easy to see, that
since
. From the formal equality and equalities (7) and (5) we have:
b). Then
since is X-semilattice of unions. For the semilattice of unions
consider the following cases.
1. Let, where,
. Then binary relation
has representation of the form
. In this case suppose that
and are mapping of the set
on the set
. Then
(8)
where,
and
, then it is easy to see, that
since
. From the formal equality and equalities (8) and (5) we have:
2. Let, where,
. Then binary relation
has representation of the
form. In this case suppose that
and are mapping of the set
on the set
. Then
(9)
where,
and
, then it is easy to see, that
since
. From the formal equality and equalities (9) and (5) we have:
c). Then
since is X-semilattice of unions. For the semilattice of unions
consider the following cases.
1. Let. Then binary relation
has representation of the form
. In this case suppose that
and are mapping of the set
on the set
. Then
(10)
where,
,
and
, then it is easy to see, that
since
. From the formal equality and equalities (10) and (5) we have:
2. Let. Then binary relation
has representation of the form
. In this case suppose that
and are mapping of the set
on the set
. Then
(11)
where,
,
and
, then it is easy to see, that
since
. From the formal equality and equalities (11) and (5) we have:
3. Let. Then binary relation
has representation of the form
. In this case suppose that
and are mapping of the set
on the set
. Then
(12)
where,
,
and
, then it is easy to see, that
since
. From the formal equality and equalities (12) and (5) we have:
4. Let. Then binary relation
has representation of the form
. In this case suppose that
and are mapping of the set
on the set
. Then
(13)
where,
,
and
, then it is easy to see, that
since
. From the formal equality and equalities (13) and (5) we have:
5. Let. Then binary relation
has representation of the form
. In this case suppose that
and are mapping of the set
on the set
. Then
(14)
where,
,
and
, then it is easy to see, that
since
. From the formal equality and equalities (14) and (5) we have:
6. Let. Then binary relation
has representation of the form
. In this case suppose that
and are mapping of the set
on the set
. Then
(15)
where,
,
and
, then it is easy to see, that
since
. From the formal equality and equalities (15) and (5) we have:
7. Let. Then binary relation
has representation of the form
. In this case suppose that
and are mapping of the set
on the set
. Then
(16)
where,
,
,
and
, then it is easy to see, that
since
. From the formal equality and equalities (16) and (5) we have:
,
Cite this paper
YashaDiasamidze,NesetAydin,AliErdoğan, (2016) Generating Set of the Complete Semigroups of Binary Relations. Applied Mathematics,07,98-107. doi: 10.4236/am.2016.71009
References
- 1. Diasamidze, Ya. and Makharadze, Sh. (2013) Complete Semigroups of Binary Relations. Cityplace Kriter, Country-Region Turkey, 520 p.
- 2. Davedze, M.Kh. (1968) Generating Sets of Some Subsemigroups of the Semigroup of All Binary Relations in a Finite Set. Proc. A. I. Hertzen Leningrad State Polytechn. Inst., 387, 92-100. (In Russian)
- 3. Davedze, M.Kh. (1971) A Semigroup Generated by the Set of All Binary Relations in a Finite Set. XIth All-Union Algebraic Colloquium, Abstracts of Reports, Kishinev, 193-194. (In Russian)
- 4. Davedze, M.Kh. (1968) Generating Sets of the Subsemigroup of All Binary Relations in a Finite Set. Doklady AN BSSR, 12, 765-768. (In Russian)
- 5. Givradze, O. (2010) Irreducible Generating Sets of Complete Semigroups of Unions Defined by Semilattices of Class . Proceedings of the International Conference “Modern Algebra and Its Aplications”, Batumi.
- 6. Givradze, O. (2011) Irreducible Generating Sets of Complete Semigroups of Unions Defined by Semilattices of Class in Case, When and . Proceedings of the International Conference “Modern Algebra and Its Aplications”, Batumi.