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 P_i there exist such parameters that cannot be empty sets for D. Such sets P_i are called basis sources, whereas sets P_i 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:

(4)

The parameters P₁, P₂, P₃ 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