ABSTRACT

In this article, we study generated sets of the complete semigroups of binary relations defined by X-semilattices unions of the class ${\Sigma }_8\left(X,n+k+1\right)$ , and find uniquely irreducible generating set for the given semigroups.

Keywords:

Semigroup, Semilattice, Binary Relation

1. Introduction

Let X be an arbitrary nonempty set, D is an X-semilattice of unions which is closed with respect to the set-theoretic union of elements from D, f be an arbitrary mapping of the set X in the set D. To each mapping f we put into correspondence a binary relation ${\alpha }_f$ on the set X that satisfies the condition ${\alpha }_f={\displaystyle \underset{x\in X}{\cup }\left(\left\{x\right\}\times f\left(x\right)\right)}$ . The set of all such ${\alpha }_f$ ( $f:X\to D$ ) is denoted by $B_X\left(D\right)$ . It is easy to prove that $B_X\left(D\right)$ is a semigroup with respect to the operation of multiplication of binary relations, which is called a complete semigroup of binary relations defined by an X-semilattice of unions D.

We denote by Æ an empty binary relation or an empty subset of the set X. The condition $\left(x,y\right)\in \alpha$ will be written in the form $x\alpha y$ . Further, let $x,y\in X$ , $Y\subseteq X$ , $\alpha \in B_X\left(D\right)$ , $\stackrel{⌣}{D}={\displaystyle \underset{Y\in D}{\cup }Y}$ and $T\in D$ . We denote by the symbols $y\alpha$ , $Y\alpha$ , $V\left(D,\alpha \right)$ , $X^{\ast }$ and $V\left(X^{\ast },\alpha \right)$ the following sets:

$\begin{array}{l}y\alpha =\left\{x\in X|y\alpha x\right\},Y\alpha ={\displaystyle \underset{y\in Y}{\cup }y\alpha },V\left(D,\alpha \right)=\left\{Y\alpha |Y\in D\right\},\\ X^{\ast }=\left\{Y|\varnothing \ne Y\subseteq X\right\},V\left(X^{\ast },\alpha \right)=\left\{Y\alpha |\varnothing \ne Y\subseteq X\right\},\\ D_T=\left\{Z\in D|T\subseteq Z\right\}\text{,}{Y}_T^{\alpha }=\left\{y\in X|y\alpha =T\right\}.\end{array}$

It is well known the following statements:

Theorem 1.1. Let $D=\left\{\stackrel{⌣}{D},Z_1,Z_2,\cdots ,Z_{m-1}\right\}$ be some finite X-semilattice of unions and $C\left(D\right)=\left\{P_0,P_1,P_2,\cdots ,P_{m-1}\right\}$ be the family of sets of pairwise nonintersecting subsets of the set X (the set Æ can be repeated several times). If j is a mapping of the semilattice D on the family of sets $C\left(D\right)$ which satisfies the conditions

$\phi =\left(\begin{array}{l}\stackrel{⌣}{D}{Z}_1{Z}_2\cdots Z_{m-1}\\ P_0{P}_1{P}_2\cdots P_{m-1}\end{array}\right)$

and ${\hat{D}}_Z=D\backslash D_Z$ , then the following equalities are valid:

$\stackrel{⌣}{D}=P_0\cup P_1\cup P_2\cup \cdots \cup P_{m-1},Z_i=P_0\cup {\displaystyle \underset{T\in {\hat{D}}_{Z_i}}{\cup }\phi \left(T\right)}.$ (1.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.1), then among the parameters $P_i$ $\left(0<i\le m-1\right)$ there exist such parameters that cannot be empty sets for D. Such sets $P_i$ are called bases sources, where sets $P_j$ $\left(0\le j\le m-1\right)$ , which can be empty sets too are called completeness sources.

It is proved that under the mapping j the number of covering elements of the pre-image of a

bases source is always equal to one, while under the mapping j 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] [2] chapter 11).

Definition 1.1. We say that an element a of the semigroup $B_X\left(D\right)$ is external if $\alpha \ne \delta \circ \beta$ for all $\delta ,\beta \in B_X\left(D\right)\backslash \left\{\alpha \right\}$ (see [1] [2] Definition 1.15.1).

It is well known, that if B is all external elements of the semigroup $B_X\left(D\right)$ and $B^{\prime }$ is any generated set for the $B_X\left(D\right)$ , then $B\subseteq B^{\prime }$ (see [1] [2] Lemma 1.15.1).

Definition 1.2. The representation $\alpha ={\displaystyle \underset{T\in D}{\cup }\left(Y_T^{\alpha }\times T\right)}$ of binary relation a is called quasinormal, if ${\displaystyle \underset{T\in D}{\cup }{Y}_T^{\alpha }}=X$ and $Y_T^{\alpha }\cap Y_{T^{\prime }}^{\alpha }=\varnothing$ for any $T,T^{\prime }\in D$ ,

$T\ne T^{\prime }$ (see [1] [2] chapter 1.11).

Definition 1.3. Let $\alpha ,\beta \subseteq X\times X$ . Their product $\delta =\alpha \circ \beta$ is defined as follows: $x\delta y$ $\left(x,y\in X\right)$ if there exists an element $z\in X$ such that $x\alpha z\beta y$ (see [1] , chapter 1.3).

2. Result

Let ${\Sigma }_8\left(X,n+k+1\right)$ $\left(3\le k\le n\right)$ be a class of all X-semilattices of unions whose every element is isomorphic to an X-semilattice of unions $D=\left\{Z_1,Z_2,\cdots ,Z_{n+k},\stackrel{⌣}{D}\right\}$ , which satisfies the condition:

$\begin{array}{l}{Z}_{n+i}\subset Z_i\subset \stackrel{⌣}{D},\left(i=1,2,\cdots ,k\right);Z_j\subset \stackrel{⌣}{D},\left(j=1,2,\cdots ,n+k\right);\\ Z_p\backslash Z_q\ne \varnothing \text{and}{Z}_q\backslash Z_p\ne \varnothing \left(1\le p\ne q\le n+k\right).\end{array}$ (see Figure 1).

It is easy to see that $\tilde{D}=\left\{Z_1,Z_2,\cdots ,Z_{n+k}\right\}$ is irreducible generating set of the semilattice D.

Let $C\left(D\right)=\left\{P_0,P_1,P_2,\cdots ,P_{n+k}\right\}$ be a family of sets, where $P_0,P_1,P_2,\cdots ,P_{n+k}$ are pairwise disjoint subsets of the set X and $\phi =\left(\begin{array}{l}\stackrel{⌣}{D}{Z}_1{Z}_2\cdots Z_{n+k}\\ P_0{P}_1{P}_2\cdots P_{n+k}\end{array}\right)$ is a map

ping of the semilattice D onto the family of sets $C\left(D\right)$ . Then the formal equalities of the semilattice D have a form:

$\stackrel{⌣}{D}={\displaystyle \underset{i=0}{\overset{n+k}{\cup }}{P}_i};Z_j={\displaystyle \underset{\begin{array}{l}i=0,\\ i\ne j\end{array}}{\overset{n+k}{\cup }}{P}_i},j=1,2,\cdots ,n;Z_{n+q}={\displaystyle \underset{\begin{array}{l}i=0,\\ i\ne q,n+q\end{array}}{\overset{n+k}{\cup }}{P}_i},q=1,2,\cdots ,k.$ (2.0)

Here the elements $P_i\left(i=1,2,\cdots ,n+k\right)$ are bases sources, the element $P_0$ are sources of completeness of the semilattice D. Therefore $\left|X\right|\ge n+k$ (by symbol $\left|X\right|$ we denoted the power of a set X), since $\left|P_i\right|\ge \text{1}\left(i=1,2,\cdots ,n+k\right)$ (see [1] [2] chapter 11).

In this paper we are learning irreducible generating sets of the semigroup $B_X\left(D\right)$ defined by semilattices of the class ${\Sigma }_8\left(X,n+k+1\right)$ .

Note, that it is well known, when $k=2$ , then generated sets of the complete semigroup of binary relations defined by semilattices of the class ${\Sigma }_8\left(X,2+2+1\right)={\Sigma }_8\left(X,5\right)$ .

In this paper we suppose, that $3\le k\le n$ .

Remark, that in this case (i.e. $k\ge 3$ ), from the formal equalities of a semilattice D follows, that the intersections of any two elements of a semilattice D is not empty.

Lemma 2.0 If $D\in {\Sigma }_8\left(X,n+k+1\right)$ , then the following statements are true:

a) ${\displaystyle \underset{i=1}{\overset{n+k}{\cap }}{Z}_i}=P_0;$

b) $Z_{j+1}\backslash Z_j=P_j,j=1,2,\cdots ,n-1;$

c) $Z_q\backslash Z_{n+q}=P_{n+q},q=1,\cdots ,k.$

Proof. From the formal equalities of the semilattise D immediately follows the following statements:

$\begin{array}{l}{\displaystyle \underset{i=1}{\overset{n+k}{\cap }}{Z}_i}=P_0,Z_{j+1}\backslash Z_j=\left({\displaystyle \underset{\begin{array}{l}i=0,\\ i\ne j+1\end{array}}{\overset{n+k}{\cup }}{P}_i}\right)\backslash \left({\displaystyle \underset{\begin{array}{l}i=0,\\ i\ne j\end{array}}{\overset{n+k}{\cup }}{P}_i}\right)=P_j,j=1,2,\cdots ,n-1;\\ Z_q\backslash Z_{n+q}=\left({\displaystyle \underset{\begin{array}{l}i=0,\\ i\ne q\end{array}}{\overset{n+k}{\cup }}{P}_i}\right)\backslash \left({\displaystyle \underset{\begin{array}{l}i=0,\\ i\ne q,n+q\end{array}}{\overset{n+k}{\cup }}{P}_i}\right)=P_{n+q},q=1,\cdots ,k.\end{array}$

The statements a), b) and c) of the lemma 2.0 are proved.

Lemma 2.0 is proved.

We denoted the following sets by symbols $D_1$ , $D_2$ and $D_3$ :

$D_1=\left\{Z_1,Z_2,\cdots ,Z_k\right\},D_2=\left\{Z_{k+1},Z_{k+2},\cdots ,Z_n\right\},D_3=\left\{Z_{n+1},Z_{n+2},\cdots ,Z_{n+k}\right\}.$

Lemma 2.1. Let $D\in {\Sigma }_{8.0}\left(X,n+k+1\right)$ and $\alpha \in B_X\left(D\right)$ . Then the following statements are true:

1) Let $T,T^{\prime }\in D_2\cup D_3,T\ne T^{\prime }$ . If $T,T^{\prime }\in V\left(D,\alpha \right)$ , then a is external element of the semigroup $B_X\left(D\right)$ ;

2) Let $T\in D_1$ , $T^{\prime }\in D_2\cup D_3$ . If $T^{\prime }\not\subset T$ and $T,T^{\prime }\in V\left(D,\alpha \right)$ , then a is external element of the semigroup $B_X\left(D\right)$ .

