Regular Elements of Bx(D) Defined by the Class ∑1(X,10)-I

Show more

Received 15 January 2016; accepted 24 May 2016; published 27 May 2016

1. Introduction

Let D be a nonempty set of subsets of a given set X, closed under union. Such a set D is called a complete X-semilattice of unions. For any map f from X to D, we define a binary relation.

The set of all, denoted by, is a subsemigroup of semigroup of all binary relations on X. (See [1] - [6] .)

All notations, symbol and required definitions used in this work can be found in [7] . Recall the following results.

Lemma 1. [1] , Corollary 1.18.1. Let and be two sets where and. Then the number of all possible mappings from Y to subsets of such that is given by.

Theorem 1. [1] , Theorem 1.18.1. Let. Let be nonempty sets. Then the number

of mappings from X to such that for some is equal to.

2. Results

Let X be a nonempty set, D a X-semilattice of union with the conditions (see Figure 1);

(1)

The class of X-semilattices where each element is isomorphic to D is denoted by.

An element is called regular if for some. Our aim in this work is to identify all regular elements of where D is given above.

Definition 1. The complete X-semilattice of unions is called an XI-semilattice of unions if

and for any nonempty Z in D. Here is an exact lower bound of in D where

The following Lemma is well known (see [7] , Lemma 3).

Lemma 2. All semilattices in the form of the diagrams in Figure 2 are XI-semilattices.

Figure 1. Diagram of semilattice of unions D.

Figure 2. Diagram of all XI-subsemilattices of D.

Definition 2. Let and be two X-semilattices of unions. A one to one map from to is said to be a complete isomorphism if

for

Definition 3. [1] , Definition 6.3.3. Let. We say that a complete isomorphism is a complete a-isomorphism if

a)

b) for and for any.

The following subsemilattices are all XI-semilattices of the X-semilattices of unions D.

a), where (see diagram 1 of the Figure 3);

b) where and (see diagram 2 of the Figure 3);

c) where and (see diagram 3 of the Figure 3);

d) where and (see diagram 4 of the Figure 3);

e) where, , , , , (see diagram 5 of the Figure 3);

f) where, , , , ,

(see diagram 6 of the Figure 3);

g), where, , , , , (see diagram 7 of the Figure 3);

h), where, , , , , , (see diagram 8 of the Figure 3);

For each we set

One can see that

Assume that and denote by the symbol the set of all regular elements a of the semigroup

Figure 3. Diagram of all subsemilattices isomorphic to subsemilattices in Figure 2.

, for which the semilattices and are mutually a-isomorphic and and

(see [1] , Definition 6.3.5).

The following results have the key role in this study.

Theorem 2. Let be the set of all regular elements of the semigroup. Then the following state- ments are true:

a) for any and;

b);

c) if X is a finite set, then (see [1] , Theorem 6.3.6).

Lemma 3. Let be isomorphism between and semilattices, , and. If X is a finite set and , then the following equalities are true:

a)

b)

c)

d)

e)

f)

g)

h)

Proof. The propositions a), b), c) and d) immediately follow from ( [1] , Theorem 6.3.5 and Theorem 13.1.2), while the equalities e), f), g) and h) follow from ( [1] , Theorem 6.3.5, Corolaries 13.3.4-5-6 and 13.7.3). □

3. Regular Elements of the Complete Semigroups of Binary Relations of the Class , When and

Theorem 3. Let and. Then a binary relation a

of the semigroup whose quasinormal representation has the form will be a

regular element of this semigroup iff there exist a complete a-isomorphism of the semilattice on some subsemilattice of the semilattice D which satisfies at least one of the following conditions:

a), for some;

b), for some, and which satisfies the condi- tions:,;

c), for some, , and which satisfies the conditions:, , ,;

d), for some, and

which satisfies the conditions:, , , , ,;

e), where, , ,

, , and satisfies the conditions:,

, ,;

f), where, ,

, , and satisfies the conditions:, ,

