considered implicitly in Section 5.4. The unrestricted wreath product of $M$
with $\mathcal{T}_{X}$ is the semidirect product
$M^{\mathcal{T}_{X}}\rtimes\mathcal{T}_{X}$.)

There are (at least) two standard ways to generalise this construction of
$M\wr\mathcal{T}_{X}$ in order to define $M\wr\mathcal{P}\mathcal{T}_{X}$:
either as a suitable subsemigroup or quotient of a semidirect product
$M_{0}^{X}\rtimes\mathcal{P}\mathcal{T}_{X}$, where $M_{0}$ is $M$ with a zero
adjoined. These definitions are of course interchangeable, but among other
things we will see in this chapter that action pairs provide a natural
mechanism for passing between the two viewpoints. When $M$ is a group,
$M\wr\mathcal{P}\mathcal{T}_{X}$ is isomorphic to the partial endomorphism
monoid of a free $M$-act of rank $|X|$. Since free group-acts are (strong)
independence algebras, it follows that the results of this chapter and those
of Chapter 8 have a common specialisation. We will sometimes be able to use
results from Chapter 8 to assist in proofs in the current chapter.

We begin in Section 9.1 with definitions and basic results, including that
$M\wr\mathcal{P}\mathcal{T}_{X}$ is a left restriction monoid, and we comment
on the above connection with free group-acts. The rest of Chapter 9 then
proceeds in two largely parallel strands. In Sections 9.2 and 9.5 we identify
two families of action pairs in $M\wr\mathcal{P}\mathcal{T}_{X}$, leading to
natural subsemigroups such as $M\wr\mathcal{T}_{X}$, $M\wr\mathcal{I}_{X}$,
$M\wr(\mathcal{P}\mathcal{T}_{X}\setminus\mathcal{T}_{X})$,
$M\wr\operatorname{Sing}(\mathcal{P}\mathcal{T}_{X})$ for finite $X$, and so
on. Sections 9.3 and 9.6 explore ‘congruence conditions’ that feed into
general results from Chapters 4 and 6. In Sections 9.4 and 9.7 we apply these
general results to obtain presentations for several of our wreath products;
see Theorems 9.33, 9.58, 9.67, 9.68 and 9.69. Taking $M=\\{1\\}$, these
theorems reduce to well-known presentations for various (partial)
transformation semigroups [32, 1, 92, 100, 73, 28, 27, 25].

Throughout this chapter we will again often identify one-element subsets of
$X$ with their unique elements, and so use abbreviations such as $X\setminus
x\equiv X\setminus\\{x\\}$.

####  9.1 Preliminaries

Let $M$ be a monoid with identity $1$, and $X$ an arbitrary set. Let
$M_{0}=M\sqcup\\{0\\}$, where $0$ is a symbol not belonging to $M$, acting as
an adjoined zero element, even if $M$ already had a zero element.

We write $M_{0}^{X}$ for the set of all $X$-tuples ${\bf a}=(a_{x})_{x\in X}$
over $M_{0}$; we usually abbreviate such a tuple to ${\bf a}=(a_{x})$. As
usual, $M_{0}^{X}$ is a monoid under the componentwise product. The identity
of $M_{0}^{X}$ is ${\bf 1}=(1)_{x\in X}$, the $X$-tuple with all entries equal
to $1$. Before we define our wreath products, we fix some basic notation.

The _support_ of ${\bf a}=(a_{x})\in M_{0}^{X}$ is the set
$\operatorname{supp}({\bf a})=\\{{x\in X}:{a_{x}\not=0}\\}$. It is worth
noting that

$\operatorname{supp}({\bf a}{\bf b})=\operatorname{supp}({\bf
a})\cap\operatorname{supp}({\bf b})\qquad\text{for all ${\bf a},{\bf b}\in
M_{0}^{X}$.}$ (9.1)

For $B\subseteq X$, we write ${\bf 1}_{B}\in M_{0}^{X}$ for the _indicator
function_ of $B$, defined by

$\displaystyle{\bf 1}_{B}=(b_{x})$ $\displaystyle\qquad\text{where}\qquad
b_{x}=\begin{cases}\mathrlap{1}\hphantom{a_{x\alpha}}&\text{if $x\in B$,}\\\
\mathrlap{0}\hphantom{a_{x\alpha}}&\text{if $x\in X\setminus B$.}\end{cases}$
For ${\bf a}=(a_{x})\in M_{0}^{X}$, and for $B\subseteq X$, we write ${\bf
a}\mathord{\restriction}_{B}\in M_{0}^{X}$ for the _restriction of ${\bf a}$
to $B$_, defined by $\displaystyle{\bf a}\mathord{\restriction}_{B}={\bf
a}\cdot{\bf 1}_{B}={\bf 1}_{B}\cdot{\bf a}=(b_{x})$
$\displaystyle\qquad\text{where}\qquad
b_{x}=\begin{cases}\mathrlap{a_{x}}\hphantom{a_{x\alpha}}&\text{if $x\in
B$,}\\\ \mathrlap{0}\hphantom{a_{x\alpha}}&\text{if $x\in X\setminus
B$.}\end{cases}$ Note that $\operatorname{supp}({\bf
a}\mathord{\restriction}_{B})=\operatorname{supp}({\bf a})\cap B$. The partial
transformation monoid $\mathcal{P}\mathcal{T}_{X}$ has a left action on
$M_{0}^{X}$ by semigroup morphisms, defined for
$\alpha\in\mathcal{P}\mathcal{T}_{X}$ and ${\bf a}=(a_{x})\in M_{0}^{X}$ by
$\displaystyle{}^{\alpha}{\bf a}=(b_{x})$
$\displaystyle\qquad\text{where}\qquad b_{x}=\begin{cases}a_{x\alpha}&\text{if
$x\in\operatorname{dom}(\alpha)$,}\\\ 0&\text{otherwise.}\end{cases}$ (9.2)

It is worth noting that there are two ways for $b_{x}$ to equal $0$ in (9.2);
either $x\not\in\operatorname{dom}(\alpha)$ or else
$x\in\operatorname{dom}(\alpha)$ and $a_{x\alpha}=0$. This means that

$\operatorname{supp}({}^{\alpha}{\bf a})=\operatorname{supp}({\bf
a})\alpha^{-1}=\big{\\{}{x\in\operatorname{dom}(\alpha)}:{x\alpha\in\operatorname{supp}({\bf
a})}\big{\\}}\qquad\text{for all ${\bf a}\in M_{0}^{X}$ and
$\alpha\in\mathcal{P}\mathcal{T}_{X}$.}$ (9.3)

The action from (9.2) has a natural diagrammatic interpretation, as shown in
Figure 2 with $X=\\{1,\ldots,6\\}$ and
$\alpha=\left(\begin{smallmatrix}1&2&3&4&5&6\\\
2&-&3&2&6&6\end{smallmatrix}\right)$.

$\alpha$$a_{1}$$a_{2}$$a_{3}$$a_{4}$$a_{5}$$a_{6}$${\bf
a}$$\alpha$$a_{2}$$a_{3}$$a_{2}$$a_{6}$$a_{6}$$0$${}^{\alpha}{\bf a}$

Figure 2: The action of $\alpha\in\mathcal{P}\mathcal{T}_{X}$ on ${\bf a}\in
M_{0}^{X}$ from (9.2), with $X=\\{1,\ldots,6\\}$.

It is clear that the action in (9.2) is monoidal: i.e., that
${}^{\mathrm{id}_{X}}{\bf a}={\bf a}$ for all ${\bf a}\in M_{0}^{X}$. It is
not, however, by monoid morphisms, as for any
$\alpha\in\mathcal{P}\mathcal{T}_{X}$, we have ${}^{\alpha}{\bf 1}={\bf
1}_{\operatorname{dom}(\alpha)}$. It follows from this that

${}^{\alpha}{\bf 1}={\bf 1}\ \Leftrightarrow\ \alpha\in\mathcal{T}_{X}.$ (9.4)

For any subsemigroup $S\leq\mathcal{P}\mathcal{T}_{X}$, the action in (9.2)
leads as usual to the semidirect product

$M_{0}^{X}\rtimes S=\big{\\{}{({\bf a},\alpha)}:{{\bf a}\in M_{0}^{X},\
\alpha\in S}\big{\\}}\qquad\text{with operation}\qquad({\bf
a},\alpha)\cdot({\bf b},\beta)=({\bf a}\cdot{}^{\alpha}{\bf b},\alpha\beta).$

If $S$ is a submonoid of $\mathcal{P}\mathcal{T}_{X}$, then $({\bf
1},\mathrm{id}_{X})$ is a left identity for $M_{0}^{X}\rtimes S$, as the
action is monoidal, but it is only a right identity when the action of $S$ on
$M_{0}^{X}$ is by monoid morphisms; by (9.4), this is equivalent to having
$S\subseteq\mathcal{T}_{X}$. This all follows from Lemma 3.11, or by examining
products of the form

$({\bf a},\alpha)\cdot({\bf 1},\mathrm{id}_{X})=({\bf a}\cdot{}^{\alpha}{\bf
1},\alpha)=({\bf a}\cdot{\bf 1}_{\operatorname{dom}(\alpha)},\alpha)=({\bf
a}\mathord{\restriction}_{\operatorname{dom}(\alpha)},\alpha).$ (9.5)

In any case, when $S$ is a submonoid of $\mathcal{P}\mathcal{T}_{X}$, the
local monoid of $M_{0}^{X}\rtimes S$ with identity $({\bf 1},\mathrm{id}_{X})$
is $({\bf 1},\mathrm{id}_{X})\cdot(M_{0}^{X}\rtimes S)\cdot({\bf
1},\mathrm{id}_{X})=(M_{0}^{X}\rtimes S)\cdot({\bf 1},\mathrm{id}_{X})$. Using
(9.5) it is easy to see that this is

$(M_{0}^{X}\rtimes S)\cdot({\bf 1},\mathrm{id}_{X})=\big{\\{}{({\bf
a},\alpha)\in M_{0}^{X}\rtimes S}:{\operatorname{supp}({\bf
a})\subseteq\operatorname{dom}(\alpha)}\big{\\}}.$ (9.6)

This leads us naturally to the following:

######  Definition 9.7.

For any set $X$, any subsemigroup $S$ of $\mathcal{P}\mathcal{T}_{X}$, and any
monoid $M$, the _(transformational) wreath product_ $M\wr S$ is the set

$M\wr S=\big{\\{}{({\bf a},\alpha)\in M_{0}^{X}\rtimes
S}:{\operatorname{supp}({\bf a})=\operatorname{dom}(\alpha)}\big{\\}}.$

It is routine to check that $M\wr S$ is a subsemigroup of $M_{0}^{X}\rtimes
S$. Indeed, given $({\bf a},\alpha),({\bf b},\beta)\in M\wr S$, we have $({\bf
a},\alpha)\cdot({\bf b},\beta)=({\bf a}\cdot{}^{\alpha}{\bf b},\alpha\beta)$,
and (9.1) and (9.3) give

$\operatorname{supp}({\bf a}\cdot{}^{\alpha}{\bf b})=\operatorname{supp}({\bf
a})\cap\operatorname{supp}({\bf
b})\alpha^{-1}=\operatorname{dom}(\alpha)\cap\operatorname{dom}(\beta)\alpha^{-1}=\operatorname{dom}(\alpha\beta).$

Wreath products of this kind (and similar) have been studied by numerous
authors. See for example [18, 69, 70, 71, 72, 11, 109, 15, 85, 79]. The
introduction to [70] discusses some of the early history of the idea, going
back to the work of Specht [110].

######  Remark 9.8.

If $S\subseteq\mathcal{T}_{X}$, then every element $({\bf a},\alpha)\in M\wr
S$ satisfies ${\operatorname{supp}({\bf a})=\operatorname{dom}(\alpha)=X}$:
i.e., ${\bf a}\in M^{X}$. In this case, we have $M\wr S=M^{X}\rtimes S$.

Given (9.5), it is clear that $M\wr S$ is a monoid whenever $S$ is a submonoid
of $\mathcal{P}\mathcal{T}_{X}$.

The elements of $M\wr\mathcal{P}\mathcal{T}_{X}$, and their products, have a
natural diagrammatic representation, which will be useful in all the
calculations to follow. Figure 3 gives an example with ${X=\\{1,\ldots,6\\}}$,
and

$\alpha=\left(\begin{smallmatrix}1&2&3&4&5&6\\\
2&-&3&2&6&6\end{smallmatrix}\right)\qquad\text{and}\qquad\beta=\left(\begin{smallmatrix}1&2&3&4&5&6\\\
1&1&-&4&-&4\end{smallmatrix}\right).$

When drawing an element $({\bf a},\alpha)$ of
$M\wr\mathcal{P}\mathcal{T}_{X}$, we omit the label $a_{x}$ of upper vertex
$x$ if this label is $0$. We will also often omit the label if it is $1$. One
can tell whether an omitted label is $0$ or $1$ by the non/existence of an
edge at that vertex. See Figures 4–10.

$a_{1}$$a_{3}$$a_{4}$$a_{5}$$a_{6}$$b_{1}$$b_{2}$$b_{4}$$b_{6}$$a_{1}b_{2}$$a_{4}b_{2}$$a_{5}b_{6}$$a_{6}b_{6}$

Figure 3: Elements of $M\wr\mathcal{P}\mathcal{T}_{X}$ (left) and their
product (right), with $X=\\{1,\ldots,6\\}$.

An important special case arises when $M$ is a group, when wreath products can
be viewed as (partial) endomorphism monoids.

######  Example 9.9.

For an arbitrary monoid $M$, the class of $M$-acts forms a variety.
Consequently, free $M$-acts exist, and a number of equivalent
characterisations exist; see for example [69]. Roughly speaking, the free
$M$-act of rank $\rho$ can be thought of as $\rho$ disjoint copies of $M$,
with the action coinciding with multiplication in $M$. More formally, given a
set $X$, the _free (left) $M$-act over $X$_ is the algebra $F_{X}(M)$ with:

  * •

underlying set $M\times X$, and

  * •

a unary operation $f_{a}$ for each $a\in M$, defined by $f_{a}(b,x)=(ab,x)$.

It is known [117] that $F_{X}(M)$ is an independence algebra (of dimension
$|X|$) if and only if $M$ is a group. In this case, we have

$\displaystyle\operatorname{PEnd}(F_{X}(M))$ $\displaystyle\cong
M\wr\mathcal{P}\mathcal{T}_{X},$ $\displaystyle\operatorname{PAut}(F_{X}(M))$
$\displaystyle\cong M\wr\mathcal{I}_{X},$
$\displaystyle\operatorname{End}(F_{X}(M))$ $\displaystyle\cong
M\wr\mathcal{T}_{X},$ $\displaystyle\operatorname{Aut}(F_{X}(M))$
$\displaystyle\cong M\wr\mathcal{G}_{X}.$

For example, the isomorphism $\operatorname{PAut}(F_{X}(M))\cong
M\wr\mathcal{I}_{X}$ (with $X$ finite) was demonstrated in [11, Theorem 2.2],
and the argument there works virtually unchanged for the others (for any $X$).
Thus, the group case of any result proved in this chapter can also be viewed
as a special case of a result from Chapter 8 (when $A$ is a free group-act).

When $M$ is not a group, we do not have the above isomorphisms. Indeed, the
proof in the group case relies on the fact that the subalgebras of $F_{X}(M)$
are all of the form $F_{Y}(M)=M\times Y$ for some $Y\subseteq X$, but this is
no longer true when $M$ is not a group. For example, $I\times X$ is a
subalgebra of $F_{X}(M)$ for any left ideal $I\subseteq M$. More generally,
one can show that the subalgebras of $F_{X}(M)$ are precisely the subsets of
the form $\bigcup_{y\in Y}(I_{y}\times\\{y\\})$, where $Y$ is an arbitrary
subset of $X$, and where each $I_{y}$ ($y\in Y$) is a left ideal of $M$. (When
$M$ is a group, each $I_{y}=M$, as groups have no proper non-empty left
ideals, and then the subalgebra in question is just $M\times Y=F_{Y}(M)$.)

Returning now to the more general discussion of wreath products, we fix a
monoid $M$, a set $X$, and a subsemigroup $S\leq\mathcal{P}\mathcal{T}_{X}$.
It is important to note that $M\wr S$ contains a natural copy of $S$, namely:

$S\equiv\big{\\{}{({\bf 1}_{\operatorname{dom}(\alpha)},\alpha)}:{\alpha\in
S}\big{\\}}.$

In this way, $M\wr\mathcal{P}\mathcal{T}_{X}$ contains the semilattice

