Generated Sets of the Complete Semigroup Binary Relations Defined by Semilattices of the Class Σ8 (X, n + k + 1)
Abstract: In this article, we study generated sets of the complete semigroups of binary relations defined by X-semilattices unions of the class Σ8 (X, n + k +1) , and find uniquely irreducible generating set for the given semigroups.

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}=\underset{x\in X}{\cup }\left(\left\{x\right\}×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}=\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\},\text{}Y\alpha =\underset{y\in Y}{\cup }y\alpha ,\text{}V\left(D,\alpha \right)=\left\{Y\alpha |Y\in D\right\},\\ {X}^{\ast }=\left\{Y|\varnothing \ne Y\subseteq X\right\},\text{}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}\text{}{Z}_{1}\text{}{Z}_{2}\text{}\cdots \text{}{Z}_{m-1}\\ {P}_{0}\text{}{P}_{1}\text{}{P}_{2}\text{}\cdots \text{}{P}_{m-1}\end{array}\right)$

and ${\stackrel{^}{D}}_{Z}=D\{D}_{Z}$ , then the following equalities are valid:

$\stackrel{⌣}{D}={P}_{0}\cup {P}_{1}\cup {P}_{2}\cup \cdots \cup {P}_{m-1},\text{}{Z}_{i}={P}_{0}\cup \underset{T\in {\stackrel{^}{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 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   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)\\left\{\alpha \right\}$ (see   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   Lemma 1.15.1).

Definition 1.2. The representation $\alpha =\underset{T\in D}{\cup }\left({Y}_{T}^{\alpha }×T\right)$ of binary relation a is called quasinormal, if $\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   chapter 1.11).

Definition 1.3. Let $\alpha ,\beta \subseteq X×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  , 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},\text{}\left(i=1,2,\cdots ,k\right);\text{}{Z}_{j}\subset \stackrel{⌣}{D},\text{}\left(j=1,2,\cdots ,n+k\right);\\ {Z}_{p}\{Z}_{q}\ne \varnothing \text{and}{Z}_{q}\{Z}_{p}\ne \varnothing \text{}\left(1\le p\ne q\le n+k\right).\end{array}$ (see Figure 1).

Figure 1. Diagram of the semilattice D.

It is easy to see that $\stackrel{˜}{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}\text{}{Z}_{1}\text{}{Z}_{2}\text{}\cdots \text{}{Z}_{n+k}\\ {P}_{0}\text{}{P}_{1}\text{}{P}_{2}\text{}\cdots \text{}{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}=\underset{i=0}{\overset{n+k}{\cup }}{P}_{i};\text{}{Z}_{j}=\underset{\begin{array}{l}i=0,\\ i\ne j\end{array}}{\overset{n+k}{\cup }}{P}_{i},\text{}j=1,2,\cdots ,n;{Z}_{n+q}=\underset{\begin{array}{l}\text{}i=0,\\ i\ne q,n+q\end{array}}{\overset{n+k}{\cup }}{P}_{i},\text{}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 $|X|\ge n+k$ (by symbol $|X|$ we denoted the power of a set X), since $|{P}_{i}|\ge \text{1}\left(i=1,2,\cdots ,n+k\right)$ (see   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) $\underset{i=1}{\overset{n+k}{\cap }}{Z}_{i}={P}_{0};$

b) ${Z}_{j+1}\{Z}_{j}={P}_{j},\text{}j=1,2,\cdots ,n-1;$

c) ${Z}_{q}\{Z}_{n+q}={P}_{n+q},\text{}q=1,\cdots ,k.$

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

$\begin{array}{l}\underset{i=1}{\overset{n+k}{\cap }}{Z}_{i}={P}_{0},\text{}{Z}_{j+1}\{Z}_{j}=\left(\underset{\begin{array}{l}\text{}i=0,\\ i\ne j+1\end{array}}{\overset{n+k}{\cup }}{P}_{i}\right)\\left(\underset{\begin{array}{l}i=0,\\ i\ne j\end{array}}{\overset{n+k}{\cup }}{P}_{i}\right)={P}_{j},\text{}j=1,2,\cdots ,n-1;\\ {Z}_{q}\{Z}_{n+q}=\left(\underset{\begin{array}{l}i=0,\\ i\ne q\end{array}}{\overset{n+k}{\cup }}{P}_{i}\right)\\left(\underset{\begin{array}{l}\text{}i=0,\\ i\ne q,n+q\end{array}}{\overset{n+k}{\cup }}{P}_{i}\right)={P}_{n+q},\text{}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\},\text{}{D}_{2}=\left\{{Z}_{k+1},{Z}_{k+2},\cdots ,{Z}_{n}\right\},\text{}{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)\\left\{\alpha \right\}$ . If quasinormal representation of binary relation d has a form

$\delta =\underset{T\in V\left(D,\delta \right)}{\cup }\left({Y}_{T}^{\delta }×T\right)$ ,

then

$\alpha =\delta \circ \beta =\underset{T\in V\left(D,\delta \right)}{\cup }\left({Y}_{T}^{\delta }×T\beta \right)$ . (2.1)

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