, , , ,;

g), where,

, , , and satisfies the conditions:, , , ,;

h), where

, , , and satisfies the conditions:, , , , , , .

Proof. In this case from Lemma 2 it follows that diagrams 1-8 given in Figure 2 exhaust all diagrams of XI-subsemilattices of the semilattice D. A quasinormal representation of regular elements of the semigroup, which are defined by these XI-semilattices, may have one of the form listed above. Then the validity of theorem immediately follows from ( [1] , Theorem 13.1.1, Theorem 13.3.1 and Theorem 13.7.1). □

Lemma 4. Let and. Let be set of all regular elements of such that each element satisfies the condition of a) of Theorem 3. Then.

Proof. Let binary relation a of the semigroup satisfy the condition a) of Theorem 3. Then quasinormal representation of a binary relation a has a form for some. It is easy to see that for all, i.e. binary relation a is a regular element of the semigroup. Therefore

□

Now let binary relation a of the semigroup satisfy the condition b) of Theorem 3 (see diagram 2 of the Figure 3). In this case we have where and. By definition of the semi- lattice D it follows that

It is easy to see that there is only one isomorphism from to itself. That is and. If

then

(2)

Lemma 5. Let X be a finite set,

and. Let be the set of all regular elements of such that each element satisfies the condition b) of Theorem 3. Then

Proof. Let, , and. Then quasinormal representation of a binary relation a has a form for some , and by state- ment b) of theorem 3 satisfies the conditions and. By definition of the semilattice D we have and, i.e., and. It follows that. Therefore we have

(3)

From this equality and by statement b) of Lemma 3 it immediately follows that

□

Let binary relation a of the semigroup satisfy the condition c) of Theorem 3 (see diagram 3 of the Figure 3). In this case we have, where and. By definition of the semilattice D it follows that

It is easy to see and. If

then

(4)

Lemma 6. Let X be a finite set,

and. Let be the set of all regular elements of such that each element satisfies the condition c) of Theorem 3. Then

where

Proof. Let be arbitrary element of the set and. Then quasinormal representation of a binary relation a has a form for some , and by statement c) of Theorem 3 satisfies the conditions, , and. By definition of the semilattice D we have,. From this and by the condition, , , we have

i.e., where. It follows that, From the last inclusion and by definition of the semilattice D we have for all, where

Therefore the following equality

(5)

holds. Now, let, and. Then

for the binary relation a we have

From the last condition it follows that.

1). Then we have that. But the inequality contradicts the condition that representation of binary relation a is quasinormal. So, the equality is true. From the last equality and by definition of the semilattice D we have for all, where

2), , , ,

and are true. Then we have

and

respectively, i.e., or if and only if

Therefore the equality is true. From the last equality and by definition of the semilattice D we have for all, where

3),

, , , and are true. Then we have

and

respectively, i.e., and if and only if

Therefore the equality is true. From the last equality and by definition of the semilattice D we have

for all, where

Now, by equality (4) and conditions 1), 2) and 3) it follows that the following equality is true

where

□

Lemma 7. Let, where and. If quasinormal repre-

sentation of binary relation a of the semigroup has a form for

some, and, then iff

Proof. If, then by statement c) of Theorem 3 we have

(6)

From the last condition we have

(7)

since by assumption.

On the other hand, if the conditions of (7) holds, then (6) immediately follows, i.e.. Lemma is proved. □

Lemma 8. Let, and X be a finite set. Then the following equality holds

Proof. Let, where. Assume that

and a quasinormal representation of a regular binary relation a has a form for some, and. Then ac- cording to Lemma 7, we have

(8)

Further, let be a mapping of the set X in the semilattice D satisfying the conditions for all., , and are the restrictions of the mapping on the sets, , , respectively. It is clear that the intersection of elements of the set is an empty set, and. We are going to find properties of the maps, , ,.

1). Then by the properties (1) we have, i.e., and by definition of the set. Therefore for all.