$\mathcal{E}_{X}=\\{{\mathrm{id}_{B}}:{B\subseteq X}\\}\equiv\big{\\{}{({\bf
1}_{B},\mathrm{id}_{B})}:{B\subseteq X}\big{\\}}$

of partial identities. As in Chapter 8, we also write
$\operatorname{Sing}(\mathcal{E}_{X})=\mathcal{E}_{X}\setminus\\{\mathrm{id}_{X}\\}$.

It is easy to see that for all $({\bf a},\alpha)\in
M\wr\mathcal{P}\mathcal{T}_{X}$ and $B\subseteq X$, we have

$\mathrm{id}_{B}\cdot({\bf a},\alpha)=({\bf
a}\mathord{\restriction}_{B},\alpha\mathord{\restriction}_{B})\qquad\text{and}\qquad({\bf
a},\alpha)\cdot\mathrm{id}_{B}=\mathrm{id}_{B\alpha^{-1}}\cdot({\bf
a},\alpha).$ (9.10)

Figures 4 and 5 illustrate these identities, with $X=\\{1,\ldots,6\\}$,
$B=\\{1,2,4,5\\}$, and $\alpha=\left(\begin{smallmatrix}1&2&3&4&5&6\\\
2&-&3&2&6&6\end{smallmatrix}\right)$.

$a_{1}$$a_{3}$$a_{4}$$a_{5}$$a_{6}$$a_{1}$$a_{4}$$a_{5}$

Figure 4: An example of $\mathrm{id}_{B}\cdot({\bf a},\alpha)=({\bf
a}\mathord{\restriction}_{B},\alpha\mathord{\restriction}_{B})$ in
$M\wr\mathcal{P}\mathcal{T}_{X}$, with $X=\\{1,\ldots,6\\}$.

$a_{1}$$a_{3}$$a_{4}$$a_{5}$$a_{6}$$a_{1}$$a_{3}$$a_{4}$$a_{5}$$a_{6}$$a_{1}$$a_{4}$

Figure 5: An example of $({\bf
a},\alpha)\cdot\mathrm{id}_{B}=\mathrm{id}_{B\alpha^{-1}}\cdot({\bf
a},\alpha)$ in $M\wr\mathcal{P}\mathcal{T}_{X}$, with $X=\\{1,\ldots,6\\}$.

The next result is crucial in all that follows. As far as we are aware, it has
not been stated explicitly in the literature. Of course it follows from
Proposition 8.16 in the special case that $M$ is a group, when
$M\wr\mathcal{P}\mathcal{T}_{X}\cong\operatorname{PEnd}(F_{X}(M))$ is the
partial endomorphism monoid of the (independence) algebra $F_{X}(M)$.

######  Proposition 9.11.

For any set $X$ and monoid $M$, the wreath product
$M\wr\mathcal{P}\mathcal{T}_{X}$ is a left restriction monoid under the unary
operation $({\bf
a},\alpha)^{+}=\alpha^{+}=\mathrm{id}_{\operatorname{dom}(\alpha)}\equiv({\bf
1}_{\operatorname{dom}(\alpha)},\mathrm{id}_{\operatorname{dom}(\alpha)})$.

###### Proof.

The identities (L1) and (L2) are clear. For (L3) and (L4), we use (9.10). We
just give the details for (L4), as (L3) is easier. So consider elements
$x=({\bf a},\alpha)$ and $y=({\bf b},\beta)$ from
$M\wr\mathcal{P}\mathcal{T}_{X}$, and write $B=\operatorname{dom}(\beta)$.
Then

$xy^{+}=({\bf
a},\alpha)\cdot\mathrm{id}_{B}\qquad\text{and}\qquad(xy)^{+}x=\mathrm{id}_{D}\cdot({\bf
a},\alpha)\qquad\text{where}\qquad
D=\operatorname{dom}(\alpha\beta)=B\alpha^{-1},$

so $xy^{+}=(xy)^{+}x$ follows from the second identity in (9.10). ∎

In the notation of Section 4.3, we have

$\displaystyle P(M\wr\mathcal{P}\mathcal{T}_{X})$
$\displaystyle=\big{\\{}{({\bf a},\alpha)^{+}}:{({\bf a},\alpha)\in
M\wr\mathcal{P}\mathcal{T}_{X}}\big{\\}}=\mathcal{E}_{X}$ (9.12)
$\displaystyle\text{and}\qquad T(M\wr\mathcal{P}\mathcal{T}_{X})$
$\displaystyle=\big{\\{}{({\bf a},\alpha)\in
M\wr\mathcal{P}\mathcal{T}_{X}}:{({\bf
a},\alpha)^{+}=\mathrm{id}_{X}}\big{\\}}=M\wr\mathcal{T}_{X}.$ (9.13)

Next we note that we may also identify $M_{0}^{X}$ with a submonoid of
$M\wr\mathcal{P}\mathcal{T}_{X}$:

$M_{0}^{X}\equiv\big{\\{}{({\bf a},\mathrm{id}_{\operatorname{supp}({\bf
a})})}:{{\bf a}\in M_{0}^{X}}\big{\\}}.$

For ${\bf a}\in M_{0}^{X}$ and $\alpha\in\mathcal{P}\mathcal{T}_{X}$, we have

$\displaystyle{\bf a}\cdot\alpha$ $\displaystyle=({\bf
a}\mathord{\restriction}_{B},\alpha\mathord{\restriction}_{C})$ where
$B=\operatorname{dom}(\alpha)$ and $C=\operatorname{supp}({\bf a})$
$\displaystyle=({\bf
a}\mathord{\restriction}_{D},\alpha\mathord{\restriction}_{D})$ where
$D=\operatorname{dom}(\alpha)\cap\operatorname{supp}({\bf a})$. (9.14)

This is illustrated in Figure 6, with $X=\\{1,\ldots,6\\}$, $C=\\{1,2,4,5\\}$
and $\alpha=\left(\begin{smallmatrix}1&2&3&4&5&6\\\
2&-&3&2&6&6\end{smallmatrix}\right)$. In particular, if $({\bf a},\alpha)\in
M\wr\mathcal{P}\mathcal{T}_{X}$, then $\operatorname{supp}({\bf
a})=\operatorname{dom}(\alpha)$, and so $({\bf a},\alpha)={\bf a}\cdot\alpha$.
It is also important to note that

$\alpha\cdot{\bf a}={}^{\alpha}{\bf a}\cdot\alpha\qquad\text{for all ${\bf
a}\in M_{0}^{X}$ and $\alpha\in\mathcal{P}\mathcal{T}_{X}$.}$ (9.15)

Indeed, this can be verified by directly showing that both sides evaluate to
$(({}^{\alpha}{\bf
a})\mathord{\restriction}_{\operatorname{dom}(\alpha)},\alpha\mathord{\restriction}_{\operatorname{supp}({}^{\alpha}{\bf
a})})$, keeping in mind the identifications $\alpha\equiv({\bf
1}_{\operatorname{dom}(\alpha)},\alpha)$, etc. It is also easy to see
diagrammatically; cf. Figure 2.

$a_{1}$$a_{2}$$a_{4}$$a_{5}$$a_{1}$$a_{4}$$a_{5}$

Figure 6: An example of ${\bf a}\cdot\alpha=({\bf
a}\mathord{\restriction}_{\operatorname{dom}(\alpha)},\alpha\mathord{\restriction}_{\operatorname{supp}({\bf
a})})$ in $M\wr\mathcal{P}\mathcal{T}_{X}$, with $X=\\{1,\ldots,6\\}$.

The remainder of this chapter will be split into two largely parallel strands,
each dealing with one family of action pairs:

  * •

Sections 9.2–9.4 concern pairs of the form $(E,S)$, where $E=\mathcal{E}_{X}$
or $\operatorname{Sing}(\mathcal{E}_{X})$, and where $S\leq
M\wr\mathcal{T}_{X}$.

  * •

Sections 9.5–9.7 concern pairs of the form $(U,S)$, where $U=M_{0}^{X}$ or
$M^{X}$, and where $S\leq\mathcal{P}\mathcal{T}_{X}$.

The pairs of the first type are all strong, as are some (but not all) of the
second type. No pair of the first type is proper (apart from trivially small
exceptions), but some of the second type are proper.

####  9.2 Action pairs and subsemigroups I

Here is the first family of action pairs in $M\wr\mathcal{P}\mathcal{T}_{X}$:

######  Proposition 9.16.

For any set $X$ and monoid $M$, the following are all strong action pairs in
${M\wr\mathcal{P}\mathcal{T}_{X}}$_:_

  1. (i)

$(\mathcal{E}_{X},M\wr\mathcal{T}_{X})$,

  2. (ii)

$(\operatorname{Sing}(\mathcal{E}_{X}),M\wr\mathcal{T}_{X})$,

  3. (iii)

$(\mathcal{E}_{X},M\wr\operatorname{Sing}(\mathcal{T}_{X}))$ if
$|X|<\aleph_{0}$,

  4. (iv)

$(\operatorname{Sing}(\mathcal{E}_{X}),M\wr\operatorname{Sing}(\mathcal{T}_{X}))$
if $|X|<\aleph_{0}$,

  5. (v)

$(\mathcal{E}_{X},M\wr\mathcal{G}_{X})$,

  6. (vi)

$(\operatorname{Sing}(\mathcal{E}_{X}),M\wr\mathcal{G}_{X})$.

###### Proof.

This follows from Propositions 4.44 and 9.11, together with (9.12) and (9.13).
∎

The next result characterises the semigroups $ES$ arising from the pairs
$(E,S)$ in Proposition 9.16. Again, parts (iii) and (iv) do not assume that
$X$ is finite, even though
$\operatorname{Sing}(\mathcal{T}_{X})=\mathcal{T}_{X}\setminus\mathcal{G}_{X}$
and
$\operatorname{Sing}(\mathcal{P}\mathcal{T}_{X})=\mathcal{P}\mathcal{T}_{X}\setminus\mathcal{G}_{X}$
are not semigroups for infinite $X$; in these cases,
$M\wr\operatorname{Sing}(\mathcal{T}_{X})$ simply refers to the relevant
_subset_ of $M\wr\mathcal{T}_{X}$, and similarly for
$M\wr\operatorname{Sing}(\mathcal{P}\mathcal{T}_{X})$. (The $|X|=1$ cases are
excluded in these parts because the left-hand sets are empty, and the right-
hand sets contain the empty map.) For parts (v) and (vi), we again write

$\mathcal{F}_{X}=\big{\\{}{\alpha\in\mathcal{I}_{X}}:{|X\setminus\operatorname{dom}(\alpha)|=|X\setminus\operatorname{im}(\alpha)|}\big{\\}}.$

As discussed in Remark 8.63, $\mathcal{F}_{X}$ is the largest factorisable
inverse submonoid of $\mathcal{I}_{X}$ [14]. Note that
$\operatorname{Sing}(\mathcal{F}_{X})=\mathcal{F}_{X}\setminus\mathcal{G}_{X}$
is always an (almost-factorisable inverse) subsemigroup of $\mathcal{F}_{X}$,
even when $X$ is infinite; cf. Example 4.27.

######  Proposition 9.17.

For any set $X$ and monoid $M$, we have:

  1. (i)

$\mathcal{E}_{X}\cdot(M\wr\mathcal{T}_{X})=M\wr\mathcal{P}\mathcal{T}_{X}$,

  2. (ii)

$\operatorname{Sing}(\mathcal{E}_{X})\cdot(M\wr\mathcal{T}_{X})=M\wr(\mathcal{P}\mathcal{T}_{X}\setminus\mathcal{T}_{X})$,

  3. (iii)

$\mathcal{E}_{X}\cdot(M\wr\operatorname{Sing}(\mathcal{T}_{X}))=M\wr\operatorname{Sing}(\mathcal{P}\mathcal{T}_{X})$
if $|X|\not=1$,

  4. (iv)

$\operatorname{Sing}(\mathcal{E}_{X})\cdot(M\wr\operatorname{Sing}(\mathcal{T}_{X}))=M\wr(\mathcal{P}\mathcal{T}_{X}\setminus\mathcal{T}_{X})$
if $|X|\not=1$,

  5. (v)

$\mathcal{E}_{X}\cdot(M\wr\mathcal{G}_{X})=M\wr\mathcal{F}_{X}\subseteq
M\wr\mathcal{I}_{X}$, with equality if and only if $|X|<\aleph_{0}$,

  6. (vi)

$\operatorname{Sing}(\mathcal{E}_{X})\cdot(M\wr\mathcal{G}_{X})=M\wr\operatorname{Sing}(\mathcal{F}_{X})\subseteq
M\wr\operatorname{Sing}(\mathcal{I}_{X})$, with equality if and only if
$|X|<\aleph_{0}$.

###### Proof.

The proof is straightforward, and in each case we can use the relevant part of
Theorems 8.56 and 8.61, applied to
$\operatorname{PEnd}(A)=\mathcal{P}\mathcal{T}_{X}$, where $A=X$ is viewed as
an independence algebra with no operations.

For example, in (iii), the main work is in showing the backwards inclusion.
For this, consider some $({\bf a},\alpha)$ from
$M\wr\operatorname{Sing}(\mathcal{P}\mathcal{T}_{X})$, where $|X|\not=1$. By
Theorem 8.56(iii) we have $\alpha=\mathrm{id}_{B}\cdot\beta$ for some
$\beta\in\operatorname{Sing}(\mathcal{T}_{X})$, where
$B=\operatorname{dom}(\alpha)$. And then for any ${\bf b}\in M^{X}$ with ${\bf
a}={\bf b}\mathord{\restriction}_{B}$, we have $({\bf
a},\alpha)=\mathrm{id}_{B}\cdot({\bf b},\beta)$, with $({\bf b},\beta)\in
M\wr\operatorname{Sing}(\mathcal{T}_{X})$. ∎

######  Remark 9.18.

As in Remark 8.59, and again excluding trivially small exceptions, none of the
action pairs $(E,S)$ listed in Proposition 9.16 are proper. Hence (cf.
Proposition 5.29), none of the left restriction semigroups $ES$ in Proposition
9.17 are proper. But by Theorem 5.39 each $ES$ is covered by the proper left
restriction semigroup

$\big{\\{}{(\mathrm{id}_{B},({\bf a},\alpha))\in E\rtimes
S}:{\mathrm{id}_{B}=\mathrm{id}_{B}\cdot({\bf
a},\alpha)^{+}}\big{\\}}=\big{\\{}{(\mathrm{id}_{B},({\bf a},\alpha))\in
E\rtimes S}:{B\subseteq\operatorname{dom}(\alpha)}\big{\\}}.$

####  9.3 Congruence conditions I

In Section 9.4 we will use the results of Chapter 6 to give presentations for
the semigroups arising from (some of) the pairs from Proposition 9.16. We
first examine which of the simplifying conditions on the right congruences
hold for these pairs.

######  Lemma 9.19.

Let $(E,S)$ be one of the (strong) action pairs in
$M\wr\mathcal{P}\mathcal{T}_{X}$ listed in Proposition 9.16, with the
exception of
$(E,S)=(\operatorname{Sing}(\mathcal{E}_{X}),M\wr\mathcal{T}_{X})$ in the case
that $|X|\geq\aleph_{0}$. Then $(E,S)$ satisfies at least one of the
conditions listed in Lemma 4.61.

###### Proof.

This is proved in similar fashion to Lemma 8.65. Again, the cases in which
$E=\mathcal{E}_{X}$ are clear, and for those involving
$E=\operatorname{Sing}(\mathcal{E}_{X})$ it reduces to checking (using
Proposition 9.17) that any element $({\bf a},\alpha)$ of the semigroup $ES$
satisfies $\operatorname{im}(\alpha)\not=X$. ∎

As in Section 8.7, we now restrict our attention to the pairs $(E,S)$ from
Proposition 9.16 in which

  * •

$E=\mathcal{E}_{X}$, and

  * •

$S$ is one of $M\wr\mathcal{T}_{X}$,
$M\wr\operatorname{Sing}(\mathcal{T}_{X})$ or $M\wr\mathcal{G}_{X}$, where we
must additionally assume that $|X|<\aleph_{0}$ in the second case.

We are particularly concerned with determining which of the stronger
congruence conditions considered in Section 4.5 and Chapter 6 are satisfied by
these pairs. Recall that these conditions were stated in terms of the right
congruences on $S$ or $S^{1}$ defined, for each $B\subseteq X$, by

