Received 16 January 2015; accepted 6 February 2015; published 10 February 2015

ABSTRACT

In this paper we take subsemilattice of X-semilattice of unions D which satisfies the following conditions:

, , , , , , , , , , , , ,.

We will investigate the properties of regular elements of the complete semigroup of binary relations satisfying. For the case where X is a finite set we derive formulas by means of which we can calculate the numbers of regular elements and right units of the respective semigroup.

Keywords:

Semilattice, Semigroup, Regular Element, Right Unit, Binary Relation

1. Introduction

Let X be an arbitrary nonempty set and D be an X-semilattice of unions, which means a nonempty set of subsets of the set X that is closed with respect to the set-theoretic operations of unification of elements from D. Let’s denote an arbitrary mapping from X into D by f. For each f there exists a binary relation on the set X that

satisfies the condition. Let denote the set of all such by. It

is not hard to prove that is a semigroup with respect to the operation of multiplication of binary relations. is called a complete semigroup of binary relations defined by a X-semilattice of unions D (see [1] , Item 2.1), ([2] , Item 2.1]).

An empty binary relation or an empty subset of the set X is denoted by. The form is used to express that. Also, in this paper following conditions are used, , ,

, and. Moreover, following sets are denoted by given symbols:

And is an exact lower bound of the set in the semilattice D.

Definition 1.1. Let. If or for any, then is called an idem­potent element or called right unit of the semigroup respectively (see [1] -[3] ).

Definition 1.2. An element taken from the semigroup called a regular element of the semigroup if in there exists an element such that (see [1] -[4] ).

Definition 1.3. We say that a complete X-semilattice of unions D is an XI-semilattice of unions if it satisfies the following two conditions:

1) for any;

2) for any nonempty element Z of D (see [1] , definition 1.14.2), ([2] definition 1.14.2), [5] or [6] .

Definition 1.4. Let D be an arbitrary complete X-semilattice of unions, and . If

then it is obvious that any binary relation of a semigroup can always be written in the form

the sequel, such a representation of a binary relation will be called quasinormal.

Note that for a quasinormal representation of a binary relation, not all sets can be different from an empty set. But for this representation the following conditions are always fulfilled:

1), for any and;

2) (see [1] , definition 1.11.1), ([2] , definition 1.11.1).

Definition 1.5. We say that a nonempty element T is a nonlimiting element of the set D' if and a nonempty element T is a limiting element of the set D' if (see [1] , definition 1.13.1 and definition 1.13.2), ([2] , definition 1.13.1 and definition 1.13.2).

Definition 1.6. The one-to-one mapping between the complete X-semilattices of unions and is called a complete isomorphism if the condition

is fulfilled for each nonempty subset D₁ of the semilattice D' (see [1] , definition 6.3.2), ([2] definition 6.3.2) or [5] ).

Definition 1.7. Let be some binary relation of the semigroup. We say that the complete isomorphism between the complete semilattices of unions Q and D' is a complete -isomorphism if

1);

2) for and for eny (see [1] , definition 6.3.3), ([2] , definition 6.3.3).

Lemma 1.1. Let and be any two sets. Then the number of all possible mappings of Y into any subset of the set that D_j such that can be calculated by the formula (see [1] , Corollary 1.18.1), ([2] , Corollary 1.18.1).

Lemma 1.2. Let D by a complete X-semilattice of unions. If a binary relation of the form

is right unit of the semigroup, then is the greatest right

unit of that semigroup (see [1] , Lemma 12.1.2), ([2] , Lemma 12.1.2).

Theorem 1.1. Let, X and Y- be three such sets, that. If f is such mapping of the set X, in the set D_j, for which for some, then the number s of all those mappings f of the

set X in the set D_j is equal to (see [1] , Theorem 1.18.2), ([2] , Theorem 1.18.2).

Theorem 1.2. 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:

(*)

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 (*), 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 completeness source either does not exist or is always greater than one (see [1] , Item 11.4), ([2] , Item 11.4) or [4] ).

Theorem 1.3. Let D be a complete X-semilattice of unions. The semigroup possesses a right unit iff D is an XI-semilattice of unions (see [1] , Theorem 6.1.3, [2] , Theorem 6.1.3, [7] or [8] ).

Theorem 1.4. Let. A binary relation is a regular element of the semigroup iff the complete X-semilattice of unions satisfies the following two conditions:

1);

2) is a complete XI-semilattice of unions (see [1] Theorem 6.3.1), ([2] , Theorem 6.3.1).

Theorem 1.5. Let D be a finite X-semilattice of unions and for some and of the semigroup; be the set of those elements T of the semilattice which are nonlimiting elements of the set. Then a binary relation having a quasinormal representation of the form

is a regular element of the semigroup iff the set is a XI-semilattice of