2). Then by the properties (1) 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. That is contradiction to the equality, while by definition of the se- milattice D.

Therefore for some.

3). Then by properties (1) 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 by definition of the set and. We have contradiction to the equality.

Therefore for some.

4). Then by definition of a quasinormal representation of a binary relation a and by property (1) we have, i.e. by definition of the sets and. There- fore for all.

We have seen that for every binary relation there exists ordered system . It is obvious that for disjoint binary relations there exist disjoint ordered systems.

Further, let

be such mappings that satisfy the conditions:

for all;

for all and for some;

for all and for some;

for all.

Now we define a map f from X to the semilattice D, which satisfies the condition:

Further, let, , and. Then

binary relation may be represented by

and satisfies the conditions

.

(By suppose for some and for some), i.e., by lemma 7 we have that.

Therefore for every binary relation and ordered system there exists one to one mapping.

By Lemma 1 and by Theorem 1 the number of the mappings are respectively

Note that the number does not depend on choice of chains

of the semilattice D. Since the number of such different chains of the semilattice D is equal to 22, for arbitrary where, the number of regular elements of the set is equal to

□

Therefore we obtain

(9)

Lemma 9. Let X be a finite set, and. Let be set of all regular elements of such that each element satisfies the condition c) of Theorem 3. Then

Proof. The given Lemma immediately follows from Lemma 6 and from the Equalities (5).

Now let a binary relation a of the semigroup satisfy the condition (d) of Theorem 3 (see diagram 4

of the Figure 3). In this case we have where and. By de-

finition of the semilattice D it follows that

It is easy to see and. If

then

(10)

Lemma 10. Let X be a finite set,

and. Let be set of all regular elements of such that each element satisfies the condition d) of Theorem 3. Then

Proof. Let, and. Then

, where, and the following inclusions and inequalities are true

From this it follows that

We consider the following cases.

1) or. Then we have. But the inequality contradicts the condition that representation of binary relation a is quasinormal. So,

the equality holds. From the last equality and by definition of the semilattice D we have

for all, where

(10a)

2) or Then we have or

. But the inequality or

contradicts the condition that representation of binary relation a is quasinormal. So, the equality holds. From the last equality and by definition of the semilattice D we have for all, where

(10b)

By conditions (10a) and (10b) it follows that

From the last equality we have that the given Lemma is true. □

Now let a binary relation a of the semigroup satisfy the condition e) of Theorem 3 (see diagram 5 of the Figure 3). In this case we have where and and. By definition of the semilattice D it follows that

It is easy to see and. If

then

(11)

Lemma 11. Let X be a finite set,

and. Let be set of all regular elements of such that each element satisfies the condition e) of Theorem 3. Then

where

Proof. Let be arbitrary element of the set and. Then quasinormal representation of a binary relation a of the semigroup has a form

where, , , , and by statement e) of Theorem 3 satisfies the following conditions

From this we have that the inclusions

are fulfilled. Therefore from the Equality (1) it follows that

(12)

Let and be such elements of the set that and. Then quasinormal representation of a binary relation a of the semigroup has a form

where, , , , and by statement e) of Theorem 3 satisfies the following conditions

, , and.

Then by statement e) of Theorem 3 we have

From this conditions it follows that

For and we consider the following cases.

1) or. Then or

respectively. But the inequalities and contradict the condition that representation of binary relation a is quasinormal. So, the equality holds. From the last equality it follows that for all, where

2) or. Then by definition of the semilattice D it

follows that the inequalities,

or,

are true respectively. But the inequalities

and contradict the condition that representation of binary relation a is quasinormal. So,

the equality holds. From the last equality, by definition of the semilattice D it follows

that for all, where

3) If, then

Then by definition of the semilattice D it follows that the inequalities

are true. But the inequalities contradict the condition that representation of binary relation a is quasinormal. So, the equality holds. From the last equality it follows that, where

By similar way one can prove that for any.