3) Let $T,T^{\prime }\in D_1$ and $T\ne T^{\prime }$ . If $T,T^{\prime }\in V\left(D,\alpha \right)$ and $k\ge 3$ , then a is external element of the semigroup $B_X\left(D\right)$ ;

Proof. Let $Z_0=\stackrel{⌣}{D}$ and $\alpha =\delta \circ \beta$ for some $\delta ,\beta \in B_X\left(D\right)\backslash \left\{\alpha \right\}$ . If quasinormal representation of binary relation d has a form

$\delta ={\displaystyle \underset{T\in V\left(D,\delta \right)}{\cup }\left(Y_T^{\delta }\times T\right)}$ ,

then

$\alpha =\delta \circ \beta ={\displaystyle \underset{T\in V\left(D,\delta \right)}{\cup }\left(Y_T^{\delta }\times T\beta \right)}$ . (2.1)

From the formal equalities (2.0) of the semilattice D we obtain that:

$\begin{array}{l}{Z}_0\beta ={\displaystyle \underset{i=0}{\overset{n+k}{\cup }}{P}_i\beta };Z_j\beta ={\displaystyle \underset{\begin{array}{l}i=0,\\ i\ne j\end{array}}{\overset{n+k}{\cup }}{P}_i\beta },j=1,2,\cdots ,n;\\ Z_{n+q}\beta ={\displaystyle \underset{\begin{array}{l}i=0,\\ i\ne q,n+q\end{array}}{\overset{n+k}{\cup }}{P}_i\beta },q=1,2,\cdots ,k.\end{array}$ (2.2)

where $P_i\beta \ne \varnothing$ for any $P_i\ne \varnothing$ $\left(i=0,1,2,\cdots ,n+k\right)$ and $\beta \in B_X\left(D\right)$ by definition of a semilattice D from the class ${\Sigma }_{8.0}\left(X,n+k+1\right)$ .

Now, let $Z_m\beta =T$ and $Z_j\beta =T^{\prime }$ for some $T\ne T^{\prime }$ , $T,T^{\prime }\in D_2\cup D_3$ , then from the equalities (2.3) follows that $T=P_0\beta =T^{\prime }$ since T and $T^{\prime }$ are minimal elements of the semilattice D and $P_0\ne \varnothing$ by preposition. The equality $T=T^{\prime }$ contradicts the inequality $T\ne T^{\prime }$ .

The statement a) of the Lemma 2.1 is proved.

Now, let $Z_m\beta =T$ and $Z_j\beta =T^{\prime }$ , for some $T\in D_1$ , $T^{\prime }\in D_2\cup D_3$ and $T^{\prime }\not\subset T$ , then from the equalities 2.3 follows, that

$T^{\prime }=Z_j\beta =Z_0\beta ={\displaystyle \underset{i=0}{\overset{n+k}{\cup }}{P}_i\beta }$ , if $j=0$ , or $T^{\prime }=Z_j\beta ={\displaystyle \underset{\begin{array}{l}i=0,\\ i\ne j\end{array}}{\overset{n+k}{\cup }}{P}_i\beta }$ , $1\le j\le n$ , or $T^{\prime }=Z_{n+q}\beta ={\displaystyle \underset{\begin{array}{l}i=0,\\ i\ne q,n+q\end{array}}{\overset{n+k}{\cup }}{P}_i\beta }$

where $j=n+q$ . For the $Z_j\beta =T^{\prime }$ we consider the following cases:

1) If $T^{\prime }=Z_0\beta ={\displaystyle \underset{i=0}{\overset{n+k}{\cup }}{P}_i\beta }$ , then we have

$P_0\beta =P_1\beta =\cdots =P_{n+k}\beta =T^{\prime }$ ,

since $T^{\prime }$ is a minimal element of a semilattice D. On the other hand,

$T=Z_m\beta =\{\begin{array}{l}{\displaystyle \underset{\begin{array}{l}i=0,\\ i\ne m\end{array}}{\overset{n+k}{\cup }}{P}_i\beta }={\displaystyle \underset{\begin{array}{l}i=0,\\ i\ne m\end{array}}{\overset{n+k}{\cup }}{T}^{\prime }=T^{\prime }},\text{if}1\le m\le n;\\ {\displaystyle \underset{\begin{array}{l}i=0,\\ i\ne q,n+q\end{array}}{\overset{n+k}{\cup }}{P}_i\beta }={\displaystyle \underset{\begin{array}{l}i=0,\\ i\ne q,n+q\end{array}}{\overset{n+k}{\cup }}{T}^{\prime }=T^{\prime }},\text{if}m=n+q.\end{array}$

But the equality $T=T^{\prime }$ contradicts the inequality $T\ne T^{\prime }$ . Thus we have, that $j\ne 0$ .

2) Let $1\le j\le n$ , i.e. $T^{\prime }=Z_j\beta ={\displaystyle \underset{\begin{array}{l}i=0,\\ i\ne j\end{array}}{\overset{n+k}{\cup }}{P}_i\beta }$ , then we have, that

$P_0\beta =P_1\beta =\cdots =P_{j-1}\beta =P_{j+1}\beta =\cdots =P_{n+k}\beta =T^{\prime }$ ,

since $T^{\prime }$ is a minimal element of a semilattice D. On the other hand:

$T=Z_m\beta =\{\begin{array}{l}\left({\displaystyle \underset{i=0}{\overset{n+k}{\cup }}{P}_i\beta }\right)=\left({\displaystyle \underset{\begin{array}{l}i=0,\\ i\ne j\end{array}}{\overset{n+k}{\cup }}{P}_i\beta }\right)\cup P_j\beta =T^{\prime }\cup P_j\beta ,\text{if}m=0;\\ \left({\displaystyle \underset{\begin{array}{l}i=0,\\ i\ne m\end{array}}{\overset{n+k}{\cup }}{P}_i\beta }\right)=\left({\displaystyle \underset{\begin{array}{l}i=0,\\ i\ne m,j\end{array}}{\overset{n+k}{\cup }}{P}_i\beta }\right)\cup P_j\beta =T^{\prime }\cup P_j\beta ,\text{if}1\le m\le n,m\ne j;\\ \left({\displaystyle \underset{\begin{array}{l}i=0,\\ i\ne j,n+j\end{array}}{\overset{n+k}{\cup }}{P}_i\beta }\right)=T^{\prime },\text{if}m=n+j;\\ \left({\displaystyle \underset{\begin{array}{l}i=0,\\ i\ne q,n+q\end{array}}{\overset{n+k}{\cup }}{P}_i\beta }\right)=\left({\displaystyle \underset{\begin{array}{l}i=0,\\ i\ne q,n+q,j\end{array}}{\overset{n+k}{\cup }}{P}_i\beta }\right)\cup P_j\beta =T^{\prime }\cup P_j\beta ,\text{if}m=n+q,q\ne j.\end{array}$

The equality $T=T^{\prime }$ contradicts the inequality $T\ne T^{\prime }$ . Also, the equality $T=T^{\prime }\cup P_j\beta$ $\left(P_j\beta \in D\right)$ contradicts the inequality $T\ne T^{\prime }\cup Z$ for any $Z\in D$ and $T^{\prime }\not\subset T$ ( $T^{\prime }\not\subset T$ , by preposition) by definition of a semilattice D.

3) If $j=n+q$ $\left(1\le q\le k\right)$ , i.e. $T^{\prime }=Z_{n+q}\beta ={\displaystyle \underset{\begin{array}{l}i=0,\\ i\ne q,n+q\end{array}}{\overset{n+k}{\cup }}{P}_i\beta }$ , then we have, that

$P_0\beta =P_1\beta =\cdots =P_{q-1}\beta =P_{q+1}\beta =\cdots =P_{n+q-1}\beta =P_{n+q+1}\beta =\cdots =P_{n+k}\beta =T^{\prime }$ ,

since $T^{\prime }$ is a minimal element of a semilattice D. On the other hand:

$T=Z_m\beta =\{\begin{array}{l}\left({\displaystyle \underset{i=0,}{\overset{n+k}{\cup }}{P}_i\beta }\right)=\left({\displaystyle \underset{\begin{array}{l}i=0,\\ i\ne q,n+q\end{array}}{\overset{n+k}{\cup }}{P}_i\beta }\right)\cup P_q\beta \cup P_{n+q}\beta =T^{\prime }\cup P_q\beta \cup P_{n+q}\beta ,\text{if}m=0;\\ \left({\displaystyle \underset{\begin{array}{l}i=0,\\ i\ne q\end{array}}{\overset{n+k}{\cup }}{P}_i\beta }\right)=\left({\displaystyle \underset{\begin{array}{l}i=0,\\ i\ne q,n+q\end{array}}{\overset{n+k}{\cup }}{P}_i\beta }\right)\cup P_{n+q}\beta =T^{\prime }\cup P_{n+q}\beta ,\text{if}1\le m=q\le n;\\ \left({\displaystyle \underset{\begin{array}{l}i=0,\\ i\ne m\end{array}}{\overset{n+k}{\cup }}{P}_i\beta }\right)=\left({\displaystyle \underset{\begin{array}{l}i=0,\\ i\ne m,q,n+q\end{array}}{\overset{n+k}{\cup }}{P}_i\beta }\right)\cup P_q\beta \cup P_{n+q}\beta =T^{\prime }\cup P_q\beta \cup P_{n+q}\beta ,\text{if}1\le m\ne q\le n;\\ \left({\displaystyle \underset{\begin{array}{l}i=0,\\ i\ne m,\end{array}}{\overset{n+k}{\cup }}{P}_i\beta }\right)=\left({\displaystyle \underset{\begin{array}{l}i=0,\\ i\ne q^{\prime },n+q^{\prime }\end{array}}{\overset{n+k}{\cup }}{P}_i\beta }\right)=\left({\displaystyle \underset{\begin{array}{l}i=0,\\ i\ne ,q^{\prime },n+q^{\prime },q,n+q\end{array}}{\overset{n+k}{\cup }}{P}_i\beta }\right)\cup P_q\beta \cup P_{n+q}=T\cup P_q\beta \cup P_{n+q},\\ \text{if}n+1\le m=n+q^{\prime }\le n+k,q\ne q^{\prime }\text{since}j\ne m.\end{array}$

The equality $T=T^{\prime }$ contradicts the inequality $T\ne T^{\prime }$ . Also, the equality $T=T^{\prime }\cup P_q\beta \cup P_{n+q}\beta$ , or $T=T^{\prime }\cup P_{n+q}\beta$ $\left(P_q\beta ,P_{n+q}\beta \in D\right)$ contradicts the inequality $T\ne T^{\prime }\cup Z$ for any $Z\in D$ and $T^{\prime }\not\subset T$ by definition of a semilattice D.

The statement 2) of the Lemma 2.1 is proved.