$\begin{array}{l}{Z}_{0}\beta =\underset{i=0}{\overset{n+k}{\cup }}{P}_{i}\beta ;\text{}{Z}_{j}\beta =\underset{\begin{array}{l}i=0,\\ i\ne j\end{array}}{\overset{n+k}{\cup }}{P}_{i}\beta ,\text{}j=1,2,\cdots ,n;\\ {Z}_{n+q}\beta =\underset{\begin{array}{l}\text{}i=0,\\ i\ne q,n+q\end{array}}{\overset{n+k}{\cup }}{P}_{i}\beta ,\text{}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 =\underset{i=0}{\overset{n+k}{\cup }}{P}_{i}\beta$ , if $j=0$ , or ${T}^{\prime }={Z}_{j}\beta =\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 =\underset{\begin{array}{l}\text{}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 =\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 =\left\{\begin{array}{l}\underset{\begin{array}{l}i=0,\\ i\ne m\end{array}}{\overset{n+k}{\cup }}{P}_{i}\beta =\underset{\begin{array}{l}i=0,\\ i\ne m\end{array}}{\overset{n+k}{\cup }}{T}^{\prime }={T}^{\prime },\text{if}\text{\hspace{0.17em}}1\le m\le n;\\ \underset{\begin{array}{l}\text{}i=0,\\ i\ne q,n+q\end{array}}{\overset{n+k}{\cup }}{P}_{i}\beta =\underset{\begin{array}{l}\text{}i=0,\\ i\ne q,n+q\end{array}}{\overset{n+k}{\cup }}{T}^{\prime }={T}^{\prime },\text{if}\text{\hspace{0.17em}}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 =\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 =\left\{\begin{array}{l}\left(\underset{i=0}{\overset{n+k}{\cup }}{P}_{i}\beta \right)=\left(\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}\text{\hspace{0.17em}}m=0;\\ \left(\underset{\begin{array}{l}i=0,\\ i\ne m\end{array}}{\overset{n+k}{\cup }}{P}_{i}\beta \right)=\left(\underset{\begin{array}{l}\text{}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}\text{\hspace{0.17em}}1\le m\le n,\text{}m\ne j;\\ \left(\underset{\begin{array}{l}\text{}i=0,\\ i\ne j,n+j\end{array}}{\overset{n+k}{\cup }}{P}_{i}\beta \right)={T}^{\prime },\text{if}\text{\hspace{0.17em}}m=n+j;\\ \left(\underset{\begin{array}{l}\text{}i=0,\\ i\ne q,n+q\end{array}}{\overset{n+k}{\cup }}{P}_{i}\beta \right)=\left(\underset{\begin{array}{l}\text{}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}\text{\hspace{0.17em}}m=n+q,\text{}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 =\underset{\begin{array}{l}\text{}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 =\left\{\begin{array}{l}\left(\underset{i=0,}{\overset{n+k}{\cup }}{P}_{i}\beta \right)=\left(\underset{\begin{array}{l}\text{}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}\text{\hspace{0.17em}}m=0;\\ \left(\underset{\begin{array}{l}i=0,\\ i\ne q\end{array}}{\overset{n+k}{\cup }}{P}_{i}\beta \right)=\left(\underset{\begin{array}{l}\text{}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}\text{\hspace{0.17em}}1\le m=q\le n;\\ \left(\underset{\begin{array}{l}\text{}i=0,\\ i\ne m\end{array}}{\overset{n+k}{\cup }}{P}_{i}\beta \right)=\left(\underset{\begin{array}{l}\text{}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}\text{\hspace{0.17em}}1\le m\ne q\le n;\\ \left(\underset{\begin{array}{l}i=0,\\ i\ne m,\end{array}}{\overset{n+k}{\cup }}{P}_{i}\beta \right)=\left(\underset{\begin{array}{l}\text{}i=0,\\ i\ne {q}^{\prime },n+{q}^{\prime }\end{array}}{\overset{n+k}{\cup }}{P}_{i}\beta \right)=\left(\underset{\begin{array}{l}\text{}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}\text{\hspace{0.17em}}n+1\le m=n+{q}^{\prime }\le n+k,\text{}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 $|V\left(D,\alpha \right)\cap {D}_{1}|\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 $|V\left(D,\alpha \right)\cap {D}_{2}|\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 $|V\left(D,\alpha \right)\cap {D}_{3}|\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 $|V\left(D,\alpha \right)\cap {D}_{1}|\ge 2$ , $|V\left(D,\alpha \right)\cap {D}_{3}|=1$ , or $|V\left(D,\alpha \right)\cap {D}_{1}|=1$ , $|V\left(D,\alpha \right)\cap {D}_{3}|\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 $|V\left(D,\alpha \right)\cap {D}_{1}|=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 $|V\left(D,\alpha \right)\cap {D}_{1}|\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 $|V\left(D,\alpha \right)\cap {D}_{2}|=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 $|V\left(D,\alpha \right)\cap {D}_{2}|\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 $|V\left(D,\alpha \right)\cap {D}_{3}|=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 $|V\left(D,\alpha \right)\cap {D}_{3}|\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 $|V\left(D,\alpha \right)\cap {D}_{1}|=1,|V\left(D,\alpha \right)\cap {D}_{3}|=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,\text{\hspace{0.17em}}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 $|V\left(D,\alpha \right)\cap {D}_{1}|=1,|V\left(D,\alpha \right)\cap {D}_{3}|\ge 2$ , or $|V\left(D,\alpha \right)\cap {D}_{1}|\ge 2,|V\left(D,\alpha \right)\cap {D}_{3}|=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}\text{\hspace{0.17em}}j=1,2,\cdots ,k;\\ {\mathfrak{A}}_{2}=\left\{\left\{{Z}_{j},\stackrel{⌣}{D}\right\}\right\},\text{where}\text{\hspace{0.17em}}j=1,2,\cdots ,n+k;\\ {\mathfrak{A}}_{3}=\left\{\left\{{Z}_{n+j},{Z}_{j}\right\}\right\},\text{where}\text{\hspace{0.17em}}j=1,2,\cdots ,k;\\ {\mathfrak{A}}_{4}=\left\{\left\{{Z}_{j}\right\},\left\{\stackrel{⌣}{D}\right\}\right\},\text{where}\text{\hspace{0.17em}}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 }×{Z}_{n+j}\right)\cup \left({Y}_{j}^{\alpha }×{Z}_{j}\right)\cup \left({Y}_{0}^{\alpha }×\stackrel{⌣}{D}\right),$

where ${Y}_{n+j}^{\alpha },{Y}_{j}^{\alpha },{Y}_{0}^{\alpha }\notin \left\{\varnothing \right\}$ 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 }×{Z}_{n+j}\right)\cup \left({Y}_{j}^{\delta }×{Z}_{j}\right)\cup \left({Y}_{q}^{\delta }×{Z}_{q}\right)\cup \left({Y}_{0}^{\delta }×\stackrel{⌣}{D}\right),\\ \beta =\left(\text{}{Z}_{n+j}×{Z}_{n+j}\right)\cup \left(\left({Z}_{j}\{Z}_{n+j}\right)×{Z}_{j}\right)\cup \left(\left(\stackrel{⌣}{D}\{Z}_{j}\right)×{Z}_{q}\right)\cup \left(\left(X\\stackrel{⌣}{D}\right)×\stackrel{⌣}{D}\right),\end{array}$

where ${Y}_{n+j}^{\alpha },{Y}_{j}^{\alpha },{Y}_{q}^{\alpha }\notin \left\{\varnothing \right\},{Z}_{1}\le {Z}_{q}\le {Z}_{k},q\ne j,\text{}j=1,\cdots ,k$ .

$\begin{array}{l}{Z}_{n+j}\cup \left({Z}_{j}\{Z}_{n+j}\right)\cup \left(\stackrel{⌣}{D}\{Z}_{j}\right)\cup \left(X\\stackrel{⌣}{D}\right)\\ =\left({P}_{0}\cup \underset{\begin{array}{l}\text{}i=1,\text{}\\ i\ne j,n+j\end{array}}{\overset{n+k}{\cup }}{P}_{i}\right)\cup {P}_{n+j}\cup {P}_{j}\cup \left(X\\stackrel{⌣}{D}\right)=\stackrel{⌣}{D}\cup \left(X\\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 \underset{\begin{array}{l}i=1,\text{}\\ i\ne j\end{array}}{\overset{n+k}{\cup }}{P}_{i}\right)\beta =\left(\left({P}_{0}\cup \underset{\begin{array}{l}\text{}i=1,\text{}\\ 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 \underset{\begin{array}{l}i=1,\text{}\\ 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 =\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}\{Z}_{n+j}\right)={P}_{n+j}\ne \varnothing ,{Z}_{q}\cap \left(D\{Z}_{j}\right)={P}_{j}\ne \varnothing$ (see equality (2.0))

$\begin{array}{c}\alpha =\delta \circ \beta =\left({Y}_{n+j}^{\delta }×{Z}_{n+j}\beta \right)\cup \left({Y}_{j}^{\delta }×{Z}_{j}\beta \right)\cup \left({Y}_{q}^{\delta }×{Z}_{q}\beta \right)\cup \left({Y}_{0}^{\delta }×\stackrel{⌣}{D}\beta \right)\\ =\left({Y}_{n+j}^{\delta }×{Z}_{n+j}\right)\cup \left({Y}_{j}^{\delta }×{Z}_{j}\right)\cup \left({Y}_{q}^{\delta }×\stackrel{⌣}{D}\right)\cup \left({Y}_{0}^{\delta }×\stackrel{⌣}{D}\right)\\ =\left({Y}_{n+j}^{\delta }×{Z}_{n+j}\right)\cup \left({Y}_{j}^{\delta }×{Z}_{j}\right)\cup \left(\left({Y}_{q}^{\delta }\cup {Y}_{0}^{\delta }\right)×\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 $|{Y}_{q}^{\delta }\cup {Y}_{0}^{\delta }|\ge 1$ ( $|{Y}_{0}^{\delta }|\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 }×{Z}_{j}\right)\cup \left({Y}_{0}^{\alpha }×\stackrel{⌣}{D}\right)$ , where ${Y}_{j}^{\alpha },{Y}_{0}^{\alpha }\notin \left\{\varnothing \right\}$ , $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 }×{Z}_{j}\right)\cup \left({Y}_{q}^{\delta }×{Z}_{q}\right)\cup \left({Y}_{0}^{\delta }×\stackrel{⌣}{D}\right),\\ \beta =\left({Z}_{j}×{Z}_{j}\right)\cup \left(\left(\stackrel{⌣}{D}\{Z}_{j}\right)×{Z}_{q}\right)\cup \left(\left(X\\stackrel{⌣}{D}\right)×\stackrel{⌣}{D}\right),\end{array}$

where ${Y}_{j}^{\delta },{Y}_{q}^{\delta }\notin \left\{\varnothing \right\}$ 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\{Z}_{j}\right)={P}_{j}\ne \varnothing ,$

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

$\begin{array}{c}\delta \circ \beta =\left({Y}_{j}^{\delta }×{Z}_{j}\beta \right)\cup \left({Y}_{q}^{\delta }×{Z}_{q}\beta \right)\cup \left({Y}_{0}^{\delta }×\stackrel{⌣}{D}\beta \right)\\ =\left({Y}_{j}^{\delta }×{Z}_{j}\right)\cup \left({Y}_{q}^{\delta }×\stackrel{⌣}{D}\right)\cup \left({Y}_{0}^{\delta }×\stackrel{⌣}{D}\right)\\ =\left({Y}_{j}^{\delta }×{Z}_{j}\right)\cup \left(\left({Y}_{q}^{\delta }\cup {Y}_{0}^{\delta }\right)×\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 $|{Y}_{q}^{\delta }\cup {Y}_{0}^{\delta }|\ge 1$ ( $|{Y}_{0}^{\delta }|\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 }×{Z}_{n+j}\right)\cup \left({Y}_{j}^{\alpha }×{Z}_{j}\right)$ , where ${Y}_{n+j}^{\alpha },{Y}_{j}^{\alpha }\notin \left\{\varnothing \right\}$ , $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 }×{Z}_{n+j}\right)\cup \left({Y}_{q}^{\delta }×{Z}_{q}\right)\cup \left({Y}_{0}^{\delta }×\stackrel{⌣}{D}\right),\\ \beta =\left({Z}_{n+j}×{Z}_{n+j}\right)\cup \left(\left(\stackrel{⌣}{D}\{Z}_{n+j}\right)×{Z}_{j}\right)\cup \left(\left(X\\stackrel{⌣}{D}\right)×\stackrel{⌣}{D}\right),\end{array}$

where ${Y}_{n+j}^{\delta },{Y}_{q}^{\delta }\notin \left\{\varnothing \right\}$ , $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},\text{}$

${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}\{Z}_{n+j}\right)={P}_{n+j}\ne \varnothing ,\text{}j\ne q$ (see equality(2.0))

$\stackrel{⌣}{D}\beta ={Z}_{j}$ since $\stackrel{⌣}{D}\cap \left(X\\stackrel{⌣}{D}\right)=\varnothing ,$

$\begin{array}{c}\delta \circ \beta =\left({Y}_{n+j}^{\delta }×{Z}_{n+j}\beta \right)\cup \left({Y}_{q}^{\delta }×{Z}_{q}\beta \right)\cup \left({Y}_{0}^{\delta }×\stackrel{⌣}{D}\right)\\ =\left({Y}_{n+j}^{\delta }×{Z}_{n+j}\right)\cup \left({Y}_{q}^{\delta }×{Z}_{j}\right)\cup \left({Y}_{0}^{\delta }×{Z}_{j}\right)\\ =\left({Y}_{n+j}^{\delta }×{Z}_{n+j}\right)\cup \left(\left({Y}_{q}^{\delta }\cup {Y}_{0}^{\delta }\right)×{Z}_{j}\right)=\alpha ,\end{array}$

if ${Y}_{n+j}^{\delta }={Y}_{n+j}^{\alpha }$ and ${Y}_{q}^{\delta }\cup {Y}_{0}^{\delta }={Y}_{j}^{\alpha }$ . Last equalities are possible since $|{Y}_{q}^{\delta }\cup {Y}_{0}^{\delta }|\ge 1$ ( $|{Y}_{0}^{\delta }|\ge 0$ by preposition).

Lemma 2.5 is proved.

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

1) If quasinormal representation of a binary relation a has a form $\alpha =X×{Z}_{j}$ $\left(j=1,2,\cdots ,k\right)$ , then binary relation a is generated by elements of the set $B\left({\mathfrak{A}}_{0}\right)$ .