$\displaystyle\theta_{\mathrm{id}_{B}}$ $\displaystyle=\big{\\{}{(({\bf
a},\alpha),({\bf b},\beta))\in S\times S}:{\mathrm{id}_{B}\cdot({\bf
a},\alpha)=\mathrm{id}_{B}\cdot({\bf b},\beta)}\big{\\}}$
$\displaystyle=\big{\\{}{(({\bf a},\alpha),({\bf b},\beta))\in S\times
S}:{{\bf a}\mathord{\restriction}_{B}={\bf b}\mathord{\restriction}_{B},\
\alpha\mathord{\restriction}_{B}=\beta\mathord{\restriction}_{B}}\big{\\}}$
for $S=M\wr\mathcal{T}_{X}$ and $S=M\wr\mathcal{G}_{X}$, and
$\displaystyle\Theta_{\mathrm{id}_{B}}$ $\displaystyle=\big{\\{}{(({\bf
a},\alpha),({\bf b},\beta))\in S^{1}\times S^{1}}:{\mathrm{id}_{B}\cdot({\bf
a},\alpha)=\mathrm{id}_{B}\cdot({\bf b},\beta)}\big{\\}}$
$\displaystyle=\big{\\{}{(({\bf a},\alpha),({\bf b},\beta))\in S^{1}\times
S^{1}}:{{\bf a}\mathord{\restriction}_{B}={\bf b}\mathord{\restriction}_{B},\
\alpha\mathord{\restriction}_{B}=\beta\mathord{\restriction}_{B}}\big{\\}}$

for $S=M\wr\operatorname{Sing}(\mathcal{T}_{X})$, where
$S^{1}=(M\wr\operatorname{Sing}(\mathcal{T}_{X}))\cup\\{\mathrm{id}_{X}\\}$.
Again we will abbreviate these to $\theta_{B}$ and $\Theta_{B}$. Note that we
do not use the sub(semi)groups $S_{B}$ in the case of $S=M\wr\mathcal{G}_{X}$,
since this is not a group in general, even though $\mathcal{G}_{X}$ is.

######  Lemma 9.20.

If $S=M\wr\mathcal{T}_{X}$ for any $X$, then
$\theta_{B}\vee\theta_{C}=\theta_{B\cap C}$ for any $B,C\subseteq X$.

###### Proof.

This follows quickly from Proposition 8.70. We need to show that any pair
$(({\bf a},\alpha),({\bf b},\beta))$ from $\theta_{B\cap C}$ belongs to
$\theta_{B}\vee\theta_{C}$, so fix some such pair. Since
$\alpha\mathord{\restriction}_{B\cap C}=\beta\mathord{\restriction}_{B\cap
C}$, the pair $(\alpha,\beta)$ belongs to the ‘$\theta_{B\cap C}$ relation of
$\mathcal{T}_{X}$’. So we let $\gamma\in\mathcal{T}_{X}$ be as in the proof of
Proposition 8.70, so that
$\gamma\mathord{\restriction}_{B}=\alpha\mathord{\restriction}_{B}$ and
$\gamma\mathord{\restriction}_{C}=\beta\mathord{\restriction}_{C}$. Since
${\bf a}\mathord{\restriction}_{B\cap C}={\bf b}\mathord{\restriction}_{B\cap
C}$, we may also define

${\bf c}=(c_{x})\qquad\text{where}\qquad c_{x}=\begin{cases}a_{x}&\text{if
$x\in B$,}\\\ b_{x}&\text{if $x\in C$,}\\\ 1&\text{otherwise,}\end{cases}$
(9.21)

and then $({\bf a},\alpha)\mathrel{\theta}_{B}({\bf
c},\gamma)\mathrel{\theta}_{C}({\bf b},\beta)$. ∎

######  Lemma 9.22.

If $S=M\wr\operatorname{Sing}(\mathcal{T}_{X})$ for $|X|<\aleph_{0}$, then
$\Theta_{B}\vee\Theta_{C}=\Theta_{B\cap C}$ for any $B,C\subseteq X$.

###### Proof.

This is similar to the proof of Lemma 9.20, with a little care taken for the
$|X|=2$ case (cf. Proposition 8.71 and Remark 8.76).

Beginning with the case $|X|\not=2$, we fix some $(({\bf a},\alpha),({\bf
b},\beta))$ from $\Theta_{B\cap C}$, aiming to show it belongs to
$\Theta_{B}\vee\Theta_{C}$. We let $\gamma_{1},\gamma_{2},\gamma_{3}$ be as in
the proof of Proposition 8.71 (Case 1 or 3), and take ${\bf c}$ as in (9.21),
and we have $({\bf a},\alpha)\mathrel{\Theta}_{B}({\bf
c},\gamma_{1})\mathrel{\Theta}_{C}({\bf
c},\gamma_{2})\mathrel{\Theta}_{B}({\bf
c},\gamma_{3})\mathrel{\Theta}_{C}({\bf b},\beta)$.

For the $|X|=2$ case, we assume without loss of generality that $X=\\{1,2\\}$.
We need only show that $\Theta_{B}\vee\Theta_{C}=\Theta_{B\cap C}$ when $B$
and $C$ are incomparable, and by symmetry the only case to consider is
$B=\\{1\\}$ and $C=\\{2\\}$. Since $B\cap C=\varnothing$ and
$\Theta_{\varnothing}$ is the universal relation, we must show that every
element of $M\wr\operatorname{Sing}(\mathcal{T}_{X})$ is
$(\Theta_{B}\vee\Theta_{C})$-related to $\mathrm{id}_{X}$. So fix some such
$({\bf a},\alpha)\in M\wr\operatorname{Sing}(\mathcal{T}_{X})$. By symmetry,
we may assume that $\alpha=\left(\begin{smallmatrix}1&2\\\
1&1\end{smallmatrix}\right)$. Write ${\bf a}=(a_{1},a_{2})$, and set ${\bf
b}=(1,a_{2})$. Then $({\bf a},\alpha)\mathrel{\Theta}_{C}({\bf
b},\alpha)\mathrel{\Theta}_{B}\mathrm{id}_{X}$. ∎

Lemmas 9.20 and 9.22 allow us to simplify presentations for
$M\wr\mathcal{P}\mathcal{T}_{X}$ and
$M\wr\operatorname{Sing}(\mathcal{P}\mathcal{T}_{X})$ arising from Theorems
6.4 and 6.35; see Remark 6.5 and Theorem 6.43(ii). To utilise these results,
we need generators for the right congruences $\theta_{B}$ and $\Theta_{B}$ in
the case that $|X\setminus B|=1$, and for these we first recall the definition
of certain idempotents from $\mathcal{T}_{X}$. Given distinct $x,y\in X$, we
denote by $\varepsilon_{xy}\in\mathcal{T}_{X}$ the unique idempotent with
image $X\setminus y$ and mapping $y\mapsto x$. That is,

$z\varepsilon_{xy}=\begin{cases}z&\text{if $z\in X\setminus y$,}\\\ x&\text{if
$z=y$.}\end{cases}$ (9.23)

See Figure 7 for $\varepsilon_{24}$ and $\varepsilon_{42}$, with
$X=\\{1,\ldots,6\\}$, but ignore the vertex labels.

######  Lemma 9.24.

If $S=M\wr\mathcal{T}_{X}$ for any $X$, and if $B=X\setminus y$ for some $y\in
X$, then $\theta_{B}$ is generated as a right congruence by any pair
$(\varepsilon_{xy},\mathrm{id}_{X})$ with $x\in B$.

###### Proof.

Let $\sigma$ be the right congruence generated by the stated pair. Since
$\mathrm{id}_{B}=\mathrm{id}_{B}\cdot\varepsilon_{xy}$, we have
$\sigma\subseteq\theta_{B}$. For the reverse inclusion, let $(({\bf
a},\alpha),({\bf b},\beta))\in\theta_{B}$. So ${\bf
a}\mathord{\restriction}_{B}={\bf b}\mathord{\restriction}_{B}$ and
$\alpha\mathord{\restriction}_{B}=\beta\mathord{\restriction}_{B}$, and from
these it quickly follows that $\varepsilon_{xy}\cdot({\bf
a},\alpha)=\varepsilon_{xy}\cdot({\bf b},\beta)$. Since
$\mathrm{id}_{X}\mathrel{\sigma}\varepsilon_{xy}$, and since $\sigma$ is a
right congruence, we have

$({\bf a},\alpha)=\mathrm{id}_{X}\cdot({\bf
a},\alpha)\mathrel{\sigma}\varepsilon_{xy}\cdot({\bf
a},\alpha)=\varepsilon_{xy}\cdot({\bf
b},\beta)\mathrel{\sigma}\mathrm{id}_{X}\cdot({\bf b},\beta)=({\bf
b},\beta).\qed$

The proof of the next result is essentially identical.

######  Lemma 9.25.

If $S=M\wr\operatorname{Sing}(\mathcal{T}_{X})$ for $|X|<\aleph_{0}$, and if
$B=X\setminus y$ for some $y\in X$, then $\Theta_{B}$ is generated as a right
congruence by any pair $(\varepsilon_{xy},\mathrm{id}_{X})$ with $x\in B$. ∎

######  Remark 9.26.

In Lemmas 9.24 and 9.25, since the right congruences $\theta_{B}$ and
$\Theta_{B}$ are generated by the pair $(\varepsilon_{xy},\mathrm{id}_{X})$
for _any_ $x\in B=X\setminus y$, they are also generated by the set
$\big{\\{}{(\varepsilon_{xy},\mathrm{id}_{X})}:{x\in B}\big{\\}}$ of _all_
such pairs.

We now move on to the case of $S=M\wr\mathcal{G}_{X}$, for which we must
assume $X$ is finite. It will be convenient to first give generators for the
right congruences $\theta_{B}$ for arbitrary $B\subseteq X$. To describe
these, we begin with some notation. For $x\in X$ and $a\in M$, we write ${\bf
t}_{x;a}\in M^{X}$ for the $X$-tuple whose $x$th coordinate is $a$, and all
other entries are $1$. For distinct $x,y\in X$, we write
$\tau_{xy}\in\mathcal{G}_{X}$ for the transposition that interchanges $x$ and
$y$.

For the next lemma and its proof, recall that we identify a tuple ${\bf a}\in
M^{X}$ with the element $({\bf a},\mathrm{id}_{X})$ of $M\wr\mathcal{T}_{X}$.
The statement gives a generating set $\Omega_{B}$ for the right congruence
$\theta_{B}$, and $\Omega_{B}$ is a union of two sets of pairs. A typical pair
from the first has the form $({\bf t}_{x;a},\mathrm{id}_{X})$, and as just
mentioned this is shorthand for the pair $({\bf
t}_{x;a},\mathrm{id}_{X})\equiv(({\bf t}_{x;a},\mathrm{id}_{X}),({\bf
1},\mathrm{id}_{X}))$. Similar comments apply to the second set, where we
identify $(\tau_{xy},\mathrm{id}_{X})\equiv(({\bf 1},\tau_{xy}),({\bf
1},\mathrm{id}_{X}))$.

######  Lemma 9.27.

Suppose $S=M\wr\mathcal{G}_{X}$ for $|X|<\aleph_{0}$, and let $\Gamma$ be a
(monoid) generating set for $M$. Then for any $B\subseteq X$, $\theta_{B}$ is
generated as a right congruence by the set

$\Omega_{B}=\big{\\{}{({\bf t}_{x;a},\mathrm{id}_{X})}:{x\in X\setminus B,\
a\in\Gamma}\big{\\}}\cup\big{\\{}{(\tau_{xy},\mathrm{id}_{X})}:{x,y\in
X\setminus B,\ x\not=y}\big{\\}}.$

###### Proof.

Let $\sigma$ be the right congruence generated by $\Omega_{B}$. It is easy to
check that $\Omega_{B}\subseteq\theta_{B}$, so we have
$\sigma\subseteq\theta_{B}$. It remains to show that
$\theta_{B}\subseteq\sigma$.

First we claim that

${\bf t}_{x;a}\mathrel{\sigma}\mathrm{id}_{X}\qquad\text{for all $x\in
X\setminus B$ and $a\in M$.}$ (9.28)

To prove this, write $a=c_{1}\cdots c_{k}$, where
$c_{1},\ldots,c_{k}\in\Gamma$. Since $({\bf
t}_{x;c_{i}},\mathrm{id}_{X})\in\Omega_{B}\subseteq\sigma$ for all $i$, it
follows from Lemma 2.1 that ${\bf t}_{x;a}={\bf t}_{x;c_{1}}\cdots{\bf
t}_{x;c_{k}}\mathrel{\sigma}\mathrm{id}_{X}$, and (9.28) is proved.

Now let $(({\bf a},\alpha),({\bf b},\beta))\in\theta_{B}$, so that ${\bf
a}\mathord{\restriction}_{B}={\bf b}\mathord{\restriction}_{B}$ and
$\alpha\mathord{\restriction}_{B}=\beta\mathord{\restriction}_{B}$. We must
show that $({\bf a},\alpha)\mathrel{\sigma}({\bf b},\beta)$. We begin by
defining

${\bf c}\in M^{X}\qquad\text{where}\qquad
c_{x}=\begin{cases}a_{x}=b_{x}&\text{if $x\in B$,}\\\ 1&\text{if $x\in
X\setminus B$.}\end{cases}$

Without loss of generality, we may assume that $X\setminus B=\\{1,\ldots,k\\}$
for some $k$, and we note that (9.28) gives ${\bf
t}_{i;a_{i}}\mathrel{\sigma}\mathrm{id}_{X}$ for all $1\leq i\leq k$. It
follows from Lemma 2.1 that ${\bf t}_{1;a_{1}}\cdots{\bf
t}_{k;a_{k}}\mathrel{\sigma}\mathrm{id}_{X}$. Since $\sigma$ is a right
congruence, it follows from this that ${\bf a}={\bf t}_{1;a_{1}}\cdots{\bf
t}_{k;a_{k}}\cdot{\bf c}\mathrel{\sigma}\mathrm{id}_{X}\cdot{\bf c}={\bf c}$,
and then in turn that $({\bf a},\alpha)={\bf a}\cdot\alpha\mathrel{\sigma}{\bf
c}\cdot\alpha$.

A symmetrical calculation gives $({\bf b},\beta)\mathrel{\sigma}{\bf
c}\cdot\beta$, so we can complete the proof by showing that ${{\bf
c}\cdot\alpha\mathrel{\sigma}{\bf c}\cdot\beta}$. Since
$\alpha\mathord{\restriction}_{B}=\beta\mathord{\restriction}_{B}$, we have
${}^{\alpha^{-1}}{\bf c}={}^{\beta^{-1}}{\bf c}$ (the action is defined in
(9.2)), so if we write ${\bf d}$ for this tuple, then we have ${\bf
c}\cdot\alpha=\alpha\cdot{\bf d}$ and ${\bf c}\cdot\beta=\beta\cdot{\bf d}$.
(Indeed, for the former we have $\alpha\cdot{\bf d}={}^{\alpha}{\bf
d}\cdot\alpha={}^{\alpha}({}^{\alpha^{-1}}{\bf c})\cdot\alpha={\bf
c}\cdot\alpha$, and the latter is similar.) Since $\sigma$ is a right
congruence, it therefore suffices to show that $\alpha\mathrel{\sigma}\beta$.
In fact, since $\alpha=\alpha\beta^{-1}\cdot\beta$ and
$\beta=\mathrm{id}_{X}\cdot\beta$, it is enough to show that
$\alpha\beta^{-1}\mathrel{\sigma}\mathrm{id}_{X}$.

From $\alpha\mathord{\restriction}_{B}=\beta\mathord{\restriction}_{B}$, we
see that $\alpha\beta^{-1}$ fixes $B$ pointwise, so we may write
$\alpha\beta^{-1}=\tau_{y_{1}z_{1}}\cdots\tau_{y_{l}z_{l}}$ as a product of
transpositions, where $y_{i},z_{i}\in X\setminus B$ for each $i$. Since
$(\tau_{y_{i}z_{i}},\mathrm{id}_{X})\in\Omega_{B}\subseteq\sigma$ for all $i$,
it follows from Lemma 2.1 that
$\alpha\beta^{-1}=\tau_{y_{1}z_{1}}\cdots\tau_{y_{l}z_{l}}\mathrel{\sigma}\mathrm{id}_{X}$,
as required. ∎

In Lemma 9.30 we show that the right congruences $\theta_{B}$ on
$S=M\wr\mathcal{G}_{X}$ satisfy condition (i) of Lemma 4.71. In order to do
this, it is first convenient to prove the next lemma, which shows that the
stronger condition (ii) of the same lemma _almost_ holds.

######  Lemma 9.29.

