Generating Set of the Complete Semigroups of Binary Relations

Show more

Received 16 December 2015; accepted 25 January 2016; published 28 January 2016

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:

Figure 1. Diagram of D.

(4)

The parameters P_{1}, P_{2}, P_{3} 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:

,

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.