2) If quasinormal representation of a binary relation a has a form $\alpha =X×\stackrel{⌣}{D}$ , then binary relation a is generated by elements of the set $B\left({\mathfrak{A}}_{0}\right)$ .

Proof. 1) Let $T\in D\\left({D}_{2}\cup {D}_{3}\right)$ . If quasinormal representation of a binary relations d, b have a form

$\begin{array}{l}\delta =\left({Y}_{j}^{\delta }×{Z}_{j}\right)\cup \left({Y}_{0}^{\delta }×\stackrel{⌣}{D}\right),\\ \beta =\left({Z}_{n+j}×{Z}_{n+j}\right)\cup \left(\left({Z}_{j}\{Z}_{n+j}\right)×{Z}_{j}\right)\cup \left(\left(X\\stackrel{⌣}{D}\right)×\stackrel{⌣}{D}\right),\end{array}$

where ${Y}_{j}^{\delta },{Y}_{0}^{\delta }\in \left\{\varnothing \right\}$ , $j=1,2,\cdots ,k$

$\begin{array}{l}{Z}_{n+j}\cup \left({Z}_{j}\{Z}_{n+j}\right)\cup \left(X\\stackrel{⌣}{D}\right)\\ =\left(\underset{\begin{array}{l}\text{}i=0,\text{}\\ i\ne j,n+j\end{array}}{\overset{n+k}{\cup }}{P}_{i}\right)\cup \left({P}_{j}\cup {P}_{n+j}\right)\cup \left(X\\stackrel{⌣}{D}\right)=\stackrel{⌣}{D}\cup \left(X\\stackrel{⌣}{D}\right)=X\end{array}$