Let $T,T^{\prime }\in D_1$ and $T\ne T^{\prime }$ . If $k\ge 3$ and $Z_j\beta =T^{\prime }$ , $Z_m\beta =T$ , then from the formal equalities (2.0) of a semilattice D there exists such an element, that $P_q\subseteq Z_j$ and $P_q\subseteq Z_m$ , where $0\le q\le m+k$ . So, from the equalities (2.3) follows that $P_q\beta \subseteq Z_j\beta =T^{\prime }$ and $P_q\beta \subseteq Z_m\beta =T$ . Of from this and from the equalities (2.3) we obtain that there exists such an element $Z\in D$ , for which the equalities $T^{\prime }=Z\cup Z^{\prime }$ and $T=Z\cup Z^{″}$ , where $Z^{\prime },Z^{″}\in D$ . But such elements by definition of a semilattice D do not exist.

The statement c) of the Lemma 2.1 is proved.

Lemma 2.1 is proved.

Lemma 2.2. Let $D\in {\Sigma }_8\left(X,n+k+1\right)$ and $\alpha \in B_X\left(D\right)$ . Then the following statements are true:

1) Let $V\left(D,\alpha \right)\cap D_1\ne \varnothing ,V\left(D,\alpha \right)\cap D_2=\varnothing ,V\left(D,\alpha \right)\cap D_3=\varnothing$ . If $\left|V\left(D,\alpha \right)\cap D_1\right|\ge 2$ , then a is external element of the semigroup $B_X\left(D\right)$ ;

2) Let $V\left(D,\alpha \right)\cap D_1=\varnothing ,V\left(D,\alpha \right)\cap D_2\ne \varnothing ,V\left(D,\alpha \right)\cap D_3=\varnothing$ . If $\left|V\left(D,\alpha \right)\cap D_2\right|\ge 2$ , then a is external element of the semigroup $B_X\left(D\right)$ ;

3) Let $V\left(D,\alpha \right)\cap D_1=\varnothing ,V\left(D,\alpha \right)\cap D_2=\varnothing ,V\left(D,\alpha \right)\cap D_3\ne \varnothing$ . If $\left|V\left(D,\alpha \right)\cap D_3\right|\ge 2$ , then a is external element of the semigroup $B_X\left(D\right)$ ;

4) Let $V\left(D,\alpha \right)\cap D_1=\varnothing ,V\left(D,\alpha \right)\cap D_2\ne \varnothing ,V\left(D,\alpha \right)\cap D_3\ne \varnothing$ , then a is external element of the semigroup $B_X\left(D\right)$ ;

5) Let $V\left(D,\alpha \right)\cap D_1\ne \varnothing ,V\left(D,\alpha \right)\cap D_2=\varnothing ,V\left(D,\alpha \right)\cap D_3\ne \varnothing$ . If $\left|V\left(D,\alpha \right)\cap D_1\right|\ge 2$ , $\left|V\left(D,\alpha \right)\cap D_3\right|=1$ , or $\left|V\left(D,\alpha \right)\cap D_1\right|=1$ , $\left|V\left(D,\alpha \right)\cap D_3\right|\ge 2$ then a is external element of the semigroup $B_X\left(D\right)$ ;

6) Let $V\left(D,\alpha \right)\cap D_1\ne \varnothing ,V\left(D,\alpha \right)\cap D_2\ne \varnothing ,V\left(D,\alpha \right)\cap D_3=\varnothing$ , then a is external element of the semigroup $B_X\left(D\right)$ ;

7) Let $V\left(D,\alpha \right)\cap D_1\ne \varnothing ,V\left(D,\alpha \right)\cap D_2\ne \varnothing ,V\left(D,\alpha \right)\cap D_3\ne \varnothing$ , then a is external element of the semigroup $B_X\left(D\right)$ .

Proof. Let a be any element of the semigroup $B_X\left(D\right)$ . It is easy that $V\left(D,\alpha \right)\in D$ . We consider the following cases:

Let $V\left(D,\alpha \right)\cap D_1=\varnothing ,V\left(D,\alpha \right)\cap D_2=\varnothing ,V\left(D,\alpha \right)\cap D_3=\varnothing$ , then $V\left(D,\alpha \right)\in \left\{\stackrel{⌣}{D}\right\}$ since $V\left(D,\alpha \right)$ is subsemilattice of the semilattice D.

1) Let $V\left(D,\alpha \right)\cap D_1\ne \varnothing ,V\left(D,\alpha \right)\cap D_2=\varnothing ,V\left(D,\alpha \right)\cap D_3=\varnothing$ .

If $\left|V\left(D,\alpha \right)\cap D_1\right|=1$ , then $V\left(D,\alpha \right)\in \left\{Z_j\right\}$ , or $V\left(D,\alpha \right)\in \left\{Z_j,\stackrel{⌣}{D}\right\}$ , where $j=1,2,\cdots ,k$ , since $V\left(D,\alpha \right)$ is subsemilattice of the semilattice D.

If $\left|V\left(D,\alpha \right)\cap D_1\right|\ge 2$ , then by statement c) of the Lemma 2.1 follows that a is external element of the semigroup $B_X\left(D\right)$ .

2) Let $V\left(D,\alpha \right)\cap D_1=\varnothing ,V\left(D,\alpha \right)\cap D_2\ne \varnothing ,V\left(D,\alpha \right)\cap D_3=\varnothing$ .

If $\left|V\left(D,\alpha \right)\cap D_2\right|=1$ , then $V\left(D,\alpha \right)\in \left\{Z_j\right\}$ , or $V\left(D,\alpha \right)\in \left\{Z_j,\stackrel{⌣}{D}\right\}$ , where $j=k+1,k+2,\cdots ,n$ , since $V\left(D,\alpha \right)$ is a subsemilattice of the semilattice D.