If $S=M\wr\mathcal{G}_{X}$ for $|X|<\aleph_{0}$, then
$\theta_{B}\vee\theta_{C}=\theta_{B\cap C}$ for any $B,C\subseteq X$ with
$(X\setminus B)\cap(X\setminus C)\not=\varnothing$.

###### Proof.

Write $\sigma=\theta_{B}\vee\theta_{C}$; as usual, it is enough to show that
$\theta_{B\cap C}\subseteq\sigma$. For this, it suffices to show that the
generating set $\Omega_{B\cap C}$ is contained in $\sigma$ (cf. Lemma 9.27).
Much of $\Omega_{B\cap C}$ is in fact contained in $\Omega_{B}\cup\Omega_{C}$
(keeping $X\setminus(B\cap C)=(X\setminus B)\cup(X\setminus C)$ in mind). Up
to symmetry, any pair belonging to $\Omega_{B\cap
C}\setminus(\Omega_{B}\cup\Omega_{C})$ has the form
$(\tau_{xy};\mathrm{id}_{X})$, for some $x\in X\setminus B$ and $y\in
X\setminus C$. By assumption we may fix some $z\in(X\setminus
B)\cap(X\setminus C)$, and we note that
$(\tau_{xz};\mathrm{id}_{X})\in\Omega_{B}\subseteq\sigma$ and
$(\tau_{yz};\mathrm{id}_{X})\in\Omega_{C}\subseteq\sigma$. It then follows
from Lemma 2.1 that
$\tau_{xy}=\tau_{xz}\tau_{yz}\tau_{xz}\mathrel{\sigma}\mathrm{id}_{X}$, which
completes the proof. ∎

######  Lemma 9.30.

Let $S=M\wr\mathcal{G}_{X}$ for $|X|=n<\aleph_{0}$, and let $Q=\\{{B\subseteq
X}:{n-2\leq|B|\leq n-1}\\}$. Then for any $B\subseteq X$, we have

$\theta_{B}=\bigvee_{C\in Q,\atop B\subseteq C}\theta_{C}.$

###### Proof.

If $B=X$, then $\theta_{B}=\Delta_{S}$, the stated join is empty, and the
result is trivial. If $|B|=n-1$ then we take $k=1$ and $C_{1}=B$.

Now suppose $|B|\leq n-2$, and write $X\setminus B=\\{x_{1},\ldots,x_{l}\\}$,
noting that $l\geq 2$. For $1\leq i<l$ let
$C_{i}=X\setminus\\{x_{i},x_{i+1}\\}\in Q$, so that $B=C_{1}\cap\cdots\cap
C_{l-1}$. Iterating Lemma 9.29, we obtain

$\theta_{B}=\theta_{C_{1}\cap\cdots\cap
C_{l-1}}=\theta_{C_{1}}\vee\cdots\vee\theta_{C_{l-1}}\subseteq\bigvee_{C\in
Q,\atop B\subseteq C}\theta_{C}.$

By (4.70), this completes the proof. ∎

####  9.4 Presentations I

It is now possible to give explicit presentations for the three semigroups

  * •

$M\wr\mathcal{P}\mathcal{T}_{X}=\mathcal{E}_{X}\cdot(M\wr\mathcal{T}_{X})$,

  * •

$M\wr\mathcal{I}_{X}=\mathcal{E}_{X}\cdot(M\wr\mathcal{G}_{X})$, and

  * •

$M\wr\operatorname{Sing}(\mathcal{P}\mathcal{T}_{X})=\mathcal{E}_{X}\cdot(M\wr\operatorname{Sing}(\mathcal{T}_{X}))$,

where $M$ is an arbitrary monoid, and where $X$ is finite. Without loss of
generality we may assume that $X={\bf n}=\\{1,\ldots,n\\}$ for some fixed
integer $n$, and to avoid trivialities we assume that $n\geq 2$. As usual, we
denote the semigroups involved by $\mathcal{E}_{n}$, $\mathcal{T}_{n}$, and so
on.

In what follows, we just give the full details for
$M\wr\operatorname{Sing}(\mathcal{P}\mathcal{T}_{n})$, and indicate how to
proceed for $M\wr\mathcal{P}\mathcal{T}_{X}$ and $M\wr\mathcal{I}_{X}$ in
Remark 9.39; these other two (and more) will be treated fully in Section 9.7.

To deal with
$M\wr\operatorname{Sing}(\mathcal{P}\mathcal{T}_{n})=\mathcal{E}_{n}\cdot(M\wr\operatorname{Sing}(\mathcal{T}_{n}))$,
we need presentations for $\mathcal{E}_{n}$ and
${M\wr\operatorname{Sing}(\mathcal{T}_{n})}$. The following is well known (see
for example [89, p. 115]), and is also a special case of Theorem 8.40.

######  Theorem 9.31.

For $n\geq 0$, the semilattice
$\mathcal{E}_{n}=\\{{\mathrm{id}_{A}}:{A\subseteq{\bf n}}\\}$ has presentation
$\textup{{Mon}}\langle{X_{E}}:{R_{E}}\rangle$ via
$\phi_{E}:X_{E}^{*}\to\mathcal{E}_{n}$, where:

  * •

$X_{E}=\\{t_{1},\ldots,t_{n}\\}$,

  * •

$t_{i}\phi_{E}=\mathrm{id}_{{\bf n}\setminus i}$ for all $i$,

  * •

$R_{E}=\big{\\{}{(t_{i}^{2},t_{i})}:{i\in{\bf
n}}\big{\\}}\cup\big{\\{}{(t_{i}t_{j},t_{j}t_{i})}:{i,j\in{\bf n}}\big{\\}}$.
∎

Next we recall the presentation for $M\wr\operatorname{Sing}(\mathcal{T}_{n})$
from [41]. For distinct $i,j\in{\bf n}$, and for $a,b\in M$, we define

$\varepsilon_{ij;ab}=({\bf c},\varepsilon_{ij})\in
M\wr\operatorname{Sing}(\mathcal{T}_{n})\qquad\text{where}\qquad
c_{k}=\begin{cases}a&\text{if $k=i$,}\\\ b&\text{if $k=j$,}\\\ 1&\text{if
$k\in{\bf n}\setminus\\{i,j\\}$.}\end{cases}$

See Figure 7 for two examples with $n=6$.

$a$$b$$b$$a$

Figure 7: The generators $\varepsilon_{24;ab}$ (left) and
$\varepsilon_{42;ab}$ (right) from $M\wr\operatorname{Sing}(\mathcal{T}_{6})$.

The following is Theorem 5.2 of [41]. Theorem 5.9 of the same paper gives a
presentation in terms of the smaller (all-idempotent) generating set

$\\{{\varepsilon_{ij;1b}}:{i,j\in{\bf n},\ i\not=j,\ b\in M}\\}$

in the special case that the underlying monoid $M$ has the property that its
left ideals are totally ordered under inclusion. In particular this property
holds for groups, as they have no proper non-empty left ideals. In the next
statement, we abbreviate $e_{ij;11}$ to $e_{ij}$ in the last two relations. We
display relations as equations, so writing $u=v$ instead of $(u,v)$, for
readability; we also do this for several subsequent presentations. (Note that
${\operatorname{Sing}(\mathcal{T}_{n})=\varnothing}$ if $n<2$.)

######  Theorem 9.32.

For $n\geq 2$, the wreath product $M\wr\operatorname{Sing}(\mathcal{T}_{n})$
has presentation $\textup{{Sgp}}\langle{X_{S}}:{R_{S}}\rangle$ via
$\phi_{S}:X_{S}^{+}\to M\wr\operatorname{Sing}(\mathcal{T}_{n})$, where:

  * •

$X_{S}=\\{{e_{ij;ab}}:{i,j\in{\bf n},\ i\not=j,\ a,b\in M}\\}$,

  * •

$e_{ij;ab}\phi_{S}=\varepsilon_{ij;ab}$ for all $i,j,a,b$,

  * •

$R_{S}$ consists of the following relations, with ${a,b,c,d\in M}$ arbitrary,
and $i,j,k,l\in{\bf n}$ distinct, in each:

$\displaystyle e_{ij;ab}e_{ij;cd}=e_{ij;ac,bc}$
$\displaystyle=e_{ji;ba}e_{ij;dc},$ $\displaystyle e_{ij;ab}e_{kl;cd}$
$\displaystyle=e_{kl;cd}e_{ij;ab},$ $\displaystyle e_{ik;ab}e_{jk;1c}$
$\displaystyle=e_{ik;ab},$ $\displaystyle e_{ik;ab}e_{jk;c1}$
$\displaystyle=e_{ki;ba}e_{ji;c1}e_{ik;11},$ $\displaystyle
e_{ik;aa}e_{jk;b1}$ $\displaystyle=e_{ik;11}e_{jk;b1}e_{ik;a1},$
$\displaystyle e_{ij;ab}e_{ik;cd}=e_{ik;ac,d}e_{ij;1,bc}$
$\displaystyle=e_{jk;bc,d}e_{ij;ac,1},$ $\displaystyle
e_{ij;c,ad}e_{ik;1,bd}=e_{ik;c,bd}e_{ij;1,ad}$
$\displaystyle=e_{jk;ab}e_{ij;cd},$ $\displaystyle e_{ki}e_{ij}e_{jk}$
$\displaystyle=e_{ik}e_{kj}e_{ji}e_{ik},$ $\displaystyle
e_{ki}e_{ij}e_{jk}e_{kl}$ $\displaystyle=e_{ik}e_{kl}e_{li}e_{ij}e_{jl}.$ ∎

Note that in the above relations, products in $M$ sometimes appear in
subscripts of letters from $X_{S}$, and additional commas are included to
avoid any ambiguity. For example, in the first relation, the two subscripts
from $M$ appearing in $e_{ij;ac,bc}$ are $ac$ and $bc$.

Here then is the promised presentation for
$M\wr\operatorname{Sing}(\mathcal{P}\mathcal{T}_{n})$.

######  Theorem 9.33.

For $n\geq 2$, and with the notation of Theorems 9.31 and 9.32, the wreath
product $M\wr\operatorname{Sing}(\mathcal{P}\mathcal{T}_{n})$ has presentation
$\textup{{Sgp}}\langle{X_{E}\cup X_{S}}:{R_{E}\cup R_{S}\cup R}\rangle$ via

$\Phi:(X_{E}\cup X_{S})^{+}\to
M\wr\operatorname{Sing}(\mathcal{P}\mathcal{T}_{n}):\begin{cases}e_{ij;ab}\mapsto\varepsilon_{ij;ab},\\\
t_{i}\mapsto\mathrm{id}_{{\bf n}\setminus i},\end{cases}$

where $R$ consists of the following relations, with $a,b\in M$ arbitrary, and
$i,j,k\in{\bf n}$ with $i,j$ distinct, in each:

$\displaystyle e_{ij;ab}t_{k}$ $\displaystyle=\begin{cases}e_{ij;ab}&\text{if
$k=j$,}\\\ t_{i}t_{j}e_{ij;ab}&\text{if $k=i$,}\\\
t_{k}e_{ij;ab}&\text{otherwise,}\end{cases}$ (9.34) $\displaystyle
t_{j}e_{ij}$ $\displaystyle=t_{j}.$ (9.35)

###### Proof.

This is obtained from Theorems 6.43(ii), 9.31 and 9.32, and Lemmas 9.22 and
9.25. Explicitly, these results lead to the presentation
$\textup{{Sgp}}\langle{X_{E}\cup X_{S}}:{R_{E}\cup R_{S}\cup R_{1}\cup
R_{2}^{\prime\prime}}\rangle$ via $\Phi$, where

$\displaystyle R_{1}$
$\displaystyle=\big{\\{}{(e_{ij;ab}t_{k},{}^{e_{ij;ab}}t_{k}\cdot
e_{ij;ab})}:{i,j,k\in{\bf n},\ i\not=j,\ a,b\in M}\big{\\}}$ (9.36)
$\displaystyle\qquad\text{and}\qquad R_{2}^{\prime\prime}$
$\displaystyle=\big{\\{}{(t_{j}N(\alpha),t_{j}N(\beta))}:{j\in{\bf n},\
(\alpha,\beta)\in\Omega_{j}}\big{\\}},$ (9.37)

where

  * •

${}^{e_{ij;ab}}t_{k}$ is a (possibly empty) word over $X_{E}$ mapping to
${}^{\varepsilon_{ij;ab}}\mathrm{id}_{{\bf n}\setminus k}$,

  * •

$N:M\wr\operatorname{Sing}(\mathcal{T}_{n})\to X_{S}^{+}$ is a normal form
function, and additionally $N(\mathrm{id}_{n})=\iota$, and

  * •

$\Omega_{j}$ generates $\Theta_{{\bf n}\setminus j}=\Theta_{\mathrm{id}_{{\bf
n}\setminus j}}$ as a right congruence.

(Note that $R_{3}$ from Theorem 6.43(ii) is empty because the action pair
$(\mathcal{E}_{n},\operatorname{Sing}(\mathcal{T}_{n}))$ is strong.)

By direct computation, we can take

${}^{e_{ij;ab}}t_{k}=\begin{cases}\iota&\text{if $k=j$,}\\\
t_{i}t_{j}&\text{if $k=i$,}\\\ t_{k}&\text{otherwise,}\end{cases}$

and then $R_{1}$ is precisely the set of relations in (9.34).

By Remark 9.26, we can take
$\Omega_{j}=\big{\\{}{(\varepsilon_{ij},\mathrm{id}_{X})}:{i\in{\bf
n}\setminus j}\big{\\}}$, and then $R_{2}^{\prime\prime}$ is precisely the set
of relations in (9.35). ∎

######  Remark 9.38.

The $k=i$ case of (9.34) says $e_{ij;ab}t_{i}=t_{i}t_{j}e_{ij;ab}$. One can
show that (in the presence of the other relations) this is equivalent the
slightly simpler ${e_{ij;ab}t_{i}=t_{i}t_{j}}$.

Taking $M$ to be the trivial monoid,
$M\wr\operatorname{Sing}(\mathcal{P}\mathcal{T}_{n})\equiv\operatorname{Sing}(\mathcal{P}\mathcal{T}_{n})$,
and the above presentation reduces to the main result of [32].

######  Remark 9.39.

One can adapt the above method to deal with

$M\wr\mathcal{P}\mathcal{T}_{n}=\mathcal{E}_{n}\cdot(M\wr\mathcal{T}_{n})\qquad\text{and}\qquad
M\wr\mathcal{I}_{n}=\mathcal{E}_{n}\cdot(M\wr\mathcal{G}_{n}).$

Here, in addition to the presentation for $\mathcal{E}_{n}$ from Theorem 9.31,
we need presentations for ${M\wr\mathcal{T}_{n}}$ and $M\wr\mathcal{G}_{n}$.
Since the latter are (monoid) semidirect products
$M\wr\mathcal{T}_{n}=M^{n}\rtimes\mathcal{T}_{n}$ and
${M\wr\mathcal{G}_{n}=M^{n}\rtimes\mathcal{G}_{n}}$, one could obtain such
presentations from Lavers’ Theorem 6.4. However, since we will deal with such
wreath products in Section 9.7, we do not provide the details here; see
Theorems 9.58 and 9.67–9.69.

####  9.5 Action pairs and subsemigroups II

We now move on to the second family of action pairs in
$M\wr\mathcal{P}\mathcal{T}_{X}$. Recall that $M\wr\mathcal{P}\mathcal{T}_{X}$
contains natural copies of $M_{0}^{X}$ and $\mathcal{P}\mathcal{T}_{X}$, via
the identifications

${\bf a}\equiv({\bf a},\mathrm{id}_{\operatorname{supp}({\bf
a})})\qquad\text{and}\qquad\alpha\equiv({\bf
1}_{\operatorname{dom}(\alpha)},\alpha)\qquad\text{for ${\bf a}\in M_{0}^{X}$
and $\alpha\in\mathcal{P}\mathcal{T}_{X}$.}$

######  Proposition 9.40.

For any set $X$ and monoid $M$, the following are all action pairs in
$M\wr\mathcal{P}\mathcal{T}_{X}$, with respect to the action (9.2)_:_

  1.   2. (i)

$(M_{0}^{X},\mathcal{P}\mathcal{T}_{X})$,

  3. (ii)

$(M_{0}^{X},\mathcal{I}_{X})$,

  4. (iii)

$(M_{0}^{X},\mathcal{T}_{X})$,

  5. (iv)

$(M_{0}^{X},\mathcal{G}_{X})$,

  6. (v)

$(M^{X},\mathcal{T}_{X})$,

  7. (vi)

$(M^{X},\mathcal{G}_{X})$.

For finite $X$, the following are also action pairs:

  1.   2. (vii)