(see equalities (2.0) and (2.1)), then from the Lemma 2.4 follows that d is generated by elements of the set $B\left({\mathfrak{A}}_{0}\right)$ and from the Lemma 2.3 element b is generated by elements of the set $B\left({\mathfrak{A}}_{0}\right)$ and

${Z}_{j}\beta ={Z}_{n+j}\cup {Z}_{j}={Z}_{j},$

$\stackrel{⌣}{D}\beta ={Z}_{j}$ , since $\stackrel{⌣}{D}\cap \left(X\\stackrel{⌣}{D}\right)=\varnothing ,$

$\delta \circ \beta =\left({Y}_{j}^{\delta }×{Z}_{j}\beta \right)\cup \left({Y}_{0}^{\delta }×\stackrel{⌣}{D}\beta \right)=\left({Y}_{j}^{\delta }×{Z}_{j}\right)\cup \left({Y}_{0}^{\delta }×{Z}_{j}\right)=X×{Z}_{j}=\alpha ,$

since representation of a binary relation d is quasinormal.

The statement a) of the lemma 2.6 is proved.

2) Let quasinormal representation of a binary relation d have a form

$\delta =\left({Z}_{n+j}×{Z}_{q}\right)\cup \left(\left(X\{Z}_{n+j}\right)×\stackrel{⌣}{D}\right),$