4), and are such elements of the set that, , , and, then by statement e) of theorem 3 satisfies the following conditions:

and

respectively, i.e., or if and only if

Therefore, the equality is true. From the last equality by de- finition of the semilattice D it follows that for all, where

From the equalities and

given above it follows that

where

□

Lemma 12. Let and be arbitrary elements of the set, where, and. If quasinormal representation of binary relation a

of the semigroup has a form, for some

, , and, then iff

Proof. If, then by statement e) of Theorem 3 we have

(13)

From the last condition we have

(14)

since and by supposition.

On the other hand, if the conditions of (14) hold, then the conditions of (13) follow, i.e..

□

Lemma 13. Let and be arbitrary elements of the set , where, and. Then the following equality holds:

Proof. Let and be arbitrary elements of the set , where, and. If. Then quasinormal repre- sentation of a binary relation a of semigroup has a form

for some, , , and by the lemma 12 satisfies the conditions

(15)

Now, let be a mapping from X to the semilattice D satisfying the conditions for all., , and are the restrictions of the mapping on the sets respectively. It is clear that the intersection of elements of the set is an empty set and

We are going to find properties of the maps, , and.

(1). Then by the properties (1) we have

since i.e., and by definition of the set. Therefore for all.

(2). Then by the properties (1) we have, i.e., and by definition of the set and. Therefore for all.

By suppose we have that, i.e. for some. Then since. If, then. Therefore. That contradicts the equality, while and by definition of the semilattice D.

Therefore for some.

(3). Then by the properties (1) we have, i.e., and by definition of the set and. Therefore for all.

By suppose we have that, i.e. for some. Then since. If then. Therefore. That contradicts the equality, while and by definition of the semilattice D.

Therefore for some.

(4). Then by definition quasinormal representation of a binary relation a and by property (1) we have, i.e. by definition of the sets, and. Therefore for all.

Therefore for every binary relation there exists ordered system. It is obvious that for disjoint binary relations there exists disjoint ordered systems.

Further, let

be such mappings, which satisfy the conditions

for all;

for all and for some;

for all and for some;

for all.

Now we define a map f from X to the semilattice D, which satisfies the condition

Further, let, , , and

. Then binary relation may be represented by

and satisfies the conditions

(By suppose for some and for some), i.e., by lemma 12 we have that. Therefore for every binary relation and ordered system there exists one to one mapping.

The number of the mappings, , and are respectively

Note that the number does not depend on choice of

elements of the semilattice D, where, , and. Since the number of such different elements of the form of the semilattice D are equal to 24, the number of regular elements of the set is equal to

Lemma 14. Let X be a finite set,

□

and. Let be set of all regular elements of such that each element satisfies thecondition e) of Theorem 3. Then, where

and

Proof. The given Lemma immediately follows from Lemma 11 and Lemma 13.

□Let binary relation a of the semigroup satisfy the condition g) of Theorem 3 (see diagram 7 of the Figure 3). In this case we have, where, and. By definition of the semilattice D it follows that

It is easy to see and. If

(see Figure 4).

Figure 4. Diagram of all subsemilattices isomorphic to 7 in Figure 2.

Then

(16)

Lemma 15. Let X be a finite set, and. Let

be set of all regular elements of such that each element satisfies the condition f) of Theorem 3. Then

Proof. Let, and . Then quasinormal representation of a binary relation a of the semigroup has a form

where, and and by statement f) of theorem 3 satisfies the following conditions

From this conditions it follows that

For and we consider the following case.

or. Then

or

But the inequality and contradict the condition that representation of binary relation a is quasinormal. So, the equality holds. From the last equality by definition of the semilattice D it follows that for all, where

(17)

Now by Equalities (16) and by condition (17) it follows that

By statement f) of Lemma 3 the given Lemma is true.

□Now let binary relation a of the semigroup satisfy the condition f) of Theorem 3 (see diagram 6 of the Figure 3). In this case we have, where, and. By definition of the semilattice D it follows that