$(M_{0}^{X},\operatorname{Sing}(\mathcal{P}\mathcal{T}_{X}))$,

  3. (viii)

$(M_{0}^{X},\operatorname{Sing}(\mathcal{I}_{X}))$,

  4. (ix)

$(M_{0}^{X},\operatorname{Sing}(\mathcal{T}_{X}))$,

  5. (x)

$(M^{X},\operatorname{Sing}(\mathcal{T}_{X}))$.

###### Proof.

Given Lemma 4.18, it suffices to show that
$(M_{0}^{X},\mathcal{P}\mathcal{T}_{X})$ is an action pair. For (A1), we have
already noted in (9.15) that $\alpha\cdot{\bf a}={}^{\alpha}{\bf
a}\cdot\alpha$ for all $\alpha\in\mathcal{P}\mathcal{T}_{X}$ and ${\bf a}\in
M_{0}^{X}$. For (A2) we need to show that

${\bf a}\cdot\alpha={\bf b}\cdot\beta\ \Rightarrow\ {\bf
a}\cdot\alpha^{+}={\bf b}\cdot\beta^{+}\qquad\text{for all ${\bf a},{\bf b}\in
M_{0}^{X}$ and $\alpha,\beta\in\mathcal{P}\mathcal{T}_{X}$,}$

where $\alpha^{+}={}^{\alpha}{\bf 1}={\bf
1}_{\operatorname{dom}(\alpha)}\equiv\mathrm{id}_{\operatorname{dom}(\alpha)}$.
By (9.14), we have

$\displaystyle{\bf a}\cdot\alpha$ $\displaystyle=({\bf
a}\mathord{\restriction}_{\operatorname{dom}(\alpha)},\alpha\mathord{\restriction}_{\operatorname{supp}({\bf
a})}),$ $\displaystyle{\bf a}\cdot\alpha^{+}$ $\displaystyle=({\bf
a}\mathord{\restriction}_{\operatorname{dom}(\alpha^{+})},\alpha^{+}\mathord{\restriction}_{\operatorname{supp}({\bf
a})}),$ $\displaystyle{\bf b}\cdot\beta$ $\displaystyle=({\bf
b}\mathord{\restriction}_{\operatorname{dom}(\beta)},\beta\mathord{\restriction}_{\operatorname{supp}({\bf
b})}),$ $\displaystyle{\bf b}\cdot\beta^{+}$ $\displaystyle=({\bf
b}\mathord{\restriction}_{\operatorname{dom}(\beta^{+})},\beta^{+}\mathord{\restriction}_{\operatorname{supp}({\bf
b})}).$

So the required implication quickly follows from:

  * •

the identities $\operatorname{dom}(\alpha^{+})=\operatorname{dom}(\alpha)$ and
$\operatorname{dom}(\alpha^{+}\mathord{\restriction}_{\operatorname{supp}({\bf
a})})=\operatorname{dom}(\alpha\mathord{\restriction}_{\operatorname{supp}({\bf
a})})$,

  * •

the analogous identities for ${\bf b}$ and $\beta$, and

  * •

the fact that $\mathrm{id}_{C}=\mathrm{id}_{D}\ \Leftrightarrow\ C=D$ for
$C,D\subseteq X$, noting that
$\alpha^{+}\mathord{\restriction}_{\operatorname{supp}({\bf a})}$ and
$\beta^{+}\mathord{\restriction}_{\operatorname{supp}({\bf b})}$ are both
partial identities. ∎

######  Remark 9.41.

Pairs (v), (vi) and (x) from Proposition 9.40 have the form $(M^{X},S)$. Any
such pair $(M^{X},S)$ necessarily satisfies $S\subseteq\mathcal{T}_{X}$, since
$M^{X}$ is not closed under the action of elements from
${\mathcal{P}\mathcal{T}_{X}\setminus\mathcal{T}_{X}}$. Any such pair also has
the _right-_ uniqueness property. Indeed, it quickly follows from (9.14) that

${\bf a}\cdot\alpha={\bf b}\cdot\beta\ \Rightarrow\
\alpha=\beta\qquad\text{for all ${\bf a},{\bf b}\in M^{X}$ and
$\alpha,\beta\in\mathcal{P}\mathcal{T}_{X}$.}$

But this is to be expected, since for $S\leq\mathcal{T}_{X}$ we have $M\wr
S=M^{X}\rtimes S$; cf. Remark 9.8.

We now identify the strong and proper pairs from Proposition 9.40.

######  Proposition 9.42.

Of the action pairs listed in Proposition 9.40, and apart from trivially small
exceptions:

  1. (i)

the strong pairs are precisely (iii)–(vi), (ix) and (x),

  2. (ii)

the proper pairs are precisely (v), (vi) and (x).

###### Proof.

(i). The stated pairs are precisely those of the form $(U,S)$ with
$S\subseteq\mathcal{T}_{X}$, so this part follows immediately from Lemma
4.15(ii) and (9.4).

(ii). The stated pairs are precisely those of the form $(M^{X},S)$ with
$S\subseteq\mathcal{T}_{X}$. For each of these, we have
$P(U,S)=\\{\mathrm{id}_{X}\equiv{\bf 1}\\}$, so that $\sigma=\Delta_{S}$ is
the trivial relation. The required equivalence (5.26) then becomes

${\bf a}\cdot\alpha={\bf b}\cdot\beta\qquad\Leftrightarrow\qquad{\bf a}={\bf
b}\quad\text{and}\quad\alpha=\beta\qquad\qquad\text{for all ${\bf a},{\bf
b}\in M^{X}$ and $\alpha,\beta\in S$,}$

and this again follows immediately from (9.14).

The pairs not listed are all of the form $(M_{0}^{X},S)$ with
$S\leq\mathcal{P}\mathcal{T}_{X}$. To show that these are not proper we
consider separate cases according to whether or not
$S\subseteq\mathcal{T}_{X}$. We must show that the following fails for some
${\bf a},{\bf b}\in M_{0}^{X}$ and $\alpha,\beta\in S$:

${\bf a}\cdot\alpha={\bf b}\cdot\beta\qquad\Leftrightarrow\qquad{\bf
a}\cdot\alpha^{+}={\bf
b}\cdot\beta^{+}\quad\text{and}\quad\alpha\mathrel{\sigma}\beta.$ (9.43)

Case 1. If $S\subseteq\mathcal{T}_{X}$, then as above we have
$\sigma=\Delta_{S}$, and $\alpha^{+}={\bf 1}$ for all $\alpha\in S$. In this
case, the forwards implication in (9.43) fails for ${\bf a}={\bf b}={\bf 0}$
and distinct $\alpha,\beta\in S$, where ${\bf 0}=(0)_{x\in X}\in M_{0}^{X}$ is
the all-zero $X$-tuple.

Case 2. Now suppose $S\not\subseteq\mathcal{T}_{X}$. By the form of the pairs
in question, we have $\varnothing=\mathrm{id}_{\varnothing}\in S$, and so
${\bf 0}=\varnothing^{+}\in P$, so that $\sigma=\nabla_{S}$ is the universal
relation in this case. Here the backwards implication in (9.43) fails for
${\bf a}={\bf b}={\bf 1}$ and any $\alpha,\beta\in S$ with
$\operatorname{dom}(\alpha)=\operatorname{dom}(\beta)$ but $\alpha\not=\beta$.
∎

######  Remark 9.44.

As suggested by Case 1 in the above proof, one can make a general statement
about proper action pairs in a certain special case concerning zero elements.
Indeed, suppose $(U,S)$ is a proper action pair in a monoid $M$ with zero $0$,
and suppose additionally that $0\in U$. Since $0\cdot s=0\cdot t$ (and $0\cdot
s^{+}=0\cdot t^{+}$) for all $s,t\in S$, it follows from (5.26) that
$s\mathrel{\sigma}t$ for all $s,t\in S$, meaning that $\sigma=\nabla_{S}$ for
such pairs.

On the other hand, if $(U,S)$ is a weak action pair with $\sigma=\nabla_{S}$,
then it follows from Definition 5.25 that $(U,S)$ is proper precisely when

$us=vt\ \Leftrightarrow\ us^{+}=vt^{+}\qquad\text{for all $u,v\in U^{1}$ and
$s,t\in S$.}$

This is of course an if-and-only-if version of the defining property (A2) from
Definition 4.2.

It is a routine matter to determine the subsemigroups $US$ of
$M\wr\mathcal{P}\mathcal{T}_{X}$ corresponding to the action pairs $(U,S)$ in
Proposition 9.40. In the next statement, we again do not assume $X$ is finite
in the parts involving singular subsets/subsemigroups, and we again refer to
the subsemigroup $\mathcal{F}_{X}\leq\mathcal{I}_{X}$ from Remark 8.63; recall
that $\mathcal{F}_{X}=\mathcal{I}_{X}$ when $X$ is finite.

######  Proposition 9.45.

For any set $X$ and monoid $M$, we have:

  1.   2. (i)

$M_{0}^{X}\cdot\mathcal{P}\mathcal{T}_{X}=M\wr\mathcal{P}\mathcal{T}_{X}$,

  3. (ii)

$M_{0}^{X}\cdot\mathcal{I}_{X}=M\wr\mathcal{I}_{X}$,

  4. (iii)

$M_{0}^{X}\cdot\mathcal{T}_{X}=M\wr\mathcal{P}\mathcal{T}_{X}$,

  5. (iv)

$M_{0}^{X}\cdot\mathcal{G}_{X}=M\wr\mathcal{F}_{X}$,

  6. (v)

$M^{X}\cdot\mathcal{T}_{X}=M\wr\mathcal{T}_{X}$,

  7. (vi)

$M^{X}\cdot\mathcal{G}_{X}=M\wr\mathcal{G}_{X}$,

  8. (vii)

$M_{0}^{X}\cdot\operatorname{Sing}(\mathcal{P}\mathcal{T}_{X})=M\wr\operatorname{Sing}(\mathcal{P}\mathcal{T}_{X})$,

  9. (viii)

$M_{0}^{X}\cdot\operatorname{Sing}(\mathcal{I}_{X})=M\wr\operatorname{Sing}(\mathcal{I}_{X})$,

  10. (ix)

$M_{0}^{X}\cdot\operatorname{Sing}(\mathcal{T}_{X})=M\wr\operatorname{Sing}(\mathcal{P}\mathcal{T}_{X})$,

  11. (x)

$M^{X}\cdot\operatorname{Sing}(\mathcal{T}_{X})=M\wr\operatorname{Sing}(\mathcal{T}_{X})$.
∎

####  9.6 Congruence conditions II

We now examine the congruence conditions for the pairs from Proposition 9.40.
Each such pair is of the form $(U,S)$, where
$S\leq\mathcal{P}\mathcal{T}_{X}$, and $U$ is either $M_{0}^{X}$ or $M^{X}$,
the latter only when $S\subseteq\mathcal{T}_{X}$. Since $U$ is a monoid in
each case, all such pairs satisfy all the conditions of Lemma 4.61, and hence
Lemma 4.65 applies to each pair, which then feeds into Proposition 6.1.

The stronger congruence conditions involve the behaviour of the right
congruences and sub(semi)groups

$\theta_{\bf a}=\big{\\{}{(\alpha,\beta)\in S\times S}:{{\bf
a}\cdot\alpha={\bf a}\cdot\beta}\big{\\}}\quad\text{and}\quad S_{\bf
a}=\\{{\alpha\in S}:{{\bf a}\cdot\alpha={\bf a}}\\}\qquad\text{for ${\bf a}\in
M_{0}^{X}$,}$ (9.46)

or the related right congruences $\Theta_{\bf a}$ on $S^{1}$, as appropriate.
Such conditions then feed into one of Theorems 6.4, 6.12, 6.27, 6.35 or 6.43,
as applicable to the pair $(U,S)$. Theorem 6.12 applies when $U$ and $S$ are
both submonoids, which obviously excludes the pairs with
$S\subseteq\operatorname{Sing}(\mathcal{P}\mathcal{T}_{X})$. Theorem 6.43 (and
indeed even Theorem 6.35) is not generally applicable to _any_ of the pairs,
as $M_{0}^{X}\setminus\\{{\bf 1}\\}$ and $M^{X}\setminus\\{{\bf 1}\\}$ are
typically not subsemigroups. Thus, for the remainder of the current section,
we will only be concerned with the first six pairs from Proposition 9.40. By
Proposition 9.45, the four excluded pairs produce the following three product
semigroups:

$M\wr\operatorname{Sing}(\mathcal{T}_{X}),\qquad
M\wr\operatorname{Sing}(\mathcal{P}\mathcal{T}_{X})\qquad\text{and}\qquad
M\wr\operatorname{Sing}(\mathcal{I}_{X}).$

Presentations for the first two (for finite $X$) are stated above in Theorems
9.32 and 9.33. For the third (again for finite $X$), see [15].

We have so far restricted our attention to the first six pairs $(U,S)$ from
Proposition 9.40. In fact, since we are primarily concerned with finding
presentations for the corresponding subsemigroup $US$ (for finite $X$), and
since the same subsemigroup can arise from different pairs, as seen in
Proposition 9.45 (and recalling that $\mathcal{F}_{X}=\mathcal{I}_{X}$ when
$X$ is finite), we can further restrict our attention to the following four
pairs:

  1.   2. (a)

$(M_{0}^{X},\mathcal{T}_{X})$,

  3. (b)

$(M_{0}^{X},\mathcal{G}_{X})$,

  4. (c)

$(M^{X},\mathcal{T}_{X})$,

  5. (d)

$(M^{X},\mathcal{G}_{X})$.

As in Proposition 9.45, these give rise to the following subsemigroups
(respectively), where we additionally assume $X$ is finite in (b):

  1.   2. (a)

$M\wr\mathcal{P}\mathcal{T}_{X}$,

  3. (b)

$M\wr\mathcal{I}_{X}$,

  4. (c)

$M\wr\mathcal{T}_{X}$,

  5. (d)

$M\wr\mathcal{G}_{X}$.

Since the pairs (c) and (d) have the right-uniqueness property (cf. Remark
9.41), the congruence $\theta$ is trivial, as are the right congruences
$\theta_{\bf a}$ and sub(semi)groups $S_{\bf a}$. So in fact, we need only
focus on pairs (a) and (b) in the current section, though some of the results
we prove are more general.

######  Lemma 9.47.

Let ${\bf a}\in M_{0}^{X}$, and write $B=\operatorname{supp}({\bf a})$. Then
for any subsemigroup $S\leq\mathcal{P}\mathcal{T}_{X}$ we have

$\theta_{\bf a}=\theta_{{\bf 1}_{B}}=\big{\\{}{(\alpha,\beta)\in S\times
S}:{\alpha\mathord{\restriction}_{B}=\beta\mathord{\restriction}_{B}}\big{\\}}.$

###### Proof.

Since $\alpha\mathord{\restriction}_{B}={\bf 1}_{B}\cdot\alpha$ for all
$\alpha\in\mathcal{P}\mathcal{T}_{X}$, we have $\theta_{{\bf
1}_{B}}=\big{\\{}{(\alpha,\beta)\in S\times
S}:{\alpha\mathord{\restriction}_{B}=\beta\mathord{\restriction}_{B}}\big{\\}}$
by definition.

Next, let $\alpha,\beta\in S$. Then since ${\bf a}={\bf a}\cdot{\bf 1}_{B}$,
we have

$(\alpha,\beta)\in\theta_{{\bf 1}_{B}}\ \Rightarrow\ {\bf
1}_{B}\cdot\alpha={\bf 1}_{B}\cdot\beta\ \Rightarrow\ {\bf a}\cdot\alpha={\bf
a}\cdot{\bf 1}_{B}\cdot\alpha={\bf a}\cdot{\bf 1}_{B}\cdot\beta={\bf
a}\cdot\beta\ \Rightarrow\ (\alpha,\beta)\in\theta_{\bf a}.$

The converse follows quickly from (9.14) and the definition of $\theta_{\bf
a}$. ∎

######  Lemma 9.48.

If $S=\mathcal{T}_{X}$ or $\mathcal{P}\mathcal{T}_{X}$, then

$\theta_{{\bf a}{\bf b}}=\theta_{\bf a}\vee\theta_{\bf b}\qquad\text{for all
${\bf a},{\bf b}\in M_{0}^{X}$.}$

###### Proof.

Throughout the proof we write $B=\operatorname{supp}({\bf a})$ and
$C=\operatorname{supp}({\bf b})$, so $\operatorname{supp}({\bf a}{\bf
b})=B\cap C$. By Lemma 9.47, we need to show that