where $j\ne q$ , then from the Lemma 2.4 follows that d is generated by elements of the set $B\left({\mathfrak{A}}_{0}\right)$ and

${Z}_{q}\delta =\left(\underset{\begin{array}{l}i=0,\text{}\\ i\ne q\end{array}}{\overset{n+k}{\cup }}{P}_{i}\right)\delta =\left(\underset{\begin{array}{l}i=0,\\ i\ne q\end{array}}{\overset{n+k}{\cup }}{P}_{i}\delta \right)={Z}_{q}\cup \stackrel{⌣}{D}=\stackrel{⌣}{D},\stackrel{⌣}{D}\delta =\stackrel{⌣}{D}$ , since $j\ne q,\text{\hspace{0.17em}}{Z}_{q}\delta \cap {Z}_{n+1}\ne \varnothing$ and ${Z}_{q}\delta \cap \left(X\{Z}_{n+1}\right)\ne \varnothing ;$

$\begin{array}{c}\delta \circ \delta =\left({Z}_{n+j}×{Z}_{q}\delta \right)\cup \left(\left(X\{Z}_{n+j}\right)×\stackrel{⌣}{D}\delta \right)\\ =\left({Z}_{n+j}×\stackrel{⌣}{D}\right)\cup \left(\left(X\{Z}_{n+j}\right)×\stackrel{⌣}{D}\right)=X×\stackrel{⌣}{D}=\alpha \end{array}$ ,

since representation of a binary relation d is quasinormal.

The statement b) of the lemma 2.6 is proved.

Lemma 2.6 is proved.

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

a) If $|X\\stackrel{⌣}{D}|\ge 1$ and $T\in {D}_{2}\cup {D}_{3}$ , then binary relation $\alpha =X×T$ is generated by elements of the elements of set $B\left({\mathfrak{A}}_{0}\right)$ ;

b) If $X=\stackrel{⌣}{D}$ and $T\in {D}_{2}\cup {D}_{3}$ , then binary relation $\alpha =X×T$ is external element for the semigroup ${B}_{X}\left(D\right)$ .

Proof. 1) If quasinormal representation of a binary relation d has a form

$\delta =\left({Y}_{0}^{\delta }×\stackrel{⌣}{D}\right)\cup \underset{j=k+1}{\overset{n+k}{\cup }}\left({Y}_{j}^{\delta }×{Z}_{j}\right)$ ,

where ${Y}_{j}^{\delta }\ne \varnothing$ for all $j=k+1,k+2,\cdots ,n+k$ , then $\delta \in B\left({\mathfrak{A}}_{0}\right)\\left\{\alpha \right\}$ . Let quasinormal representation of a binary relations b have a form

$\beta =\left(\stackrel{⌣}{D}×T\right)\cup \underset{{t}^{\prime }\in X\\stackrel{⌣}{D}}{\cup }\left(\left\{{t}^{\prime }\right\}×f\left({t}^{\prime }\right)\right)$ , where f is any mapping of the set $X\\stackrel{⌣}{D}$ in the set $\left({D}_{2}\cup {D}_{3}\right)\\left\{T\right\}$ . It is easy to see, that $\beta \ne \alpha$ and two elements of the set ${D}_{2}\cup {D}_{3}$ belong to the semilattice $V\left(D,\beta \right)$ , i.e. $\delta \in B\left({\mathfrak{A}}_{0}\right)\\left\{\alpha \right\}$ . In this case we have that ${Z}_{j}\beta =T$ for all $j=k+1,k+2,\cdots ,n+k$ .