If $\left|V\left(D,\alpha \right)\cap D_2\right|\ge 2$ , then by statement a) of the Lemma 2.1 follows that a is external element of the semigroup $B_X\left(D\right)$ .

3) Let $V\left(D,\alpha \right)\cap D_1=\varnothing ,V\left(D,\alpha \right)\cap D_2=\varnothing ,V\left(D,\alpha \right)\cap D_3\ne \varnothing$ .

If $\left|V\left(D,\alpha \right)\cap D_3\right|=1$ , then $V\left(D,\alpha \right)\in \left\{Z_j\right\}$ , or $V\left(D,\alpha \right)\in \left\{Z_j,\stackrel{⌣}{D}\right\}$ , $j=n+1,n+2,\cdots ,n+k$ , since $V\left(D,\alpha \right)$ is subsemilattice of the semilattice D.

If $\left|V\left(D,\alpha \right)\cap D_3\right|\ge 2$ , then by statement a) of the Lemma 2.1 follows that a is external element of the semigroup $B_X\left(D\right)$ .

4) Let $V\left(D,\alpha \right)\cap D_1=\varnothing ,V\left(D,\alpha \right)\cap D_2\ne \varnothing ,V\left(D,\alpha \right)\cap D_3\ne \varnothing$ , then by the statement a) of the Lemma 2.1 follows that a is external element of the semi­group $B_X\left(D\right)$ .

5) Let $V\left(D,\alpha \right)\cap D_1\ne \varnothing ,V\left(D,\alpha \right)\cap D_2=\varnothing ,V\left(D,\alpha \right)\cap D_3\ne \varnothing$ .

If $\left|V\left(D,\alpha \right)\cap D_1\right|=1,\left|V\left(D,\alpha \right)\cap D_3\right|=1$ , then $V\left(D,\alpha \right)=\left\{Z_{n+q},Z_q\right\}$ , or $V\left(D,\alpha \right)=\left\{Z_{n+q},Z_q,\stackrel{⌣}{D}\right\}$ , or $V\left(D,\alpha \right)=\left\{Z_{n+q},Z_j,\stackrel{⌣}{D}\right\}$ where $Z_1\le Z_j\le Z_k$ and $q=1,2,\cdots ,k$ .

If $V\left(D,\alpha \right)=\left\{Z_{n+q},Z_j,\stackrel{⌣}{D}\right\}$ where $j\ne q,q=1,2,\cdots ,k$ , then by the statement 2) of the Lemma 2.1 follows that a is external element of the semigroup $B_X\left(D\right)$ ;

If $\left|V\left(D,\alpha \right)\cap D_1\right|=1,\left|V\left(D,\alpha \right)\cap D_3\right|\ge 2$ , or $\left|V\left(D,\alpha \right)\cap D_1\right|\ge 2,\left|V\left(D,\alpha \right)\cap D_3\right|=1$ , then from the statement 1) and 3) of the Lemma 2.1 follows that a is external element of the semigroup $B_X\left(D\right)$ respectively.

6) Let $V\left(D,\alpha \right)\cap D_1\ne \varnothing ,V\left(D,\alpha \right)\cap D_2\ne \varnothing ,V\left(D,\alpha \right)\cap D_3=\varnothing$ . Then from the statement b) of the Lemma 2.1 follows that a is external element of the semi­group $B_X\left(D\right)$ .

7) Let $V\left(D,\alpha \right)\cap D_1\ne \varnothing ,V\left(D,\alpha \right)\cap D_2\ne \varnothing ,V\left(D,\alpha \right)\cap D_3\ne \varnothing$ , then by the statement a) of the Lemma 2.1 follows that a is external element of the semi­group $B_X\left(D\right)$ .

Lemma 2.2 is proved.

Now we learn the following subsemilattices of the semilattice D:

$\begin{array}{l}{\mathfrak{A}}_1=\left\{\left\{Z_{n+j},Z_j,\stackrel{⌣}{D}\right\}\right\},\text{where}j=1,2,\cdots ,k;\\ {\mathfrak{A}}_2=\left\{\left\{Z_j,\stackrel{⌣}{D}\right\}\right\},\text{where}j=1,2,\cdots ,n+k;\\ {\mathfrak{A}}_3=\left\{\left\{Z_{n+j},Z_j\right\}\right\},\text{where}j=1,2,\cdots ,k;\\ {\mathfrak{A}}_4=\left\{\left\{Z_j\right\},\left\{\stackrel{⌣}{D}\right\}\right\},\text{where}j=1,2,\cdots ,n+k.\end{array}$

We denoted the following sets by symbols ${\mathfrak{A}}_0$ and $B\left({\mathfrak{A}}_0\right)$ :

$\begin{array}{l}{\mathfrak{A}}_0=\left\{V\left(D,\alpha \right)\subseteq D|V\left(D,\alpha \right)\notin {\mathfrak{A}}_1\cup {\mathfrak{A}}_2\cup {\mathfrak{A}}_3\cup {\mathfrak{A}}_4\right\},\\ B\left({\mathfrak{A}}_0\right)=\left\{\alpha \in B_X\left(D\right)|V\left(D,\alpha \right)\in {\mathfrak{A}}_0\right\}.\end{array}$

By definition of a set $B\left({\mathfrak{A}}_0\right)$ follows that any element of the set is external element of the semigroup $B_X\left(D\right)$ .

Lemma 2.3. Let $D\in {\Sigma }_8\left(X,n+k+1\right)$ . If quasinormal representation of a binary relation a has a form

$\alpha =\left(Y_{n+j}^{\alpha }\times Z_{n+j}\right)\cup \left(Y_j^{\alpha }\times Z_j\right)\cup \left(Y_0^{\alpha }\times \stackrel{⌣}{D}\right),$