It is easy to see and. If

(see Figure 5).

Then

Lemma 16. Let X be a finite set, and. Let be set of all regular elements of such that each element satisfies the condition g) of Theorem 3. Then

Proof. Let, and . Then quasinormal representation of a binary relation a of the semigroup has a form

Figure 5. Diagram of all subsemilattices isomorphic to 6 in Figure 2.

where, and and by statement g) of Theorem 3 satisfies the following conditions

From this conditions it follows that

For and we consider the following cases.

1) or. Then

or

But the inequalities and contradicts the condition that repre- sentation of a binary relation a is quasinormal. So, the equality holds. From the last equality by definition of the semilattice D it follows that for all, where

2) or. Then

or

But the inequalities and contradicts the condition that repre- sentation of a binary relation a is quasinormal. So, the equality holds. From the last equality by definition of the semilattice D it follows that for all, where

3) or . Then

or

But the inequalities and contradicts the condition that repre- sentation of a binary relation a is quasinormal. So, the equality holds. From the last equality by definition of the semilattice D it follows that for all, where

Now by conditions 1), 2) and 3) it follows that

By statement (g) of Lemma 3 the given Lemma is true.

□Let binary relation a of the semigroup satisfy the condition h) of Theorem 3 (see diagram 8 of the Figure 3). In this case we have, where,. By definition of the semilattice D it follows that

It is easy to see and. If

(see Figure 6).

Then

Lemma 17. Let X be a finite set, and. Letbe set of all regular elements of such that each element satisfies the condition h) of Theorem 3. Then

Figure 6. Diagram of all subsemilattices isomorphic to 8 in Figure 2.

Proof. Let, where,

, and. Then quasinormal representation of a

binary relation a of the semigroup has a form

where, , and by statement g) of Theorem 3 sa- tisfies the following conditions

From this conditions it follows that

For and we consider the following case.

. Then. But the inequality

contradicts the condition that representation of binary relation a is quasinormal. So,

the equality holds. From the last equality by definition of the semilattice D it follows that

for all, where

Therefore we have

By statement h) of Lemma 3 the given Lemma is true. □

Let us assume that

Theorem 4. Let,. If X is a finite set and is a set of all regular elements of the semigroup then.

Proof. This Theorem immediately follows from Theorem 2 and Theorem 3. □

Example 1. Let,

Then, , , , , , , , and .

We have, , , , , , , ,.

References

[1] Diasamidze, Ya. and Makharadze, Sh. (2013) Complete Semigroups of Binary Relations. Cityplace Kriter, Country- Region Turkey, 520 p.

[2] Diasamidze, Ya. and Makharadze, Sh. (2010) Complete Semigroups of Binary Relations. (Russian) Sputnik+, Cityplace Moscow, 657 p.

[3] Diasamidze, Ya. (2002) To the Theory of Semigroups of Binary Relations. Proceedings of A. Razmadze Mathematical Institute, 128, 1-15.

[4] Diasamidze, Ya. (2002) Right Units in the Semigroups of Binary Relations. Proceedings of A. Razmadze Mathematical Institute, 128, 17-36.

[5] Diasamidze, Ya.I. (2003) Complete Semigroups of Binary Relations. Journal of Mathematical Sciences (New York), 117, 4271-4319.

http://dx.doi.org/10.1023/A:1025030132270

[6] Diasamidze, Ya.I., Makharadze, Sh.I. and Diasamidze, I.Ya. (2008) Idempotents and Regular Elements of Complete Semigroups of Binary Relations. Algebra and Geometry. Journal of Mathematical Sciences (New York), 153, 481-494.

http://dx.doi.org/10.1007/s10958-008-9132-1

[7] Makharadze, Sh., Aydin, N. and Erdogan, A. (2015) Complete Semigroups of Binary Relations Defined by Semilattices of the Class ∑_{1}(X,10). Applied Mathematics, 6, 274-294.

http://dx.doi.org/10.4236/am.2015.62026