$\begin{array}{c}\delta \circ \beta =\delta =\left({Y}_{0}^{\delta }×\stackrel{⌣}{D}\beta \right)\cup \underset{j=k+1}{\overset{n+k}{\cup }}\left({Y}_{j}^{\delta }×{Z}_{j}\beta \right)\\ =\left({Y}_{0}^{\delta }×T\right)\cup \underset{j=k+1}{\overset{n+k}{\cup }}\left({Y}_{j}^{\delta }×T\right)\\ =\left(\left({Y}_{0}^{\delta }\cup \underset{j=k+1}{\overset{n+k}{\cup }}{Y}_{j}^{\delta }\right)×T\right)=X×T=\alpha ,\end{array}$

since the representation of a binary relation d is quasinormal. Thus, the element a is generated by elements of the set $B\left({\mathfrak{A}}_{0}\right)$ .

The statement a) of the lemma 2.7 is proved.

2) Let $X=\stackrel{⌣}{D}$ , $\alpha =X×T$ , for some $T\in {D}_{2}\cup {D}_{3}$ and $\alpha =\delta \circ \beta$ for some $\delta ,\beta \in {B}_{X}\left(D\right)\\left\{\alpha \right\}$ . Then we obtain that ${Z}_{j}\beta =T$ since T is a minimal element of the semilattice D.

Now, let subquasinormal representations $\stackrel{¯}{\beta }$ of a binary relation b have a form

$\stackrel{¯}{\beta }=\left(\left(\underset{i=0}{\overset{n+k}{\cup }}{P}_{i}\right)×T\right)\cup \underset{{t}^{\prime }\in X\\stackrel{⌣}{D}}{\cup }\left(\left\{{t}^{\prime }\right\}×{\stackrel{¯}{\beta }}_{2}\left({t}^{\prime }\right)\right)$ ,

where ${\stackrel{¯}{\beta }}_{1}=\left(\begin{array}{l}{P}_{0}\text{}{P}_{1}\text{}{P}_{2}\text{}\cdots \text{}{P}_{n+k}\\ T\text{}T\text{}T\text{}\cdots \text{}T\text{}\end{array}\right)$ is normal mapping. But complement mapping ${\stackrel{¯}{\beta }}_{2}$ is empty, since $X\\stackrel{⌣}{D}=\varnothing$ , i.e. in the given case, subquasinormal representation $\stackrel{¯}{\beta }$ of a binary relation b is defined uniquely. So, we have that $\beta =\stackrel{¯}{\beta }=X×T=\alpha$ (see property 2) in the case 1.1), which contradict the condition, that $\beta \notin {B}_{X}\left(D\right)\\left\{\alpha \right\}$ .

Therefore, if $X=\stackrel{⌣}{D}$ and $\alpha =X×T$ , for some $T\in {D}_{2}\cup {D}_{3}$ , then a is external element of the semigroup ${B}_{X}\left(D\right)$ .

The statement 2) of the Lemma 2.7 is proved.

Lemma 2.7 is proved.

Theorem 2.1. Let $D\in {\Sigma }_{8}\left(X,n+k+1\right)$ , $k\ge 3$ , and

${D}_{1}=\left\{{Z}_{1},{Z}_{2},\cdots ,{Z}_{k}\right\},\text{}{D}_{2}=\left\{{Z}_{k+1},{Z}_{k+2},\cdots ,{Z}_{n}\right\},\text{}{D}_{3}=\left\{{Z}_{n+1},{Z}_{n+2},\cdots ,{Z}_{n+k}\right\};$

${\mathfrak{A}}_{1}=\left\{\left\{{Z}_{n+q},{Z}_{q},\stackrel{⌣}{D}\right\}\right\},\text{where}\text{\hspace{0.17em}}q=1,2,\cdots ,k;$

${\mathfrak{A}}_{2}=\left\{\left\{{Z}_{j},\stackrel{⌣}{D}\right\}\right\},\text{\hspace{0.17em}}\text{where}\text{\hspace{0.17em}}j=1,2,\cdots ,n+k;$

${\mathfrak{A}}_{3}=\left\{\left\{{Z}_{n+j},{Z}_{j}\right\}\right\},\text{where}\text{\hspace{0.17em}}j=1,2,\cdots ,k;$

${\mathfrak{A}}_{4}=\left\{\left\{{Z}_{j}\right\},\left\{\stackrel{⌣}{D}\right\}\right\},\text{\hspace{0.17em}}\text{where}\text{\hspace{0.17em}}j=1,2,\cdots ,n+k;$

${\mathfrak{A}}_{0}=\left\{V\left(D,\alpha \right)\subset 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\},$

${B}_{0}=\left\{X×T|T\notin {D}_{2}\cup {D}_{3}\right\}$

Then the following statements are true:

1) If $|X\\stackrel{⌣}{D}|\ge 1$ , then the ${S}_{0}=B\left({\mathfrak{A}}_{0}\right)$ is irreducible generating set for the semigroup ${B}_{X}\left(D\right)$ ;

2) If $X=\stackrel{⌣}{D}$ , then the ${S}_{1}={B}_{0}\cup B\left({\mathfrak{A}}_{0}\right)$ is irreducible generating set for the semigroup ${B}_{X}\left(D\right)$ .

Proof. Let $D\in {\Sigma }_{8}\left(X,n+k+1\right)$ , $k\ge 3$ and $|X\\stackrel{⌣}{D}|\ge 1$ . First, we proved that every element of the semigroup ${B}_{X}\left(D\right)$ is generated by elements of the set ${S}_{0}$ . Indeed, let a be an arbitrary element of the semigroup ${B}_{X}\left(D\right)$ . Then quasinormal representation of a binary relation a has a form

$\alpha =\left({Y}_{0}^{\alpha }×\stackrel{⌣}{D}\right)\cup \underset{i=1}{\overset{n+k}{\cup }}\left({Y}_{i}^{\alpha }×{Z}_{i}\right)$ ,

where $\underset{i=0}{\overset{n+k}{\cup }}{Y}_{i}^{\alpha }=X$ and ${Y}_{i}^{\alpha }\cap {Y}_{j}^{\alpha }=\varnothing$ $\left(0\le i\ne j\le n+k\right)$ . For the $V\left({X}^{\ast },\alpha \right)$ we consider the following cases:

1) If $V\left({X}^{\ast },\alpha \right)\notin {\mathfrak{A}}_{1}\cup {\mathfrak{A}}_{2}\cup {\mathfrak{A}}_{3}\cup {\mathfrak{A}}_{4}$ , then $\alpha \in B\left({\mathfrak{A}}_{0}\right)\subseteq {S}_{0}$ by definition of a set ${S}_{0}$ .

Now, let $V\left({X}^{\ast },\alpha \right)\in {\mathfrak{A}}_{1}\cup {\mathfrak{A}}_{2}\cup {\mathfrak{A}}_{3}\cup {\mathfrak{A}}_{4}$ .

2) If $V\left({X}^{\ast },\alpha \right)\in {\mathfrak{A}}_{1}$ , then quasinormal representation of a binary relation a has a form $\alpha =\left({Y}_{n+j}^{\alpha }×{Z}_{n+j}\right)\cup \left({Y}_{j}^{\alpha }×{Z}_{j}\right)\cup \left({Y}_{0}^{\alpha }×\stackrel{⌣}{D}\right)$ , where ${Y}_{n+j}^{\alpha },{Y}_{j}^{\alpha },{Y}_{0}^{\alpha }\notin \left\{\varnothing \right\}$ $\left(j=1,2,\cdots ,k\right)$ and from the Lemma 2.3 follows that a is generated by elements of the elements of set $B\left({\mathfrak{A}}_{0}\right)\subseteq {S}_{0}$ by definition of a set ${S}_{0}$ .

3) If $V\left({X}^{\ast },\alpha \right)\in {\mathfrak{A}}_{2}$ , then quasinormal representation of a binary relation a has a form $\alpha =\left({Y}_{j}^{\alpha }×{Z}_{j}\right)\cup \left({Y}_{0}^{\alpha }×\stackrel{⌣}{D}\right)$ , where ${Y}_{j}^{\alpha },{Y}_{0}^{\alpha }\notin \left\{\varnothing \right\}$ , $j=1,2,\cdots ,n+k$ and from the Lemma 2.4 follows that a is generated by elements of the elements of set $B\left({\mathfrak{A}}_{0}\right)\subseteq {S}_{0}$ by definition of a set ${S}_{0}$ .

4) If $V\left({X}^{\ast },\alpha \right)\in {\mathfrak{A}}_{3}$ , then quasinormal representation of a binary relation a has a form $\alpha =\left({Y}_{n+j}^{\alpha }×{Z}_{n+j}\right)\cup \left({Y}_{j}^{\alpha }×{Z}_{j}\right)$ , where ${Y}_{n+j}^{\alpha },{Y}_{j}^{\alpha }\notin \left\{\varnothing \right\}$ , $j=1,2,\cdots ,k$ and from the Lemma 2.5 follows that a is generated by elements of the elements of set $B\left({\mathfrak{A}}_{0}\right)\subseteq {S}_{0}$ by definition of a set ${S}_{0}$ .

Now, let $V\left({X}^{\ast },\alpha \right)\in {\mathfrak{A}}_{4}$ , then quasinormal representation of a binary relation a has a form $\alpha =X×\stackrel{⌣}{D}$ , or $\alpha =X×{Z}_{j}$ , where $j=1,2,\cdots ,n+k$ .

5) If $\alpha =X×\stackrel{⌣}{D}$ , then from the statement b) of the Lemma 2.6 follows that binary relation a is generated by elements of the set $B\left({\mathfrak{A}}_{0}\right)$ .

6) If $\alpha =X×{Z}_{j}$ , where $j=1,2,\cdots ,n+k$ , then from the statement a) of the Lemma 2.6 and 2.7 follows that binary relation a is generated by elements of the set $B\left({\mathfrak{A}}_{0}\right)$ .