unions and for -isomorphism of the semilattice on some X-subsemilattice D' of the semilattice D the following conditions are fulfilled:

1) for any;

2) for any;

3) for any element T of the set (see [1] , Theorem 6.3.3), ([2] , Theorem 6.3.3) or [5] ).

2. Results

Let D be arbitrary X-semilattice of unions and, which satisfies the following conditions:

(1)

Figure 1 is a graph of semilattice Q, where the semilattice Q satisfies the conditions (1). The symbol is used to denote the set of all X-semilattices of unions, whose every element is isomorphic to Q.

P₇, P₆, P₅, P₄, P₃, P₂, P₁, P₀ are pairwise disjoint subsets of the set X and let be a family sets, also

is a mapping from the semilattice Q into the family sets. Then we have following formal equalities of the semilattice Q:

(2)

Note that the elements P₁, P₂, P₃, P₆ are basis sources, the element P₀, P₄, P₅, P₇ is sources of completenes of the semilattice Q. Therefore and (see Theorem 1.2).

Theorem 2.1. Let. Then Q is XI-semilattice

Proof. Let, and is the exact lower bound of the set Q_t in Q. Then from the formal equalities (2) we get that

We have, for all t and, ,. The semilattice Q, which has diagram of Figure 1, is XI-semilattice, which follows from the Definition 1.3.

Theorem is proved.

Lemma 2.1. Let. Then following equalities are true:

Proof. This Lemma follows directly from the formal equalities (2) of the semilattice Q.

Lemma is proved.

Lemma 2.2. Let. Then the binary relation

is the largest right unit of the semigroup.

Proof. From preposition and from Theorem 2.1 we get that Q is XI-semilattice. To prove this Lemma we will use Lemma 1.2, lemma 2.1, and Theorem 1.3, from where we have that the following binary relation

is the largest right unit of the semigroup.

Lemma is proved.

Lemma 2.3. Let. Binary relation having quazinormal representation of the form

where and is a regular element of the semigroup

iff for some complete -isomorphism of the semilattice Q

on some X-subsemilattice of the semilattice Q satisfies the following conditions:

Proof. It is easy to see, that the set is a generating set of the semilattice Q. Then the following equalities are hold:

If we follow statement b) of the Theorem 1.5 we get that followings are true:

From the last conditions we have that following is true:

Moreover, the following conditions are true:

The elements are nonlimiting elements of the sets, , and

respectively. The proof of condition, , and comes from the statement c) of the Theorem 1.5

Therefore the following conditions are hold:

Lemma is proved.

Definition 2.1. Assume that. Denote by the symbol the set of all regular elements of the semigroup, for which the semilattices Q' and Q are mutually -isomorphic and.

Note that, , where q is the number of automorphism of the semilattice Q.

Theorem 2.2. Let and. If X be finite set, and the

XI-semilattice Q and (see Figure 2) are -isomorphic, then

Proof. Assume that. Then a quasinormal representation of a regular binary relation has the form

where and by Lemma 2.2 satisfies the conditions:

(3)

Father, let is a mapping the set X in the semilattice Q satisfying the conditions for all., , , , and are the restrictions of the mapping on the sets,

, , , , respectively. It is clear, that the intersection disjoint elements of

the set are empty set and

.

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

1). Then by properties (3) we have, i.e.,

and by definition of the set. Therefore for all.

2). Then by properties (3) we have, i.e., and by

definition of the set and. Therefore for all.

By suppose we have that, i.e. for some. If. Then.

Therefore. That is contradict of the equality, while, and by definition of the semilattice Q. Therefore for some.

3). Then by properties (3) 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. We have contradict of the equality, since.

Therefore for some.

4). Then by properties (3) 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. We have contradict of the equality, since.

Therefore for some.

5). Then by properties (3) 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. We have contradict of the equal- ity, since.

Therefore for some.

6). Then by definition quasinormal representation binary relation and by property (3) we have

, i.e. by definition of

the sets,. Therefore for all.

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

Father, let

are such mappings, which satisfying the conditions:

7) for all;

8) for all and for some;

9) for all and for some;

10) for all and for some;

11) for all and for some;

12) for all.

Now we define a map f of a set X in the semilattice D, which satisfies the condition:

Father, let,. Then binary relation my be representation by form

and satisfying the conditions:

(By suppose for some; for some; for some; for some. From this and by lemma 2.3 we have that.

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

By Theorem 1.1 the number of the mappings are respectively:

(see Lemma 1.1). The number of ordered system or number idempotent elements of this case we my be calculated by formula

Theorem is proved.

Corollary 2.1. Let, If X be a finite set and be the set of all right units of the semigroup, then the following formula is true

Proof: This Corollary directly follows from the Theorem 2.2 and from the [2, 3 Theorem 6.3.7].

Corollary is proved.

References