where $Y_{n+j}^{\alpha },Y_j^{\alpha },Y_0^{\alpha }\notin \{\varnothing \}$ and $j=1,2,\cdots ,k$ , then a is generated by elements of the elements of set $B\left({\mathfrak{A}}_0\right)$ .

Proof. 1). Let quasinormal representation of binary relations d and b have a form

$\begin{array}{l}\delta =\left(Y_{n+j}^{\delta }\times Z_{n+j}\right)\cup \left(Y_j^{\delta }\times Z_j\right)\cup \left(Y_q^{\delta }\times Z_q\right)\cup \left(Y_0^{\delta }\times \stackrel{⌣}{D}\right),\\ \beta =\left(Z_{n+j}\times Z_{n+j}\right)\cup \left(\left(Z_j\backslash Z_{n+j}\right)\times Z_j\right)\cup \left(\left(\stackrel{⌣}{D}\backslash Z_j\right)\times Z_q\right)\cup \left(\left(X\backslash \stackrel{⌣}{D}\right)\times \stackrel{⌣}{D}\right),\end{array}$

where $Y_{n+j}^{\alpha },Y_j^{\alpha },Y_q^{\alpha }\notin \{\varnothing \},Z_1\le Z_q\le Z_k,q\ne j,j=1,\cdots ,k$ .

$\begin{array}{l}{Z}_{n+j}\cup \left(Z_j\backslash Z_{n+j}\right)\cup \left(\stackrel{⌣}{D}\backslash Z_j\right)\cup \left(X\backslash \stackrel{⌣}{D}\right)\\ =\left(P_0\cup {\displaystyle \underset{\begin{array}{l}i=1,\\ i\ne j,n+j\end{array}}{\overset{n+k}{\cup }}{P}_i}\right)\cup P_{n+j}\cup P_j\cup \left(X\backslash \stackrel{⌣}{D}\right)=\stackrel{⌣}{D}\cup \left(X\backslash \stackrel{⌣}{D}\right)=X\end{array}$ ,

since the representation of a binary relation b is quasinormal and by statement 3) of the Lemma 2.1 binary relations d and b are external elements of the semigroup $B_X\left(D\right)$ . It is easy to see, that:

$Z_{n+j}\beta =Z_{n+j},$

$\begin{array}{c}{Z}_j\beta =\left(P_0\cup {\displaystyle \underset{\begin{array}{l}i=1,\\ i\ne j\end{array}}{\overset{n+k}{\cup }}{P}_i}\right)\beta =\left(\left(P_0\cup {\displaystyle \underset{\begin{array}{l}i=1,\\ i\ne j,n+j\end{array}}{\overset{n+k}{\cup }}{P}_i}\right)\cup P_{n+j}\right)\beta \\ =Z_{n+j}\beta \cup P_{n+j}\beta =Z_{n+j}\cup Z_j=Z_j,\end{array}$

$\begin{array}{l}{Z}_q\beta =\left(P_0\cup {\displaystyle \underset{\begin{array}{l}i=1,\\ i\ne q\end{array}}{\overset{n+k}{\cup }}{P}_i}\right)\beta =Z_{n+j}\cup Z_j\cup Z_q=\stackrel{⌣}{D},\\ \stackrel{⌣}{D}\beta ={\displaystyle \underset{i=0}{\overset{n+k}{\cup }}{P}_i\beta }=Z_{n+j}\cup Z_j\cup Z_q=\stackrel{⌣}{D}\end{array}$

since $Z_q\cap Z_{n+j}\ne \varnothing ,Z_q\cap \left(Z_j\backslash Z_{n+j}\right)=P_{n+j}\ne \varnothing ,Z_q\cap \left(D\backslash Z_j\right)=P_j\ne \varnothing$ (see equality (2.0))

$\begin{array}{c}\alpha =\delta \circ \beta =\left(Y_{n+j}^{\delta }\times Z_{n+j}\beta \right)\cup \left(Y_j^{\delta }\times Z_j\beta \right)\cup \left(Y_q^{\delta }\times Z_q\beta \right)\cup \left(Y_0^{\delta }\times \stackrel{⌣}{D}\beta \right)\\ =\left(Y_{n+j}^{\delta }\times Z_{n+j}\right)\cup \left(Y_j^{\delta }\times Z_j\right)\cup \left(Y_q^{\delta }\times \stackrel{⌣}{D}\right)\cup \left(Y_0^{\delta }\times \stackrel{⌣}{D}\right)\\ =\left(Y_{n+j}^{\delta }\times Z_{n+j}\right)\cup \left(Y_j^{\delta }\times Z_j\right)\cup \left(\left(Y_q^{\delta }\cup Y_0^{\delta }\right)\times \stackrel{⌣}{D}\right)=\alpha ,\end{array}$

if $Y_{n+j}^{\delta }=Y_{n+j}^{\alpha }$ , $Y_j^{\delta }=Y_j^{\alpha }$ and $Y_q^{\delta }\cup Y_0^{\delta }=Y_0^{\alpha }$ . Last equalities are possible since $\left|Y_q^{\delta }\cup Y_0^{\delta }\right|\ge 1$ ( $\left|Y_0^{\delta }\right|\ge 0$ , by preposition).

Lemma 2.3 is proved.