Thus, we have that ${S}_{0}$ is a generating set for the semigroup ${B}_{X}\left(D\right)$ .

If $|X\\stackrel{⌣}{D}|\ge 1$ , then the set ${S}_{0}$ is an irreducible generating set for the semigroup ${B}_{X}\left(D\right)$ since, ${S}_{0}$ is a set external elements of the semigroup ${B}_{X}\left(D\right)$ .

The statement a) of the Theorem 2.1 is proved.

Now, let $X=\stackrel{⌣}{D}$ . First, we proved that every element of the semigroup ${B}_{X}\left(D\right)$ is generated by elements of the set ${S}_{1}$ . The cases 1), 2), 3), 4) and 5) are proved analogously of the cases 1), 2), 3), 4) and 5 given above and consider case, when $V\left({X}^{\ast },\alpha \right)\in {\mathfrak{A}}_{1}$ .

If $V\left({X}^{\ast },\alpha \right)={Z}_{j}$ , where $j=1,2,\cdots ,k$ , then from the statement a) of the Lemma 2.7 follows that binary relation a is generated by elements of the set $B\left({\mathfrak{A}}_{0}\right)$ .

If $V\left({X}^{\ast },\alpha \right)={Z}_{j}$ , where ${Z}_{j}\in {D}_{2}\cup {D}_{3}$ , then from the statement b) of the Lemma 2.6 follows that binary relation $\alpha =X×T$ is external element for the semigroup ${B}_{X}\left(D\right)$ .

Thus, we have that ${S}_{1}$ is a generating set for the semigroup ${B}_{X}\left(D\right)$ .

If $X=\stackrel{⌣}{D}$ , then the set ${S}_{1}$ is an irreducible generating set for the semigroup ${B}_{X}\left(D\right)$ since ${S}_{1}$ is a set external elements of the semigroup ${B}_{X}\left(D\right)$ .

The statement b) of the Theorem 2.1 is proved.

Theorem 2.1 is proved.

Corollary 2.1. Let $D\in {\Sigma }_{8}\left(X,n+k+1\right)$ $\left(k\ge 3\right)$ and

${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\};$

${\mathfrak{A}}_{1}=\left\{\left\{{Z}_{n+q},{Z}_{q},\stackrel{⌣}{D}\right\}\right\},\text{where}\text{\hspace{0.17em}}q=1,2,\cdots ,k;$

${\mathfrak{A}}_{2}=\left\{\left\{{Z}_{j},\stackrel{⌣}{D}\right\}\right\},\text{where}\text{\hspace{0.17em}}j=1,2,\cdots ,n+k;$

${\mathfrak{A}}_{3}=\left\{\left\{{Z}_{n+j},{Z}_{j}\right\}\right\},\text{where}\text{\hspace{0.17em}}j=1,2,\cdots ,k;$

${\mathfrak{A}}_{4}=\left\{\left\{{Z}_{j}\right\},\left\{\stackrel{⌣}{D}\right\}\right\},\text{where}\text{\hspace{0.17em}}j=1,2,\cdots ,n+k;$

${\mathfrak{A}}_{0}=\left\{V\left(D,\alpha \right)\subset 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\},$

${B}_{0}=\left\{X×T|T\notin {D}_{2}\cup {D}_{3}\right\}$

Then the following statements are true:

1) If $|X\\stackrel{⌣}{D}|\ge 1$ , then ${S}_{0}=B\left({\mathfrak{A}}_{0}\right)$ is the uniquely defined generating set for the semigroup ${B}_{X}\left(D\right)$ ;

2) If $X=\stackrel{⌣}{D}$ , then ${S}_{1}={B}_{0}\cup B\left({\mathfrak{A}}_{0}\right)$ is the uniquely defined generating set for the semigroup ${B}_{X}\left(D\right)$ .

Proof. 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   Lemma 1.15.1). From this follows that the sets ${S}_{0}=B\left({\mathfrak{A}}_{0}\right)$ and ${S}_{1}={B}_{0}\cup B\left({\mathfrak{A}}_{0}\right)$ are defined uniquely, since they are sets external elements of the semigroup ${B}_{X}\left(D\right)$ .

Corollary 2.1 is proved.

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 }$ (Definition 1.1).

In this article, we find irredusible generating set for the complete semigroups of binary relations defined by X-semilattices of unions of the class ${\Sigma }_{8}\left(X,n+k+1\right)$ $\left(k\ge 3\right)$ . This generating set is uniquely defined, since they are defined by elements of the external elements of the semigroup ${B}_{X}\left(D\right)$ .

Cite this paper: Diasamidze, Y. , Givradze, O. , Tsinaridze, N. and Tavdgiridze, G. (2018) Generated Sets of the Complete Semigroup Binary Relations Defined by Semilattices of the Class Σ8 (X, n + k + 1). Applied Mathematics, 9, 369-382. doi: 10.4236/am.2018.94028.
References

   Diasamidze, Y. and Makharadze, S. (2013) Complete Semigroups of Binary Relations. Kriter, Turkey, 1-519.

   Я. И. Диасамидзе, Ш. И. Махарадзе (2017) Полные полугруппы бинарных отношений. Lambert Academic Publishing, 1-692.

Top