$\theta_{{\bf 1}_{B\cap C}}=\theta_{{\bf 1}_{B}}\vee\theta_{{\bf 1}_{C}}.$

Since ${\bf 1}_{B}$ and ${\bf 1}_{C}$ commute (and ${\bf 1}_{B}{\bf
1}_{C}={\bf 1}_{B\cap C}$), it follows from (4.70) that we only need to show
the forwards inclusion. To do so, suppose $(\alpha,\beta)\in\theta_{{\bf
1}_{B\cap C}}$, so that $\alpha\mathord{\restriction}_{B\cap
C}=\beta\mathord{\restriction}_{B\cap C}$. We then let
$\gamma\in\mathcal{P}\mathcal{T}_{X}$ be such that
$\gamma\mathord{\restriction}_{B}=\alpha\mathord{\restriction}_{B}$ and
$\gamma\mathord{\restriction}_{C}=\beta\mathord{\restriction}_{C}$; in the
case $S=\mathcal{T}_{X}$ we also define $x\gamma=x$ for all $x\in
X\setminus(B\cup C)$. We then have $\gamma\in S$, and
$\alpha\mathrel{\theta}_{B}\gamma\mathrel{\theta}_{C}\beta$. ∎

######  Remark 9.49.

The previous result excluded the cases $S=\mathcal{I}_{X}$ and
$S=\mathcal{G}_{X}$ since injectivity of $\alpha$ and $\beta$ does not imply
that the $\gamma$ constructed in the proof is injective.

Lemma 9.48 concerns the congruence condition from Lemma 4.71(ii). However,
that result can only be applied if $U$ is commutative, and since $U=M_{0}^{X}$
or $M^{X}$, this is only the case if $M$ is commutative, and we do not need or
want to assume this is the case. It turns out that while part (ii) of Lemma
4.71 does not apply in general, part (i) always does. While this might seem
less desirable, it is in fact an improvement in this case, since we can choose
the relevant subset $V\subseteq U$ to be rather a lot smaller than a
generating set for $U$, at least when $X$ is finite, as we now explain.

For $x\in X$, we write ${\bf v}_{x}={\bf 1}_{X\setminus
x}\equiv\mathrm{id}_{X\setminus x}$, and we write

$V=\\{{{\bf v}_{x}}:{x\in X}\\}.$

When $X$ is finite we have

$\langle V\rangle=\\{{{\bf 1}_{B}}:{B\subseteq
X}\\}\equiv\\{{\mathrm{id}_{B}}:{B\subseteq X}\\}=\mathcal{E}_{X}.$

Again writing $\preceq$ for the relation in (4.67), note that

${\bf v}_{x}\preceq{\bf a}\ \Leftrightarrow\ x\not\in\operatorname{supp}({\bf
a})\qquad\text{for all ${\bf a}\in M_{0}^{X}$ and $x\in X$.}$

The following therefore verifies the conditions of Lemma 4.71(i) with respect
to this $V$.

######  Lemma 9.50.

If $S=\mathcal{P}\mathcal{T}_{X}$ or $\mathcal{T}_{X}$ for $|X|<\aleph_{0}$,
and if ${\bf a}\in M_{0}^{X}$, then

$\theta_{\bf a}=\bigvee_{x\in X\setminus B}\theta_{{\bf
v}_{x}}\qquad\text{where}\qquad B=\operatorname{supp}({\bf a}).$

###### Proof.

By Lemma 9.47 we have $\theta_{\bf a}=\theta_{{\bf 1}_{B}}$. Since ${\bf
1}_{B}=\prod_{x\in X\setminus B}{\bf v}_{x}$, it follows from Lemma 9.48 that
$\theta_{{\bf 1}_{B}}=\bigvee_{x\in X\setminus B}\theta_{{\bf v}_{x}}$. ∎

The proof of the next result is similar to (but easier than) that of Lemma
9.24. For this result we do not need to assume that $X$ is finite.

######  Lemma 9.51.

If $S=\mathcal{T}_{X}$, and if $y\in X$, then $\theta_{{\bf v}_{y}}$ is
generated as a right congruence by any pair
$(\varepsilon_{xy},\mathrm{id}_{X})$ with $x\in X\setminus y$. ∎

We now have all the information we need for the pair
$(M_{0}^{X},\mathcal{T}_{X})$, so we now turn our attention to
$(M_{0}^{X},\mathcal{G}_{X})$ for finite $X$. For ${\bf a}\in M_{0}^{X}$ and
$\alpha\in\mathcal{G}_{X}$, we have $\alpha\in S_{\bf a}\ \Leftrightarrow\
(\alpha,\mathrm{id}_{X})\in\theta_{\bf a}$, so by Lemma 9.47 we have

$S_{\bf
a}=\\{{\alpha\in\mathcal{G}_{X}}:{\alpha\mathord{\restriction}_{B}=\mathrm{id}_{B}}\\}\qquad\text{where}\qquad
B=\operatorname{supp}({\bf a}).$

The next result immediately follows, where again $\tau_{xy}$ denotes the
transposition $(x,y)$.

######  Lemma 9.52.

If $S=\mathcal{G}_{X}$ for $|X|<\aleph_{0}$, and if ${\bf a}\in M_{0}^{X}$,
then $S_{\bf a}$ is generated by the set $\\{{\tau_{xy}}:{x,y\in X\setminus
B,\ x\not=y}\\}$. ∎

As in the proof of Lemma 9.29, it is then easy to show that

$S_{{\bf a}{\bf b}}=S_{\bf a}\vee S_{\bf b}\qquad\text{for any ${\bf a},{\bf
b}\in M_{0}^{X}$ with $(X\setminus\operatorname{supp}({\bf
a}))\cap(X\setminus\operatorname{supp}({\bf b}))\not=\varnothing$.}$ (9.53)

For distinct $x,y\in X$, we write ${\bf v}_{xy}={\bf v}_{x}{\bf v}_{y}={\bf
1}_{X\setminus\\{x,y\\}}\equiv\mathrm{id}_{X\setminus\\{x,y\\}}$. The next
result shows that Lemma 4.74(i) applies to the pair
$(M_{0}^{X},\mathcal{G}_{X})$, with respect to the set

$V=\\{{{\bf v}_{xy}}:{x,y\in X,\ x\not=y}\\}.$

######  Lemma 9.54.

If $S=\mathcal{G}_{X}$ for $|X|<\aleph_{0}$, and if ${\bf a}\in M_{0}^{X}$,
then

$S_{\bf a}=\bigvee_{x,y\in X\setminus B\atop x\not=y}S_{{\bf
v}_{xy}}\qquad\text{where}\qquad B=\operatorname{supp}({\bf a}).$

###### Proof.

If $|X\setminus B|\leq 1$, then $S_{\bf a}=\\{\mathrm{id}_{X}\\}$, and the
stated join is empty. If $|X\setminus B|\geq 2$, then we argue as in the proof
of Lemma 9.30, applying (9.53) in place of Lemma 9.29. ∎

####  9.7 Presentations II

We now assume that $X={\bf n}=\\{1,\ldots,n\\}$ for some integer $n\geq 2$,
with the goal of giving presentations for the wreath products

$M\wr\mathcal{P}\mathcal{T}_{n}=M_{0}^{n}\cdot\mathcal{T}_{n},\qquad
M\wr\mathcal{I}_{n}=M_{0}^{n}\cdot\mathcal{G}_{n},\qquad
M\wr\mathcal{T}_{n}=M^{n}\cdot\mathcal{T}_{n}\qquad\text{and}\qquad
M\wr\mathcal{G}_{n}=M^{n}\cdot\mathcal{G}_{n}.$

The wreath products $M\wr\operatorname{Sing}(\mathcal{T}_{n})$ and
$M\wr\operatorname{Sing}(\mathcal{I}_{n})$ were treated in [41, 15], and
$M\wr\operatorname{Sing}(\mathcal{P}\mathcal{T}_{n})$ in Theorem 9.33. For the
remaining wreath products listed above, we need presentations for $M^{n}$,
$M_{0}^{n}$, $\mathcal{G}_{n}$ and $\mathcal{T}_{n}$. For $\mathcal{G}_{n}$ we
have the following classical result, in which we continue to use the notation
$\tau_{xy}$ for the transposition $(x,y)\in\mathcal{G}_{n}$:

######  Theorem 9.55 (Moore [92]).

For $n\geq 2$, the symmetric group $\mathcal{G}_{n}$ has presentation
${\textup{{Mon}}\langle{X_{G}}:{R_{G}}\rangle}$ via
$\phi_{G}:X_{G}^{*}\to\mathcal{G}_{n}$, where

  * •

$X_{G}=\\{s_{1},\ldots,s_{n-1}\\}$,

  * •

$s_{i}\phi_{G}=\tau_{i,i+1}$ for all $i$, and

  * •

$R_{G}$ consists of the following relations:

$s_{i}^{2}=\iota\text{ for all $i$},\qquad s_{i}s_{j}=s_{j}s_{i}\text{ if
$|i-j|>1$},\qquad s_{i}s_{j}s_{i}=s_{j}s_{i}s_{j}\text{ if $|i-j|=1$.}$

The first presentation for $\mathcal{T}_{n}$ was given by Aĭzenštat [1], but
it is convenient here to use the following formulation from [36]; see also
[73]. The statement (and following ones) uses the maps $\varepsilon_{ij}$ from
(9.23).

######  Theorem 9.55 (Aĭzenštat [1]).

For $n\geq 2$, the full transformation semigroup $\mathcal{T}_{n}$ has
presentation ${\textup{{Mon}}\langle{X_{T}}:{R_{T}}\rangle}$ via
$\phi_{T}:X_{T}^{*}\to\mathcal{T}_{n}$, where

  * •

$X_{T}=\\{s_{1},\ldots,s_{n-1}\\}\cup\\{\lambda_{1},\ldots,\lambda_{n-1}\\}\cup\\{\rho_{1},\ldots,\rho_{n-1}\\}$,

  * •

$s_{i}\phi_{T}=\tau_{i,i+1}$, $\lambda_{i}\phi_{T}=\varepsilon_{i,i+1}$ and
$\rho_{i}\phi_{T}=\varepsilon_{i+1,i}$ for all $i$,

  * •

$R_{T}$ consists of the following relations:

$\displaystyle
s_{i}^{2}=\iota_{n},\qquad\lambda_{i}=\lambda_{i}^{2}=\rho_{i}\lambda_{i}=s_{i}\lambda_{i}=\rho_{i}s_{i},\qquad\rho_{i}=\rho_{i}^{2}=\lambda_{i}\rho_{i}=s_{i}\rho_{i}=\lambda_{i}s_{i},$
$\displaystyle\lambda_{i}\lambda_{i+1}=\lambda_{i}s_{i+1},\qquad\rho_{i+1}\rho_{i}=\rho_{i+1}s_{i},\qquad\lambda_{i}\rho_{i+1}=\lambda_{i},\qquad\rho_{i+1}\lambda_{i}=\rho_{i+1},$
$\displaystyle\lambda_{i+1}\lambda_{i}=\lambda_{i}\lambda_{i+1}\lambda_{i}=\lambda_{i+1}\lambda_{i}\lambda_{i+1},\qquad\rho_{i}\rho_{i+1}=\rho_{i}\rho_{i+1}\rho_{i}=\rho_{i+1}\rho_{i}\rho_{i+1},$
$\displaystyle\lambda_{i+1}s_{i}=s_{i}s_{i+1}\lambda_{i}\lambda_{i+1},\qquad\rho_{i}s_{i+1}=s_{i+1}s_{i}\rho_{i+1}\rho_{i},$
$\displaystyle
s_{i}s_{j}=s_{j}s_{i},\qquad\lambda_{i}\lambda_{j}=\lambda_{j}\lambda_{i},\qquad\rho_{i}\rho_{j}=\rho_{j}\rho_{i},$
if $|i-j|>1$, $\displaystyle s_{i}\lambda_{j}=\lambda_{j}s_{i},\qquad
s_{i}\rho_{j}=\rho_{j}s_{i},$ if $|i-j|>1$, $\displaystyle
s_{i}s_{j}s_{i}=s_{j}s_{i}s_{j},$ if $|i-j|=1$,
$\displaystyle\lambda_{i}\rho_{j}=\rho_{j}\lambda_{i},$ if $j\not=i,i+1$. ∎

The generators for $\mathcal{G}_{n}$ and $\mathcal{T}_{n}$ from Theorems 9.55
and 9.55 are pictured in Figure 8.

$1$$i$$n$$1$$i$$n$$1$$i$$n$

Figure 8: The generators $\lambda_{i}\phi_{T}$ (left),
$s_{i}\phi_{G}=s_{i}\phi_{T}$ (middle) and $\rho_{i}\phi_{T}$ (right), for
$1\leq i\leq n-1$.

Presentations for $M^{n}$ and $M_{0}^{n}$ are easy to obtain (either directly,
or by iterating Theorem 6.4 in the special case of direct products), so we fix
notation for these as follows. For $a\in M$ and $i\in{\bf n}$, we denote by
$a^{(i)}\in M^{n}$ the $n$-tuple over $M$ whose $i$th entry is $a$, and all
other entries are $1$. (This tuple was denoted ${\bf t}_{i;a}$ in Section 9.3,
but the $a^{(i)}$ notation is more convenient for our present purposes.) If
${\bf a}=(a_{1},\ldots,a_{n})\in M^{n}$, then ${\bf a}=a_{1}^{(1)}\cdots
a_{n}^{(n)}$.

We assume the monoid $M$ has presentation

$\textup{{Mon}}\langle{X_{M}}:{R_{M}}\rangle\qquad\text{via}\qquad\phi_{M}:X_{M}^{*}\to
M.$

For $w\in X_{M}^{*}$, we write $\overline{w}=w\phi_{M}$. For each $i\in{\bf
n}$, we define an alphabet $X_{M}^{(i)}=\\{{x^{(i)}}:{x\in X_{M}}\\}$ in one-
one correspondence with $X_{M}$. For a word $w=x_{1}\cdots x_{k}\in
X_{M}^{*}$, we write $w^{(i)}=x_{1}^{(i)}\cdots x_{k}^{(i)}$, and we also
define ${R_{M}^{(i)}=\big{\\{}{(w^{(i)},v^{(i)})}:{(w,v)\in R_{M}}\big{\\}}}$.
We then define the alphabet

$X_{M^{n}}=X_{M}^{(1)}\cup\cdots\cup X_{M}^{(n)},$

and the set of relations