Lemma 2.4. Let $D\in {\Sigma }_8\left(X,n+k+1\right)$ . If quasinormal representation of a binary relation a has a form $\alpha =\left(Y_j^{\alpha }\times Z_j\right)\cup \left(Y_0^{\alpha }\times \stackrel{⌣}{D}\right)$ , where $Y_j^{\alpha },Y_0^{\alpha }\notin \{\varnothing \}$ , $j=1,2,\cdots ,n+k$ , then binary relation a is generated by elements of the elements of set $B\left({\mathfrak{A}}_0\right)$ .

Proof. Let quasinormal representation of the binary relations d and b have a form:

$\begin{array}{l}\delta =\left(Y_j^{\delta }\times Z_j\right)\cup \left(Y_q^{\delta }\times Z_q\right)\cup \left(Y_0^{\delta }\times \stackrel{⌣}{D}\right),\\ \beta =\left(Z_j\times Z_j\right)\cup \left(\left(\stackrel{⌣}{D}\backslash Z_j\right)\times Z_q\right)\cup \left(\left(X\backslash \stackrel{⌣}{D}\right)\times \stackrel{⌣}{D}\right),\end{array}$

where $Y_j^{\delta },Y_q^{\delta }\notin \{\varnothing \}$ and $Z_1\le Z_j\ne Z_q\le Z_{n+k}$ . Then from the statements a), b) and c) of the Lemma 2.1 follows, that d and b are generated by elements of the set $B\left({\mathfrak{A}}_0\right)$ and

$Z_j\beta =Z_j,$

$Z_q\beta =\stackrel{⌣}{D}$ , since $Z_q\cap \left(D\backslash Z_j\right)=P_j\ne \varnothing ,$

$\stackrel{⌣}{D}\beta =\stackrel{⌣}{D};$

$\begin{array}{c}\delta \circ \beta =\left(Y_j^{\delta }\times Z_j\beta \right)\cup \left(Y_q^{\delta }\times Z_q\beta \right)\cup \left(Y_0^{\delta }\times \stackrel{⌣}{D}\beta \right)\\ =\left(Y_j^{\delta }\times Z_j\right)\cup \left(Y_q^{\delta }\times \stackrel{⌣}{D}\right)\cup \left(Y_0^{\delta }\times \stackrel{⌣}{D}\right)\\ =\left(Y_j^{\delta }\times Z_j\right)\cup \left(\left(Y_q^{\delta }\cup Y_0^{\delta }\right)\times \stackrel{⌣}{D}\right)=\alpha ,\end{array}$

if $Y_j^{\delta }=Y_j^{\alpha }$ , $Y_q^{\delta }\cup Y_0^{\delta }=Y_0^{\alpha }$ and $q=1,2,\cdots ,n+k$ . Last equalities are possible since $\left|Y_q^{\delta }\cup Y_0^{\delta }\right|\ge 1$ ( $\left|Y_0^{\delta }\right|\ge 0$ by preposition).

Lemma 2.4 is proved.

Lemma 2.5. Let $D\in {\Sigma }_8\left(X,n+k+1\right)$ . If quasinormal representation of a binary relation a has a form $\alpha =\left(Y_{n+j}^{\alpha }\times Z_{n+j}\right)\cup \left(Y_j^{\alpha }\times Z_j\right)$ , where $Y_{n+j}^{\alpha },Y_j^{\alpha }\notin \{\varnothing \}$ , $j=1,2,\cdots ,k$ , then binary relation a is generated by elements of the elements of set $B\left({\mathfrak{A}}_0\right)$ .

Proof. Let quasinormal representation of a binary relations d, b have a form

$\begin{array}{l}\delta =\left(Y_{n+j}^{\delta }\times Z_{n+j}\right)\cup \left(Y_q^{\delta }\times Z_q\right)\cup \left(Y_0^{\delta }\times \stackrel{⌣}{D}\right),\\ \beta =\left(Z_{n+j}\times Z_{n+j}\right)\cup \left(\left(\stackrel{⌣}{D}\backslash Z_{n+j}\right)\times Z_j\right)\cup \left(\left(X\backslash \stackrel{⌣}{D}\right)\times \stackrel{⌣}{D}\right),\end{array}$

where $Y_{n+j}^{\delta },Y_q^{\delta }\notin \{\varnothing \}$ , $j\ne q$ and $j=1,2,\cdots ,k$ . Then from the Lemma 2.2 follows that b is generated by elements of the set $B\left({\mathfrak{A}}_0\right)$ , $\delta \in B\left({\mathfrak{A}}_0\right)$ and

$Z_{n+j}\beta =Z_{n+j},$

$Z_q\beta =Z_{n+j}\cup Z_j=Z_j$ , since $Z_q\cap Z_{n+j}\ne \varnothing$ , $Z_q\cap \left(\stackrel{⌣}{D}\backslash Z_{n+j}\right)=P_{n+j}\ne \varnothing ,j\ne q$ (see equality(2.0))

$\stackrel{⌣}{D}\beta =Z_j$ since $\stackrel{⌣}{D}\cap \left(X\backslash \stackrel{⌣}{D}\right)=\varnothing ,$

$\begin{array}{c}\delta \circ \beta =\left(Y_{n+j}^{\delta }\times Z_{n+j}\beta \right)\cup \left(Y_q^{\delta }\times Z_q\beta \right)\cup \left(Y_0^{\delta }\times \stackrel{⌣}{D}\right)\\ =\left(Y_{n+j}^{\delta }\times Z_{n+j}\right)\cup \left(Y_q^{\delta }\times Z_j\right)\cup \left(Y_0^{\delta }\times Z_j\right)\\ =\left(Y_{n+j}^{\delta }\times Z_{n+j}\right)\cup \left(\left(Y_q^{\delta }\cup Y_0^{\delta }\right)\times Z_j\right)=\alpha ,\end{array}$