$R_{M^{n}}=R_{M}^{(1)}\cup\cdots\cup
R_{M}^{(n)}\cup\big{\\{}{(x^{(i)}y^{(j)},y^{(j)}x^{(i)}}:{x,y\in X_{M},\
i,j\in{\bf n},\ i\not=j}\big{\\}}.$

######  Theorem 9.56.

With the above notation, $M^{n}$ has presentation
$\textup{{Mon}}\langle{X_{M^{n}}}:{R_{M^{n}}}\rangle$ via

$\phi_{M^{n}}:X_{M^{n}}^{*}\to M^{n}:x^{(i)}\mapsto\overline{x}^{(i)}.$

A presentation for $M_{0}^{n}$ can be derived as a special case of Theorem
9.56, beginning instead with a presentation for $M_{0}$. However, it is
convenient to give a more explicit formulation, making use of the fact that
$M$ is a subsemigroup of $M_{0}$ by definition. For this, we additionally use
the notation of Theorem 9.31, in particular the alphabet $X_{E}$ and the
relations $R_{E}$. We define the alphabet

$X_{M_{0}^{n}}=X_{M^{n}}\cup X_{E},$

and set of relations

$\displaystyle R_{M_{0}^{n}}=R_{M^{n}}\cup R_{E}$
$\displaystyle\cup\big{\\{}{(t_{i}x^{(j)},x^{(j)}t_{i})}:{x\in X_{M},\
i,j\in{\bf n},\ i\not=j}\big{\\}}$
$\displaystyle\cup\big{\\{}{(t_{i}x^{(i)},t_{i}),(x^{(i)}t_{i},t_{i})}:{x\in
X_{M},\ i\in{\bf n}}\big{\\}}.$

######  Theorem 9.57.

With the above notation, $M_{0}^{n}$ has presentation
$\textup{{Mon}}\langle{X_{M_{0}^{n}}}:{R_{M_{0}^{n}}}\rangle$ via

$\phi_{M_{0}^{n}}:X_{M_{0}^{n}}^{*}\to
M_{0}^{n}:x^{(i)}\mapsto\overline{x}^{(i)},\ t_{i}\mapsto{\bf 1}_{{\bf
n}\setminus i}.$

The generators for $M^{n}$ and $M_{0}^{n}$ from Theorems 9.56 and 9.57 are
pictured in Figure 9, each identified with a pair from
$M\wr\mathcal{P}\mathcal{T}_{n}$ in the usual way.

$\overline{x}$$1$$i$$n$$1$$i$$n$

Figure 9: The generators $\overline{x}^{(i)}$ (left) and ${\bf 1}_{{\bf
n}\setminus i}\equiv\mathrm{id}_{{\bf n}\setminus i}$ (right).

We can now give the main results of this section, which are presentations for
the wreath products $M\wr S$, where $S$ is one of $\mathcal{G}_{n}$,
$\mathcal{T}_{n}$, $\mathcal{I}_{n}$ or $\mathcal{P}\mathcal{T}_{n}$. It is
convenient to begin with the largest of these,
$M\wr\mathcal{P}\mathcal{T}_{n}$.

######  Theorem 9.58.

For $n\geq 2$, the wreath product $M\wr\mathcal{P}\mathcal{T}_{n}$ has
presentation

$\textup{{Mon}}\langle{X_{M_{0}^{n}}\cup X_{T}}:{R_{M_{0}^{n}}\cup R_{T}\cup
R}\rangle$

via

$\Psi:(X_{M_{0}^{n}}\cup X_{T})^{*}\to
M\wr\mathcal{P}\mathcal{T}_{n}:\begin{cases}x^{(i)}\mapsto\overline{x}^{(i)},\\\
t_{i}\mapsto\mathrm{id}_{{\bf n}\setminus i},\\\ s_{i}\mapsto\tau_{i,i+1},\\\
\lambda_{i}\mapsto\varepsilon_{i,i+1},\\\
\rho_{i}\mapsto\varepsilon_{i+1,i},\end{cases}$

where $R$ consists of the following relations, with $x\in X_{M}$, $1\leq i\leq
n-1$ and $1\leq k\leq n$ in each:

$\displaystyle s_{i}x^{(k)}$
$\displaystyle=\begin{cases}\mathrlap{x^{(i+1)}s_{i}}\hphantom{XXXXXX}&\text{if
$k=i$,}\\\ x^{(i)}s_{i}&\text{if $k=i+1$,}\\\
x^{(k)}s_{i}&\text{otherwise,}\end{cases}$ (9.59)
$\displaystyle\lambda_{i}x^{(k)}$
$\displaystyle=\begin{cases}\mathrlap{x^{(i)}x^{(i+1)}\lambda_{i}}\hphantom{XXXXXX}&\text{if
$k=i$,}\\\ \lambda_{i}&\text{if $k=i+1$,}\\\
x^{(k)}\lambda_{i}&\text{otherwise,}\end{cases}$ (9.60)
$\displaystyle\rho_{i}x^{(k)}$
$\displaystyle=\begin{cases}\mathrlap{\rho_{i}}\hphantom{XXXXXX}&\text{if
$k=i$,}\\\ x^{(i)}x^{(i+1)}\rho_{i}&\text{if $k=i+1$,}\\\
x^{(k)}\rho_{i}&\text{otherwise,}\end{cases}$ (9.61) $\displaystyle
s_{i}t_{k}$
$\displaystyle=\begin{cases}\mathrlap{t_{i+1}s_{i}}\hphantom{XXXXXX}&\text{if
$k=i$,}\\\ t_{i}s_{i}&\text{if $k=i+1$,}\\\
t_{k}s_{i}&\text{otherwise,}\end{cases}$ (9.62)
$\displaystyle\lambda_{i}t_{k}$
$\displaystyle=\begin{cases}\mathrlap{t_{i}t_{i+1}\lambda_{i}}\hphantom{XXXXXX}&\text{if
$k=i$,}\\\ \lambda_{i}&\text{if $k=i+1$,}\\\
t_{k}\lambda_{i}&\text{otherwise,}\end{cases}$ (9.63)
$\displaystyle\rho_{i}t_{k}$
$\displaystyle=\begin{cases}\mathrlap{\rho_{i}}\hphantom{XXXXXX}&\text{if
$k=i$,}\\\ t_{i}t_{i+1}\rho_{i}&\text{if $k=i+1$,}\\\
t_{k}\rho_{i}&\text{otherwise,}\end{cases}$ (9.64) $\displaystyle
t_{i}\rho_{i}$ $\displaystyle=t_{i}.$ (9.65)

###### Proof.

By Proposition 9.40 $(M_{0}^{n},\mathcal{T}_{n})$ is a strong action pair, and
by Proposition 9.45 we have
$M\wr\mathcal{P}\mathcal{T}_{n}=M_{0}^{n}\cdot\mathcal{T}_{n}$. Theorem 6.4
therefore applies, and tells us that $M\wr\mathcal{P}\mathcal{T}_{n}$ has
presentation

$\textup{{Mon}}\langle{X_{M_{0}^{n}}\cup X_{T}}:{R_{M_{0}^{n}}\cup R_{T}\cup
R_{1}\cup R_{\Omega}}\rangle$

via $\Psi$, where:

  * •

$R_{1}=\big{\\{}{(xy,{}^{x}y\cdot x)}:{x\in X_{T},\ y\in
X_{M_{0}^{n}}}\big{\\}}$, and

  * •

$R_{\Omega}=\big{\\{}{(N({\bf a}),N({\bf b}))}:{({\bf a},{\bf
b})\in\Omega}\big{\\}}$ for any generating set $\Omega$ for the congruence
$\theta$ on $M_{0}^{n}\rtimes\mathcal{T}_{n}$.

In $R_{1}$, ${}^{x}y$ is a word over $X_{M_{0}^{n}}$ mapping to
${}^{\overline{x}}\overline{y}$. So we must find a suitable set of such words
${}^{x}y$, for each combination of $x=s_{i}$, $\lambda_{i}$ or $\rho_{i}$, and
$y=x^{(k)}$ or $t_{k}$. This has been carried out, and the resulting relations
are precisely (9.59)–(9.64), as can be easily checked. We give a sample
calculation in Figure 10 for the $k=i,i+1$ cases of (9.60).

For the relations $R_{\Omega}$, we begin by defining the tuples ${\bf
v}_{i}={\bf 1}_{{\bf n}\setminus i}\equiv\mathrm{id}_{{\bf n}\setminus
i}=t_{i}\Psi$ for each $i\in{\bf n}$. By Lemmas 9.50 and 4.71(i), we have
$\theta=\Omega^{\sharp}$ for

$\Omega=\big{\\{}{(({\bf v}_{i},\alpha),({\bf v}_{i},\beta))}:{i\in{\bf n},\
(\alpha,\beta)\in\Omega_{{\bf v}_{i}}}\big{\\}},$

where each $\Omega_{{\bf v}_{i}}$ generates $\theta_{{\bf v}_{i}}$ as a right
congruence. By Lemma 9.51 we can take $\Omega_{{\bf v}_{i}}$ to be the set
consisting of the single pair $(\mathrm{id}_{\bf n},\varepsilon_{i+1,i})$.
That is, we can take

$\Omega=\big{\\{}{(({\bf v}_{i},\varepsilon_{i+1,i}),({\bf
v}_{i},\mathrm{id}_{\bf n}))}:{i\in{\bf n}}\big{\\}}.$

The resulting set $R_{\Omega}$ therefore consists precisely of the relations
(9.65). ∎

$1$$i$$n$$\overline{x}$$=$$\overline{x}$$\overline{x}$$1$$i$$n$$1$$i$$n$$\overline{x}$$=$$1$$i$$n$

Figure 10: The $k=i$ (left) and $k=i+1$ (right) cases of relation (9.60).

######  Remark 9.66.

The relations in Theorem 9.58 contain a fair few redundancies. For example,
the following relations could all be deleted:

  1. (i)

the $k=i+1$ (or $k=i$) cases of (9.59) and (9.62),

  2. (ii)

all of (9.60) and (9.63), or alternatively all of (9.61) and (9.64).

Indeed, for (i), we use $R_{G}$ and the $k=i$ case of (9.62) to transform
$s_{i}t_{i+1}$ into $t_{i}s_{i+1}$ as follows:

$s_{i}t_{i+1}\to s_{i}t_{i+1}s_{i}s_{i}\to s_{i}s_{i}t_{i}s_{i}\to
t_{i}s_{i}.$

(A similar calculation works for $s_{i}x^{(i+1)}\to x^{(i)}s_{i}$.) As an
example calculation for (ii), we transform $\lambda_{i}t_{i}$ into
$t_{i}t_{i+1}\lambda_{i}$ using $R_{T}$, (9.62) and (9.64) as follows:

$\lambda_{i}t_{i}\to\rho_{i}s_{i}t_{i}\to\rho_{i}t_{i+1}s_{i}\to
t_{i}t_{i+1}\rho_{i}s_{i}\to t_{i}t_{i+1}\lambda_{i}.$

Each of the remaining results will involve a restriction of the surmorphism
$\Psi$ from Theorem 9.58, and a subset of the relations (9.59)–(9.65). The
proofs of the next two results are exactly as for Theorem 9.58, but with a
little less to check.

######  Theorem 9.67.

For $n\geq 2$, the wreath product $M\wr\mathcal{G}_{n}$ has presentation

$\textup{{Mon}}\langle{X_{M^{n}}\cup X_{G}}:{R_{M^{n}}\cup R_{G}\cup
R}\rangle$

via $\Psi\mathord{\restriction}_{(X_{M^{n}}\cup X_{G})^{*}}$, where $R$
consists of the relations (9.59). ∎

######  Theorem 9.68.

For $n\geq 2$, the wreath product $M\wr\mathcal{T}_{n}$ has presentation

$\textup{{Mon}}\langle{X_{M^{n}}\cup X_{T}}:{R_{M^{n}}\cup R_{T}\cup
R}\rangle$

via $\Psi\mathord{\restriction}_{(X_{M^{n}}\cup X_{T})^{*}}$, where $R$
consists of the relations (9.59)–(9.61). ∎

For the final result, we need to work just a little harder.

######  Theorem 9.69.

For $n\geq 2$, the wreath product $M\wr\mathcal{I}_{n}$ has presentation

$\textup{{Mon}}\langle{X_{M_{0}^{n}}\cup X_{G}}:{R_{M_{0}^{n}}\cup R_{G}\cup
R}\rangle$

via $\Psi\mathord{\restriction}_{(X_{M_{0}^{n}}\cup X_{G})^{*}}$, where $R$
consists of (9.59), (9.62), and the following relations:

$t_{i}t_{i+1}s_{i}=t_{i}t_{i+1}.$ (9.70)

###### Proof.

As in the proof of Theorem 9.58, we quickly obtain the presentation

$\textup{{Mon}}\langle{X_{M_{0}^{n}}\cup X_{G}}:{R_{M_{0}^{n}}\cup R_{G}\cup
R_{1}\cup R_{\Omega}}\rangle,$

where:

  * •

$R_{1}$ consists of relations (9.59) and (9.62), and

  * •

$R_{\Omega}=\big{\\{}{(N({\bf a}),N({\bf b}))}:{({\bf a},{\bf
b})\in\Omega}\big{\\}}$ for any generating set $\Omega$ for the congruence
$\theta$ on $M_{0}^{n}\rtimes\mathcal{G}_{n}$.

This time, Lemmas 9.52, 9.54 and 4.74(i) tell us that $\theta=\Omega^{\sharp}$
for

$\Omega=\big{\\{}{(({\bf v}_{ij},\mathrm{id}_{\bf n}),({\bf
v}_{ij},\tau_{ij}))}:{1\leq i<j\leq n}\big{\\}},$

where ${\bf v}_{ij}={\bf v}_{i}{\bf v}_{j}={\bf 1}_{{\bf
n}\setminus\\{i,j\\}}\equiv\mathrm{id}_{{\bf
n}\setminus\\{i,j\\}}=(t_{i}t_{j})\Psi$ for each $1\leq i<j\leq n$, and
$\tau_{ij}$ is the transposition $(i,j)$. Noting that
$\tau_{ij}=((s_{j-1}\cdots s_{i+1})s_{i}(s_{i+1}\cdots s_{j-1}))\phi_{G}$, the
resulting set $R_{\Omega}$ then consists of the relations

$t_{i}t_{j}=t_{i}t_{j}\cdot(s_{j-1}\cdots s_{i+1})s_{i}(s_{i+1}\cdots
s_{j-1})\qquad\text{for each $1\leq i<j\leq n$,}$ (9.71)

and we note that (9.70) contains only those with $j=i+1$. But it is easy to
see that (9.62) and (9.70) together imply (9.71). Indeed, writing $\sim$ for
the congruence generated by the claimed set of relations $R_{M_{0}^{n}}\cup
R_{G}\cup R$, it is easy to see that

$t_{i}(s_{j-1}\cdots s_{i+1})\sim(s_{j-1}\cdots
s_{i+1})t_{i}\qquad\text{and}\qquad t_{j}(s_{j-1}\cdots
s_{i+1})\sim(s_{j-1}\cdots s_{i+1})t_{i+1},$ (9.72)

and then

$\displaystyle t_{i}t_{j}(s_{j-1}\cdots s_{i+1})s_{i}(s_{i+1}\cdots s_{j-1})$
$\displaystyle\sim(s_{j-1}\cdots s_{i+1})t_{i}t_{i+1}s_{i}(s_{i+1}\cdots
s_{j-1})$ by (9.72) $\displaystyle\sim(s_{j-1}\cdots
s_{i+1})t_{i}t_{i+1}(s_{i+1}\cdots s_{j-1})$ by (9.70) $\displaystyle\sim
t_{i}t_{j}(s_{j-1}\cdots s_{i+1})(s_{i+1}\cdots s_{j-1})$ by (9.72)
$\displaystyle\sim t_{i}t_{j}$ $\displaystyle\text{by $R_{G}$.}\qed$

######  Remark 9.73.

Relations (9.70) are not included in the presentation from Theorem 9.58, even
though these relations obviously hold in the monoid
$M\wr\mathcal{P}\mathcal{T}_{n}$. We leave it as an exercise to show that
(9.70) follows from the relations listed in Theorem 9.58.

### References

  * [1] A. J. Aĭzenštat.  Defining relations of finite symmetric semigroups (in Russian).  Mat. Sb. N.S., 45 (87):261–280, 1958.
  * [2] A. J. Aĭzenštat.  The defining relations of the endomorphism semigroup of a finite linearly ordered set.  Sibirsk. Mat. Z̆., 3:161–169, 1962.
  * [3] J. Almeida, J.-E. Pin, and P. Weil.  Semigroups whose idempotents form a subsemigroup.  Math. Proc. Cambridge Philos. Soc., 111(2):241–253, 1992.
  * [4] E. Artin.  Theorie der Zöpfe.  Abh. Math. Sem. Univ. Hamburg, 4(1):47–72, 1925.
  * [5] E. Artin.  Theory of braids.  Ann. of Math. (2), 48:101–126, 1947.
  * [6] J. E. Ault.  Semigroups with midunits.  Trans. Amer. Math. Soc., 190:375–384, 1974.
  * [7] J. Berstel and D. Perrin.  Theory of codes, volume 117 of Pure and Applied Mathematics.  Academic Press, Inc., Orlando, FL, 1985.
  * [8] B. Billhardt.  Extensions of semilattices by left type-$A$ semigroups.  Glasgow Math. J., 39(1):7–16, 1997.
  * [9] M. J. J. Branco, G. M. S. Gomes, and V. Gould.  Extensions and covers for semigroups whose idempotents form a left regular band.  Semigroup Forum, 81(1):51–70, 2010.
  * [10] M. J. J. Branco, G. M. S. Gomes, and V. Gould.  Left adequate and left Ehresmann monoids.  Internat. J. Algebra Comput., 21(7):1259–1284, 2011.
  * [11] M. D. G. K. Brookes.  Congruences on the partial automorphism monoid of a free group action.  Internat. J. Algebra Comput., 31(6):1147–1176, 2021.
  * [12] S. Burris and H. P. Sankappanavar.  A course in universal algebra, volume 78 of Graduate Texts in Mathematics.  Springer-Verlag, New York-Berlin, 1981.
  * [13] J. W. Cannon, W. J. Floyd, and W. R. Parry.  Introductory notes on Richard Thompson’s groups.  Enseign. Math. (2), 42(3-4):215–256, 1996.
  * [14] S. Y. Chen and S. C. Hsieh.  Factorizable inverse semigroups.  Semigroup Forum, 8(4):283–297, 1974.
  * [15] C. Clark and J. East.  Presentations for wreath products involving symmetric inverse monoids and categories.  Preprint, 2022, arXiv:2204.06992.
  * [16] A. H. Clifford and G. B. Preston.  The algebraic theory of semigroups. Vol. I.  Mathematical Surveys, No. 7. American Mathematical Society, Providence, R.I., 1961.
  * [17] A. H. Clifford and G. B. Preston.  The algebraic theory of semigroups. Vol. II.  Mathematical Surveys, No. 7. American Mathematical Society, Providence, R.I., 1967.
  * [18] Y. Dandan, I. Dolinka, and V. Gould.  Free idempotent generated semigroups and endomorphism monoids of free $G$-acts.  J. Algebra, 429:133–176, 2015.
  * [19] I. Dolinka and J. East.  Semigroups of rectangular matrices under a sandwich operation.  Semigroup Forum, 96(2):253–300, 2018.
  * [20] I. Dolinka, I. Đurđev, J. East, P. Honyam, K. Sangkhanan, J. Sanwong, and W. Sommanee.  Sandwich semigroups in locally small categories I: foundations.  Algebra Universalis, 79(3):Art. 75, 35 pp, 2018.
  * [21] E. R. Dombi and N. Ruškuc.  On generators and presentations of semidirect products in inverse semigroups.  Bull. Aust. Math. Soc., 79(3):353–365, 2009.
  * [22] P. Dubreil.  Contribution à la théorie des demi-groupes.  Mém. Acad. Sci. Inst. France (2), 63(3):52, 1941.
  * [23] W. Dyck.  Gruppentheoretische Studien.  Math. Ann., 20(1):1–44, 1882.
  * [24] D. Easdown, J. East, and D. G. FitzGerald.  Presentations of factorizable inverse monoids.  Acta Sci. Math. (Szeged), 71(3-4):509–520, 2005.
  * [25] D. Easdown and T. G. Lavers.  The inverse braid monoid.  Adv. Math., 186(2):438–455, 2004.
  * [26] J. East.  A presentation of the singular part of the symmetric inverse monoid.  Comm. Algebra, 34(5):1671–1689, 2006.
  * [27] J. East.  Braids and partial permutations.  Adv. Math., 213(1):440–461, 2007.
  * [28] J. East.  Vines and partial transformations.  Adv. Math., 216(2):787–810, 2007.
  * [29] J. East.  A presentation for the singular part of the full transformation semigroup.  Semigroup Forum, 81(2):357–379, 2010.
  * [30] J. East.  Presentations for singular subsemigroups of the partial transformation semigroup.  Internat. J. Algebra Comput., 20(1):1–25, 2010.
  * [31] J. East.  Defining relations for idempotent generators in finite full transformation semigroups.  Semigroup Forum, 86(3):451–485, 2013.
  * [32] J. East.  Defining relations for idempotent generators in finite partial transformation semigroups.  Semigroup Forum, 89(1):72–76, 2014.
  * [33] J. East.  A symmetrical presentation for the singular part of the symmetric inverse monoid.  Algebra Universalis, 74(3-4):207–228, 2015.
  * [34] J. East.  Idempotents and one-sided units in infinite partial Brauer monoids.  J. Algebra, 534:427–482, 2019.
  * [35] J. East.  Idempotents and one-sided units: lattice invariants and a semigroup of functors on the category of monoids.  J. Algebra, 560:1219–1252, 2020.
  * [36] J. East.  Presentations for tensor categories.  Preprint, 2020, arXiv:2005.01953.
  * [37] J. East.  Presentations for $\mathbb{P}^{K}$.  Monatsh. Math., to appear, arXiv:2105.06127.
  * [38] J. East and D. G. FitzGerald.  The semigroup generated by the idempotents of a partition monoid.  J. Algebra, 372:108–133, 2012.
  * [39] B. Everitt and J. Fountain.  Partial symmetry, reflection monoids and Coxeter groups.  Adv. Math., 223(5):1782–1814, 2010.
  * [40] B. Everitt and J. Fountain.  Partial mirror symmetry, lattice presentations and algebraic monoids.  Proc. Lond. Math. Soc. (3), 107(2):414–450, 2013.
  * [41] Y.-Y. Feng, A. Al-Aadhami, I. Dolinka, J. East, and V. Gould.  Presentations for singular wreath products.  J. Pure Appl. Algebra, 223(12):5106–5146, 2019.
  * [42] D. G. FitzGerald.  Factorizable inverse monoids.  Semigroup Forum, 80(3):484–509, 2010.
  * [43] J. Fountain.  A class of right PP monoids.  Quart. J. Math. Oxford Ser. (2), 28(111):285–300, 1977.
  * [44] J. Fountain.  Adequate semigroups.  Proc. Edinburgh Math. Soc. (2), 22(2):113–125, 1979.
  * [45] J. Fountain.  Free right type $A$ semigroups.  Glasgow Math. J., 33(2):135–148, 1991.
  * [46] J. Fountain and G. M. S. Gomes.  Proper left type-$A$ monoids revisited.  Glasgow Math. J., 35(3):293–306, 1993.
  * [47] J. Fountain, G. M. S. Gomes, and V. Gould.  The free ample monoid.  Internat. J. Algebra Comput., 19(4):527–554, 2009.
  * [48] J. Fountain and A. Lewin.  Products of idempotent endomorphisms of an independence algebra of infinite rank.  Math. Proc. Cambridge Philos. Soc., 114(2):303–319, 1993.
  * [49] J. Fountain, J.-E. Pin, and P. Weil.  Covers for monoids.  J. Algebra, 271(2):529–586, 2004.
  * [50] The GAP Group.  GAP – Groups, Algorithms, and Programming.
  * [51] G. M. S. Gomes and V. Gould.  Proper weakly left ample semigroups.  Internat. J. Algebra Comput., 9(6):721–739, 1999.
  * [52] G. M. S. Gomes and V. Gould.  Graph expansions of unipotent monoids.  Comm. Algebra, 28(1):447–463, 2000.
  * [53] G. M. S. Gomes and V. Gould.  Fundamental Ehresmann semigroups.  Semigroup Forum, 63(1):11–33, 2001.
  * [54] V. Gould.  Independence algebras.  Algebra Universalis, 33(3):294–318, 1995.
  * [55] V. Gould.  Graph expansions of right cancellative monoids.  Internat. J. Algebra Comput., 6(6):713–733, 1996.
  * [56] V. Gould.  Notes on restriction semigroups and related structures.  `https://www-users.york.ac.uk/~varg1/restriction.pdf`, 2010.
  * [57] V. Gould and M. B. Szendrei.  Proper restriction semigroups—semidirect products and $W$-products.  Acta Math. Hungar., 141(1-2):36–57, 2013.
  * [58] J. A. Green.  On the structure of semigroups.  Ann. of Math. (2), 54:163–172, 1951.
  * [59] W. R. Hamilton.  Memorandum respecting a new system of roots of unity.  Philos. Mag., 12(81):446–446, 1856.
  * [60] J. B. Hickey.  Semigroups under a sandwich operation.  Proc. Edinburgh Math. Soc. (2), 26(3):371–382, 1983.
  * [61] J. B. Hickey.  On variants of a semigroup.  Bull. Austral. Math. Soc., 34(3):447–459, 1986.
  * [62] P. M. Higgins.  Techniques of semigroup theory.  Oxford Science Publications. The Clarendon Press, Oxford University Press, New York, 1992.
  * [63] P. Honyam and J. Sanwong.  Semigroups of transformations with fixed sets.  Quaest. Math., 36(1):79–92, 2013.
  * [64] J. M. Howie.  Fundamentals of semigroup theory, volume 12 of London Mathematical Society Monographs. New Series.  The Clarendon Press, Oxford University Press, New York, 1995.  Oxford Science Publications.
  * [65] J. M. Howie and N. Ruškuc.  Constructions and presentations for monoids.  Comm. Algebra, 22(15):6209–6224, 1994.
  * [66] J. E. Humphreys.  Reflection groups and Coxeter groups, volume 29 of Cambridge Studies in Advanced Mathematics.  Cambridge University Press, Cambridge, 1990.
  * [67] P. R. Jones.  Exchange properties and basis properties for closure operators.  Colloq. Math., 57(1):29–33, 1989.
  * [68] M. Kambites.  Free adequate semigroups.  J. Aust. Math. Soc., 91(3):365–390, 2011.
  * [69] M. Kilp, U. Knauer, and A. V. Mikhalev.  Monoids, acts and categories, volume 29 of de Gruyter Expositions in Mathematics.  Walter de Gruyter & Co., Berlin, 2000.  With applications to wreath products and graphs, A handbook for students and researchers.
  * [70] U. Knauer and A. Mikhalev.  Endomorphism monoids of free acts and $0$-wreath products of monoids. I. Annihilator properties.  Semigroup Forum, 19(2):177–187, 1980.
  * [71] U. Knauer and A. Mikhalev.  Endomorphism monoids of free acts and $0$-wreath products of monoids. II. Regularity.  Semigroup Forum, 19(3):189–198, 1980.
  * [72] U. Knauer and A. Mikhalev.  Endomorphism monoids of free acts and $0$-wreath products of monoids. III. Standard involution and continuous endomorphisms.  Semigroup Forum, 19(4):355–369, 1980.
  * [73] T. G. Lavers.  The theory of vines.  Comm. Algebra, 25(4):1257–1284, 1997.
  * [74] T. G. Lavers.  Presentations of general products of monoids.  J. Algebra, 204(2):733–741, 1998.
  * [75] M. V. Lawson.  The structure of type $A$ semigroups.  Quart. J. Math. Oxford Ser. (2), 37(147):279–298, 1986.
  * [76] M. V. Lawson.  Almost factorisable inverse semigroups.  Glasgow Math. J., 36(1):97–111, 1994.
  * [77] M. V. Lawson.  Inverse semigroups.  World Scientific Publishing Co., Inc., River Edge, NJ, 1998.  The theory of partial symmetries.
  * [78] M. V. Lawson and S. W. Margolis.  In McAlister’s footsteps: a random ramble around the $P$-theorem.  In Semigroups and formal languages, pages 145–163. World Sci. Publ., Hackensack, NJ, 2007.
  * [79] L. Lima.  The Local Automorphism Monoid of an Independence Algebra.  PhD thesis, University of York, 1994.
  * [80] E. Marczewski.  Independence in algebras of sets and Boolean algebras.  Fund. Math., 48:135–145, 1959/60.
  * [81] S. Margolis, F. Saliola, and B. Steinberg.  Semigroups embeddable in hyperplane face monoids.  Semigroup Forum, 89(1):236–248, 2014.
  * [82] S. Margolis, F. Saliola, and B. Steinberg.  Combinatorial topology and the global dimension of algebras arising in combinatorics.  J. Eur. Math. Soc. (JEMS), 17(12):3037–3080, 2015.
  * [83] S. W. Margolis and J.-E. Pin.  Inverse semigroups and extensions of groups by semilattices.  J. Algebra, 110(2):277–297, 1987.
  * [84] A. Markov.  The impossibility of certain algorithms in the theory of associative systems. II.  Doklady Akad. Nauk SSSR (N.S.), 58:353–356, 1947.
  * [85] V. Mazorchuk and S. Srivastava.  Jucys-murphy elements and grothendieck groups for generalized rook monoids.  Preprint, 2021, arXiv:2104.13632.
  * [86] D. B. McAlister.  Groups, semilattices and inverse semigroups.  Trans. Amer. Math. Soc., 192:227–244, 1974.
  * [87] D. B. McAlister.  Groups, semilattices and inverse semigroups II.  Trans. Amer. Math. Soc., 196:351–370, 1974.
  * [88] D. B. McAlister.  Some covering and embedding theorems for inverse semigroups.  J. Austral. Math. Soc. Ser. A, 22(2):188–211, 1976.
  * [89] R. N. McKenzie, G. F. McNulty, and W. F. Taylor.  Algebras, lattices, varieties. Vol. I.  The Wadsworth & Brooks/Cole Mathematics Series. Wadsworth & Brooks/Cole Advanced Books & Software, Monterey, CA, 1987.
  * [90] J. D. P. Meldrum.  Wreath products of groups and semigroups, volume 74 of Pitman Monographs and Surveys in Pure and Applied Mathematics.  Longman, Harlow, 1995.
  * [91] J. D. Mitchell et al.  Semigroups - GAP package.
  * [92] E. H. Moore.  Concerning the abstract groups of order $k!$ and $\tfrac{1}{2}k!$ holohedrically isomorphic with the symmetric and the alternating substitution-groups on $k$ letters.  Proc. London Math. Soc., 28(1):357–366, 1897.
  * [93] W. D. Munn.  Fundamental inverse semigroups.  Quart. J. Math. Oxford Ser. (2), 21:157–170, 1970.
  * [94] W. D. Munn.  Free inverse semigroups.  Proc. London Math. Soc. (3), 29:385–404, 1974.
  * [95] W. D. Munn.  A note on $E$-unitary inverse semigroups.  Bull. London Math. Soc., 8(1):71–76, 1976.
  * [96] W. Narkiewicz.  Independence in a certain class of abstract algebras.  Fund. Math., 50:333–340, 1961/62.
  * [97] C.-F. Nyberg-Brodda.  The B B Newman spelling theorem.  Br. J. Hist. Math., 36(2):117–131, 2021.
  * [98] L. O’Carroll.  Embedding theorems for proper inverse semigroups.  J. Algebra, 42(1):26–40, 1976.
  * [99] M. Petrich and N. R. Reilly.  A representation of $E$-unitary inverse semigroups.  Quart. J. Math. Oxford Ser. (2), 30(119):339–350, 1979.
  * [100] L. M. Popova.  Defining relations in some semigroups of partial transformations of a finite set (in Russian).  Uchenye Zap. Leningrad Gos. Ped. Inst., 218:191–212, 1961.
  * [101] L. M. Popova.  Defining relations of a semigroup of partial endomorphisms of a finite linearly ordered set (in Russian).  Leningrad. Gos. Ped. Inst. Učen. Zap., 238:78–88, 1962.
  * [102] E. L. Post.  Recursive unsolvability of a problem of Thue.  J. Symbolic Logic, 12:1–11, 1947.
  * [103] G. B. Preston.  Semidirect products of semigroups.  Proc. Roy. Soc. Edinburgh Sect. A, 102(1-2):91–102, 1986.
  * [104] J. Rhodes and B. Steinberg.  The $q$-theory of finite semigroups.  Springer Monographs in Mathematics. Springer, New York, 2009.
  * [105] E. F. Robertson, N. Ruškuc, and M. R. Thomson.  Finite generation and presentability of wreath products of monoids.  J. Algebra, 266(2):382–392, 2003.
  * [106] E. F. Robertson, N. Ruškuc, and J. Wiegold.  Generators and relations of direct products of semigroups.  Trans. Amer. Math. Soc., 350(7):2665–2685, 1998.
  * [107] N. Ruškuc.  Presentations for subgroups of monoids.  J. Algebra, 220(1):365–380, 1999.
  * [108] H. E. Scheiblich.  Free inverse semigroups.  Proc. Amer. Math. Soc., 38:1–7, 1973.
  * [109] L. A. Skornjakov.  Regularity of the wreath product of monoids.  Semigroup Forum, 18(1):83–86, 1979.
  * [110] W. Specht.  Eine Verallgemeinerung der Permutationsgruppen.  Math. Z., 37(1):321–341, 1933.
  * [111] B. Steinberg.  McAlister’s $P$-theorem via Schützenberger graphs.  Comm. Algebra, 31(9):4387–4392, 2003.
  * [112] M. B. Szendrei.  On a pullback diagram for orthodox semigroups.  Semigroup Forum, 20(1):1–10, 1980.
  * [113] M. B. Szendrei.  Correction and supplement to: “On a pullback diagram for orthodox semigroups” [Semigroup Forum 20 (1980), no. 1, 1–10; MR 81m:20085].  Semigroup Forum, 25(3-4):311–324, 1982.
  * [114] M. B. Szendrei.  Embedding into almost left factorizable restriction semigroups.  Comm. Algebra, 41(4):1458–1483, 2013.
  * [115] P. G. Trotter.  Covers for regular semigroups and an application to complexity.  J. Pure Appl. Algebra, 105(3):319–328, 1995.
  * [116] A. M. Turing.  The word problem in semi-groups with cancellation.  Ann. of Math. (2), 52:491–505, 1950.
  * [117] K. Urbanik.  Linear independence in abstract algebras.  Colloq. Math., 14:233–255, 1966.
  * [118] M. Yamada.  A note on middle unitary semigroups.  Kōdai Math. Sem. Rep., 7:49–52, 1955.
  * [119] R. Zenab.  Algebraic properties of Zappa-Szép products of semigroups and monoids.  Semigroup Forum, 96(2):316–332, 2018.