# Left restriction monoids from left $E$-completions

Tim Stokes

###### Abstract

Given a monoid $S$ with $E$ any non-empty subset of its idempotents, we
present a novel one-sided version of idempotent completion we call left
$E$-completion. In general, the construction yields a one-sided variant of a
small category called a constellation by Gould and Hollings. Under certain
conditions, this constellation is inductive, meaning that its partial
multiplication may be extended to give a left restriction semigroup, a type of
unary semigroup whose unary operation models domain. We study the properties
of those pairs $S,E$ for which this happens, and characterise those left
restriction semigroups that arise as such left $E$-completions of their monoid
of elements having domain $1$. As first applications, we decompose the left
restriction semigroup of partial functions on the set $X$ and the right
restriction semigroup of left total partitions on $X$ as left and right
$E$-completions respectively of the transformation semigroup $T_{X}$ on $X$,
and decompose the left restriction semigroup of binary relations on $X$ under
demonic composition as a left $E$-completion of the left-total binary
relations. In many cases, including these three examples, the construction
embeds in a semigroup Zappa-Szép product.

Keywords: Left restriction semigroup, partial function monoid, partition
monoid, constellation.

2010 Mathematics Subject Classification: 20M10, 20M20, 20M30.

##  1 Introduction

The full transformation semigroup $T_{X}$ on the non-empty set $X$ is perhaps
the most important example of a semigroup. However, the larger monoid $PT_{X}$
of partial transformations on $X$ is amongst the most important. $PT_{X}$ is
frequently viewed as a unary semigroup, equipped with unary operation $D$
given by $D(f)=\\{(x,x)\mid x\in\mbox{dom}(f)\\}$, the identity map on
$\mbox{dom}(f)$. When equipped with $D$, $PT_{X}$ is a left restriction
semigroup. The class of left restriction semigroups is an equational class of
unary semigroups, and $PT_{X}$ is canonical in the sense that all embed in one
such: see [22], as well as [12] and [16]. Left restriction semigroups have
received increasing attention in recent years.

There are other examples of left restriction semigroups. The monoid of binary
relations $Rel_{X}$ under relational composition may be equipped with a domain
operation $D$ defined as for $PT_{X}$, but the resulting unary semigroup is
not a left restriction semigroup (although it satisfies most of their defining
laws). However, if one replaces the usual composition operation by so-called
demonic composition $\circledast$, $(Rel_{X},\circledast,D)$ is a left
restriction semigroup. Demonic composition is of interest in computer science
because of its connection with total correctness of (possibly non-
deterministic) programs; see [2] for example. A further example, on this
occasion a right restriction semigroup, arises from the partition monoid
$P_{X}$ on a set $X$: the submonoid $P^{lt}_{X}$ of $P_{X}$ consisting of left
total partitions (defined in the natural way).

In what follows, we show that each of the families of examples just mentioned
arises via a straightforward construction we call left (or sometimes right)
$E$-completion. It follows that each can be built from the submonoid of
elements of domain (or perhaps range) $1$, together with some suitable
idempotents $E$ of this submonoid. We characterise those left restriction
semigroups that arise from such a construction. In particular, $PT_{X}$ can be
constructed from $T_{X}$ using this construction, as can $Rel_{X}$ under
demonic composition and domain. But more surprisingly, $P^{lt}_{X}$ can be
obtained from $T_{X}$ using the right-sided version of the construction.

We now describe the construction in more detail. Recall that the idempotent
completion of a semigroup $S$ having non-empty idempotent set $E(S)$ is a
well-known category. Generalising, for any non-empty $E\subseteq E(S)$, define

$Cat_{E}(S)=\\{(e,s,f)\in E\times S\times E\mid esf=s\\}.$

Define the partial binary operation $\circ$ on $Cat_{E}(S)$ by setting

$(e,s,f)\circ(f,t,g):=(e,st,g),$

with no other products defined. Also define $D((e,s,f))=(e,e,e)$ and
$R((e,s,f))=(f,f,f)$. It is routine to check that $\circ$ is well-defined, and
that $(Cat_{E}(S),\circ,D,R)$ is a small category with domain and range
operations $D$ and $R$ respectively. We call this category the $E$-completion
of $S$. If $E=E(S)$, this is nothing but the Karoubi envelope or idempotent
completion of the semigroup; see Part C of [21], where this is defined for an
arbitrary semigroup, though not under either of the above names. Prior to
[21], the concept was in use by category theorists as a way of canonically
embedding a category into a larger one in which every idempotent splits.

We are interested in a one-sided version of $E$-completion.

###### Definition 1.1

Let $S$ be a semigroup, with $E\subseteq E(S)$. Define

$C_{E}(S)=\\{(e,s)\in E\times S\mid es=s\\}.$

Define the partial binary operation $\circ$ on $C_{E}(S)$ by setting
$(e,s)\circ(f,t)=(e,st)\mbox{ whenever }sf=s$, and define $D((e,s))=(e,e)$.
The structure $(C_{E}(S),\circ,D)$ is the left $E$-completion of $S$.

The left $E$-completion $C_{E}(S)$ is not a category, but it is a
constellation, in the sense defined by Gould and Hollings in [8] and then
considered further in [9] and [10]. In [8], constellations were defined in
order to describe partial algebraic counterparts of left restriction
semigroups. This followed earlier work in which inverse semigroups were shown
to correspond to inductive groupoids by Ehresmann and Schein (see [5], [18]),
as well as work due to Lawson showing that so-called Ehresmann semigroups
correspond to so-called Ehresmann categories (see [15]), a special case of
which is the fact that two-sided restriction semigroups correspond to
inductive categories. Ehresmann and restriction semigroups have both domain
and range operations, while left restriction semigroups have only domain, so
the first task for Gould and Hollings was to replace categories by some one-
sided analog, namely constellations. Constellations have an (asymmetric)
partial binary composition operation and a domain operation but no range.

In what follows, we make use of the notion of a demigroup introduced in [20],
in order to consider variants of left $E$-completions as just defined. The
demigroup $S$ is a unary semigroup with unary operation $d$ mapping into
$E(S)$ and otherwise satisfying only the two laws $d(x)x=x$ and
$d(xy)=d(xd(y))$. Demigroups were defined in [20] based on the most general
way in which a constellation can arise from a unary semigroup in a sense we
describe in detail later.

###### Definition 1.2

Let $S$ be a demigroup, with $E\subseteq E(S)$ such that $d(s)\in E$ for all
$s\in S$, and $ed(e)=e$ for all $e\in E$. Then we say $S$ is an $E$-demigroup.
Define

$C^{d}_{E}(S)=\\{(e,s)\in E\times S\mid es=s,d(e)=d(s)\\}.$

Define the partial binary operation $\circ$ on $C^{d}_{E}(S)$ as well as the
unary operation $D$ as for $C_{E}(S)$. The structure $(C^{d}_{E}(S),\circ,D)$
is the left $(d,E)$-completion of $S$.

We shall show that $C^{d}_{E}(S)$ is a subconstellation of $C_{E}(S)$ in
general. But there are two special cases of the greatest importance in what
follows.

###### Definition 1.3

Let $S$ be a monoid which is an $E$-demigroup, with $1\in E\subseteq E(S)$. If
$d(s)=1$ for all $s\in S$, then we say $S$ is a left $E$-monoid, and also
denote $C^{d}_{E}(S)$ as $C_{E}(S)$. If $S$ has a zero $0$ and $d(0)=0$ with
$d(s)\neq 0$ if $s\neq 0$, we say $S$ is a left $E$-monoid with zero, and
$C^{d}_{E}(S)$ as $C^{0}_{E}(S)$.

As shown below, it is easy to describe all left $E$-monoids and left
$E$-monoids with zero: the former arise from any monoid $S$ with distinguished
set of idempotents $E\subseteq E(S)$ with $1\in E$ and defining $d(s)=1$ for
all $s\in S$, and the latter from any monoid with adjoined zero element and
distinguished $E\subseteq E(S)$ with $0,1\in E$ and defining $d(0)=0$ and
$d(s)=1$ otherwise. Note that if $S$ is a left $E$-monoid, then

$C^{d}_{E}(S)=C_{E}(S),$

and if $S$ is a left $E$-monoid with zero, then

$C^{d}_{E}(S)=\\{(e,s)\in C_{E}(S)\mid s=0\Rightarrow e=0\\}\subseteq
C_{E}(S),$

and we denote $C^{d}_{E}(S)$ in the latter case by $C^{0}_{E}(S)$.

The motivation behind our definition of $C^{d}_{E}(S)$ in terms of
$E$-demigroups was to avoid the necessity of several slightly different
definitions and proofs involving $C_{E}(S)$ and $C^{0}_{E}(S)$ for these two
cases. As an added bonus, the case in which $S$ is a demigroup and we set
$E=d(S)=\\{d(s)\mid s\in S\\}$, giving $C^{d}_{d(S)}(S)$, allows the main
construction of [20] to be viewed as a special case of the current approach.
Other special cases may prove of interest in the future.

As outlined above, the reason for introducing constellations in [8] was to
retain from a left restriction semigroup only those products that were needed
to re-construct it from the partial algebraic structure, but one can reverse
this. In the current case, a natural question is: when is the constellation
$C^{d}_{E}(S)$ inductive, hence nothing but a “left restriction semigroups in
disguise”? And when does a given left restriction semigroup arise in this way?
In what follows, we obtain a complete answer to the first question by
characterising exactly when $C^{d}_{E}(S)$ is inductive in terms of conditions
on the $E$-demigroup $S$. We then characterise those left restriction
semigroups that arise as $C_{E}(S)$ or $C^{0}_{E}(S)$, and show that important
examples of left restriction semigroups arise in this way.

In Section 2 to follow, we work through some preliminaries, with discussion of
constellations and left restriction semigroups and the connections between
them, as well as of demigroups. Section 3 defines $E$-demigroups and their
left $(d,E)$-completions, and we establish exactly when an $E$-demigroup $S$
gives rise to an inductive constellation $C^{d}_{E}(S)$, with particular
reference to the special cases $C_{E}(S)$ and $C^{0}_{E}(S)$. Then in Section
4, we give an internal characterisation of those left restriction semigroups
that arise as either $C_{E}(S)$ or $C^{0}_{E}(S)$, and the pairs $S,E$
satisfying the necessary and sufficient conditions are considered for their
own sake in Section 5. In Section 6, we make a connection with semigroup
Zappa-Szép products.

In Section 7, we give three applications. It is shown that the left
restriction semigroup $(PT_{X},\cdot,D)$ (where $\cdot$ is composition) is the
zero-reduced left $E$-completion of $(T_{X}^{0},\cdot)$ (which is $T_{X}$ with
adjoined zero element) for any $E\subseteq E(S)$ that is maximal right pre-
reduced (defined below). The left restriction semigroup of binary relations
$Rel_{X}$ under demonic composition, $(Rel_{X},\circledast,D)$, is then shown
to be the zero-reduced left $E$-completion of the submonoid of left total
binary relations for the same choice of $E\subseteq T_{X}^{0}\subseteq
Rel_{X}^{0}$ as in the previous example. Finally, and perhaps most unexpected,
the right restriction semigroup $(P^{lt}_{X},\cdot,R)$ consisting of left
total partitions on $X$ is shown to be the right $E$-completion of $T_{X}$
using any maximal left pre-reduced set of idempotents $E$. It is shown that
with careful choice of $E$, each of these constructions can be viewed as
embedded in a semigroup Zappa-Szép product.

In the final section we briefly discuss some directions for future work.

##  2 Preliminaries

The current work combines many topics, so we begin with a review of them.

###  2.1 Some properties of idempotents

Throughout this subsection, $S$ is a semigroup. The natural right quasiorder
on $E(S)$ is given by $e\leq_{r}f$ if and only if $e=ef$, and the natural left
quasiorder on $E(S)$ is given by $e\leq_{l}f$ if and only if $e=fe$. Denote by
$\sim_{r}$ and $\sim_{l}$ the respective induced equivalence relations. The
natural order $\leq$ on $E(S)$ is the intersection of $\leq_{l}$ and
$\leq_{r}$, so that $e\leq f$ if and only if $e=ef=fe$, and is a partial order
on $E(S)$, with respect to which $1$ is the top element if $S$ is a monoid
with identity $1$.

Let $E$ be a nonempty subset of $E(S)$. All of the following concepts are
defined in [19], although many of them were first defined earlier than that.
We say $E$ is right pre-reduced if $\leq_{r}$ is a partial order (that is,
$e=ef$ and $f=fe$ imply $e=f$), and left pre-reduced if $\leq_{l}$ is a
partial order. Clearly, $E\subseteq E(S)$ is right pre-reduced if and only if
no two elements of $E$ are related by $\sim_{r}$.

$E$ is said to be right reduced if for all $e,f\in E$, $e=ef$ implies $e=fe$.
There is an obvious dual notion of left reduced. $E$ is reduced if it is both
left reduced and right reduced; this concept was defined in [15]. If the
elements of $E$ commute with one-another then $E$ is evidently reduced.
Obviously, if $E$ is right reduced, then it is right pre-reduced, although the
converse fails in general. So $E$ is right reduced if
${\leq_{r}}\subseteq{\leq_{l}}$ (which happens if and only if $\leq_{r}$ is
the natural order on $E$), left reduced if the opposite inclusion holds, and
reduced if ${\leq_{r}}={\leq_{l}}$.

###### Definition 2.1

Let $S$ be a semigroup. We say that the two right pre-reduced sets $E$ and
$E^{\prime}\subseteq E(S)$ are right-equivalent, and write
$E\sim_{r}E^{\prime}$, if there is a bijection $e\mapsto e^{\prime}$ from $E$
to $E^{\prime}$ such that $e\sim_{r}e^{\prime}$. Left-equivalence is defined
dually.

If two right pre-reduced sets $E,E^{\prime}\subseteq E(S)$ are right-
equivalent, then it is easily seen that
$(E,\leq_{r})\cong(E^{\prime},\leq_{r})$ as posets.

If we pick precisely one element of $E(S)$ from each $\sim_{r}$-class to give
$F\subseteq E(S)$, then $F$ is right pre-reduced; moreover every right pre-
reduced $E\subseteq E(S)$ may be extended to such $F$. We therefore call such
$F$ a maximal right pre-reduced subset of $E(S)$. Obviously, any two maximal
right pre-reduced subsets are right-equivalent. All these comments and
definitions have dual left-sided versions.

The following elementary facts will be useful in what follows.

###### Lemma 2.2

Let $S$ be a semigroup. Pick $s,t\in S$ and $e,e^{\prime},f,f^{\prime}\in
E(S)$ with $e\sim_{r}e^{\prime}$ and $f\sim_{r}f^{\prime}$.

  1. 1.

If $se=s$ then $se^{\prime}=s$.

  2. 2.

If $es=et$ then $e^{\prime}s=e^{\prime}t$.

  3. 3.

If $esf=es$ then $e^{\prime}sf^{\prime}=e^{\prime}s$.

For $S$ a semigroup and $a\in S$, denote by $Sa=\\{sa\mid s\in S\\}$, the left
ideal generated by $a\in S$. If $a\in E(S)$ or if $S$ is a monoid, then $a\in
Sa$.

The following is easily seen.

###### Lemma 2.3

Let $S$ be a semigroup. Then for $e,f\in E(S)$, $Se=Sf$ if and only if
$e\sim_{r}f$.

###### Definition 2.4

In a semigroup $S$, define $Eq(s,t)=\\{u\in S\mid us=ut\\}$, a left ideal of
$S$ if non-empty, the (left) equalizing set of $s,t$. If $Eq(s,t)=Se$ for some
$e\in E(S)$, we call $e$ a left equalizer of $(s,t)$, and we say $e$ equalizes
$(s,t)$. Dually, define $REq(s,t)=\\{u\in S\mid su=tu\\}$, a right ideal of
$S$ if non-empty, and define right equalizers dually to left equalizers.

Obviously, this notion of left equalizer is different to the category notion.

###### Proposition 2.5

Let $S$ be a semigroup with $s,t\in S$, and suppose $e$ equalizes $(s,t)$.
Then $f$ equalizes $(s,t)$ if and only if $e\sim_{r}f$. Moreover, for all
$s\in S$ and $e,f\in E(S)$ for which $e\sim_{r}f$, $Eq(s,se)=Eq(s,sf)$.

Proof. If $e$ equalizes $(s,t)$ then $Eq(s,t)=Se$. The following are then
equivalent by Lemma 2.3: $f$ equalizes $(s,t)$; $Se=Sf$; $e\sim_{r}f$.

The final statement follows because for all $s,t\in S$ and $e,f\in E(S)$ with
$e\sim_{r}f$, $tse=ts$ if and only if $tsf=ts$ by (1) of Lemma 2.2. $\Box$

###  2.2 Left restriction semigroups and their generalisations

The semigroups of most interest to us here are unary semigroups equipped with
an operation $D$, called domain. The class of left restriction semigroups
satisfies the following laws (see [8]):

  1. (R1)

$D(x)x=x$;

  2. (R2)

$D(x)D(y)=D(y)D(x)$;

  3. (R3)

$D(D(x)y)=D(x)D(y)$;

  4. (R4)

$xD(y)=D(xy)x$.

Other useful laws follow easily such as

  1. (R5)

$D(xy)=D(xD(y))$ (the left congruence condition).

Other equivalent axioms have been used by various authors. There is an obvious
dual notion of right restriction semigroup; the unary operation is typically
denoted $R$ (“range”) in such cases.

It can easily be shown that in a left restriction semigroup $S$,
$D(S)=\\{D(s)\mid s\in S\\}$ is a semilattice under multiplication, and $D(s)$
is the smallest $e\in D(S)$ (with respect to the induced (meet-)semilattice
order on $D(S)$) such that $es=s$; see [12]. The natural order on $S$ if given
by $s\leq t$ if and only if $s=D(s)t$, or equivalently, $s=et$ for some $e\in
D(S)$; the natural order is a partial order on $S$ which restricts to the
semilattice order on $D(S)$.

Perhaps the most important example of a left restriction semigroup is the
semigroup under composition of partial functions $X\rightarrow X$ for some
non-empty set $X$, denoted $PT_{X}$ and equipped with domain operation given
by $D(s)=\\{(x,x)\mid x\in\mbox{dom}(s)\\}$. Every left restriction semigroup
embeds in $PT_{X}$ for some $X$, as was first shown in [22]; see also [12] and
[16].

We say the left restriction semigroup $S$ has a zero if $S$ has a semigroup
zero $0$ such that $0\in D(S)$ (equivalently, $D(0)=0$). For example, $PT_{X}$
is a left restriction semigroup with zero the empty function. We call any left
restriction semigroup $S$ that is a monoid with identity $1$ a left
restriction monoid; in this case, $1=D(1)1=D(1)$, so $1\in D(S)$, and the
subset $S_{1}=\\{s\in S\mid D(s)=1\\}$ is a submonoid of $S$ (since if $s,t\in
S_{1}$ then $D(st)=D(sD(t))=D(s1)=D(s)=1$). $(PT_{X})_{1}$ is evidently
identifiable with $T_{X}$, and we so identify it in what follows.

The left restriction semigroup axioms have been weakened in various ways. The
class of LC-semigroups is defined in [12] to consist of those unary semigroups
$S$ with unary operation $D$ such that $D(S)=\\{D(s)\mid s\in S\\}$ is a
semilattice, with $D(s)$ the smallest $e\in D(S)$ such that $es=s$. These are
given an equational axiomatisation in [12], generalising the above axioms for
left restriction semigroups; indeed an RC-semigroup is a left restriction
semigroup if and only if law (R4) above holds. The same concept was also
considered by Batbedat in [1] where they were called type SL
$\gamma$-semigroups. There is an obvious dual concept of RC-semigroup defined
in terms of a range operation $R$.

###  2.3 Constellations, left restriction semigroups and demigroups

Next we define the partial algebras that will form the basis of our main
construction. These are one-sided generalisations of categories called
constellations. Following [10], a constellation $P$ is a partial algebra
equipped with a partial binary operation and a unary “domain” operation $D$,
such that for all $x,y,z\in P$,

  1. (C1)

if $x\circ(y\circ z)$ exists then so does $(x\circ y)\circ z$, and then the
two are equal;

  2. (C2)

if $x\circ y$ and $y\circ z$ exist then $x\circ(y\circ z)$ exists;

  3. (C3)

$D(x)$ is the unique right identity such that $D(x)\circ x=x$.

(We say $e$ is a right identity for a partial binary operation $\circ$ if for
all $a$, if $a\circ e$ exists then it equals $a$.)

These axioms generalise the object-free axioms for small categories: there is
no range operation $R$, there is asymmetry in the first law, and one law for
categories is missing entirely.

Let $P$ be a constellation. Then $D(P)=\\{D(s)\mid s\in P\\}$ is the set of
all right identities in $P$, and $e\circ e$ exists (hence equals $e$) for all
$e\in D(P)$; moreover, for $s,t\in P$, $s\circ t$ exists if and only if
$s\circ D(t)$ does. For $e,f\in D(P)$, setting $e\leq f$ if and only if
$e\circ f$ exists makes $\leq$ a quasiorder. This extends to the natural
quasiorder on $P$ given by $s\leq t$ if and only if $D(s)\circ t$ exists and
equals $s$, or equivalently, $s=e\circ t$ for some $e\in D(P)$. If one of
these quasiorders is a partial order, so is the other, and then following
[10], $P$ is said to be normal, and $\leq$ is called the natural order on $P$.
Normality of $P$ is evidently equivalent to the condition that for all $e,f\in
D(P)$, if $e\circ f$ and $f\circ e$ exist then $e=f$.

As in [10], the subset $Q$ of the constellation $P$ is a subconstellation of
$P$ if $D(s)\in Q$ for all $s\in Q$, and if $s\circ t$ exists in $P$ for some
$s,t\in Q$, then $s\circ t\in Q$. In this case $Q$ is itself a constellation
under the inherited partial operations, by Proposition $2.18$ in [10].

There is a notion analogous to that of a functor for constellations. Suppose
$P,Q$ are constellations. Following [8], we say the the function
$\rho:P\rightarrow Q$ is a radiant if the following two conditions hold:

  1. 1.

for all $s,t\in P$, if $s\circ t$ exists, then so does $\rho(s)\circ\rho(t)$,
and $\rho(s\circ t)=\rho(s)\circ\rho(t)$, and

  2. 2.

for all $s\in P$, $\rho(D(s))=D(\rho(s))$.

The radiant $\rho$ is strong if for all $s,t\in P$, if $\rho(s)\circ\rho(t)$
exists then so does $s\circ t$, is an embedding if it is an injective strong
radiant, and is an isomorphism if it is a surjective embedding in which case
we write $P\cong Q$. These definitions are the standard ones for partial
algebras, as in [7] for instance. It also follows that a radiant $\rho$ is an
isomorphism if and only if it has an inverse function which is a radiant.

Constellations were introduced in [8] in order to obtain a kind of “ESN
Theorem” for left restriciton semigroups. There, it was shown that a left
restriction semigroup can be made into a constellation by defining $s\circ
t:=st$ but only when $sD(t)=s$, and by retaining $D$. When this is done, the
natural order in the left restriction semigroup coincides with the natural
order on the derived constellation. A constellation arises from a left
restriction semigroup in this way if and only if it is inductive in the sense
of [8]. The inductive property was shown in [10] to be equivalent to the
following conditions on a constellation $P$.

  * (O4)

If $e\in D(P)$ and $a\in P$, then there is a maximum $x\in P$ with respect to
the natural quasiorder $\leq$ on $P$, such that $x\leq a$ and $x\circ e$
exists, the co-restriction of $a$ to $e$, denoted $a|e$; and

  * (O5)

for $x,y\in P$ and $e\in D(P)$, if $x\circ y$ exists then $D((x\circ
y)|e)=D(x|(D(y|e))$.

Every inductive constellation is normal. Note that the co-restriction $a|e$ in
(O4) is fully determined (if it exists) by the natural order $\leq$ on the
constellation $P$.

A recent characterisation of the inductive property appearing in [20] is
convenient in what follows.

###### Lemma 2.6

The constellation $(P,\circ,D)$ is inductive if and only if it is normal and
for all $s\in P$ and $e\in D(P)$, there exists $s\cdot e\in D(P)$ such that
for all $t\in P$, $(t\circ s)\circ e$ exists if and only if $t\circ(s\cdot e)$
exists. In that case, the co-restriction $s|e$ is $(s\cdot e)\circ s$ for all
$s\in P$ and $e\in D(P)$.

When a left restriction semigroup $S$ is viewed as a constellation
$(S,\circ,D)$ as above, then the latter is inductive, and for $s,t\in S$,
$s\circ t=st$ whenever the former is defined and $s|e=se$ for all $e\in D(S)$.
Conversely, it was shown in Proposition 4.5 of [8] that an inductive
constellation $P$ can be made into a left restriction semigroup by extending
the partial multiplication to an everywhere-defined one by defining, for all
$s,t\in P$, $s\otimes t:=(s|D(t))\circ t$, which in turn is equal to $(s\cdot
D(t))\circ s)\circ t$, where $s\cdot D(t)$ is as in Lemma 2.6. We call this
the induced left restriction semigroup on $P$. It was shown in [8] that the
categories of inductive constellations (where the morphisms are ordered
radiants as defined in [8]) and left restriction semigroups (where the
morphisms are semigroup homomorphisms respecting $D$) are isomorphic. It is
easily seen that the natural order in a left restriction semigroup is the same
as the natural order when it is viewed as a constellation under this
correspondence.

More generally, in a unary semigroup $S$ with unary operation $d$, one can
define the restricted product $x\circ y:=xy$ only if $xd(y)=x$. In [20], the
unary semigroups $S$ for which $(S,\circ,d)$ is a constellation were
characterised as the class of demigroups, defined in the introduction.

##  3 $E$-demigroups, their left $(d,E)$-completions and when they are
inductive

In this section we formally show that $C^{d}_{E}(S)$ iso a constellation, and
characterise when such constellations are inductive and hence are “left
restriction semigroups in disguise”. This is preparation for a much closer
examination of the two most important cases, namely when $S$ is a left
$E$-monoid or left $E$-monoid with zero. We start with properties of
$C_{E}(S)$ where $S$ is a semigroup and $\emptyset\neq E\subseteq E(S)$, then
extend them to $C^{d}_{E}(S)$.

###### Proposition 3.1

Suppose $S$ is a semigroup with $E$ a non-empty subet of its idempotents.

The partial operation $\circ$ on $C_{E}(S)$ as defined in Section 1 is well-
defined, and $(C_{E}(S),\circ,D)$ is a constellation $P$ in which $D(P)$ is
$\\{(e,e)\mid e\in E\\}$. Moreover in $P$, $(e,s)\leq(f,t)$ under the natural
quasiorder in $P$ if and only if $ef=e$ and $s=et$.

If $S$ is an $E$-demigroup, then $C^{d}_{E}(S)$ is a subconstellation of
$C_{E}(S)$.

Proof. Defining $(e,s)\circ(f,t)=(e,st)$ on $E\times S$ whenever $sf=s$, the
proofs of (C1) and (C2) in Section 2.3 are routine. Next note that for
$(e,s),(f,t)\in C_{E}(S)$, we have $es=s$, $ft=t$, and $sf=s$. Then $est=st$
and so $(e,st)\in C_{E}(S)$. So $\circ$ is well-defined on $C_{E}(S)$ and so
the properties (C1) and (C2) are inherited from $E\times S$.

For $e\in E$, $ee=e$ so $(e,e)\in C_{E}(S)$, and $C_{E}(S)$ is closed under
$D$. To show (C3), we first determine the right identities in $C_{E}(S)$. As
noted above, $(f,f)\in C_{E}(S)$ for all $f\in E$. Now if $(e,s)\circ(f,f)$
exists for some $e,f\in E$ and $s\in S$ then $sf=s$, and so it equals $(e,s)$,
so $(f,f)$ is a right identity. Conversely, if $(f,x)$ is a right identity,
then $(f,f)=(f,f)\circ(f,x)=(f,x)$. So the set of right identities in
$C_{E}(S)$ is the set of elements of the form $(e,e)$ where $e\in E$.

Now for all $(e,s)\in C_{E}(S)$, $(e,e)\circ(e,s)=(e,s)$, and if also
$(f,f)\circ(e,s)=(e,s)$ then $f=e$, so $(f,f)=(e,e)$. So (C3) holds, and
$C_{E}(S)$ is a constellation.

Suppose $(e,s)\leq(f,t)$ under the natural order on $P=C_{E}(S)$. Then

$(e,s)=D((e,s))\circ(f,t)=(e,e)\circ(f,t)=(e,et),$

so $ef=e$ and $s=et$. Conversely, suppose $(e,s),(f,t)\in P$ are such that
$ef=e$ and $et=s$. Then $(e,e)\circ(f,t)$ exists and equals $(e,et)=(e,s)$, so
$(e,s)\leq(f,t)$.

Finally, suppose $S$ is an $E$-demigroup and consider $(e,s),(f,t)\in
C^{d}_{E}(S)$. Then in $C_{E}(S)$, $(e,s)\circ(f,t)=(e,st)$ and indeed
$d(st)=d(sd(t))=d(sd(f))=d(sf)=d(s)=d(e)$, so $(e,st)\in C^{d}_{E}(S)$.
Trivially $(e,e)\in C^{d}_{E}(S)$ for all $e\in E$. So $C^{d}_{E}(S)$ is a
subconstellation of $C_{E}(S)$. $\Box$

We note that a similar though dual construction to $C_{E}(S)$ is used in
Section 3 of [10] to convert a constellation into a category; much earlier, a
similar dual construction was used in Section 9 of [13] to convert an RC-
semigroup satisfying the congruence condition (that is, a right Ehresmann
semigroup) into a category.

In the introduction, we defined left $E$-monoids and left $E$-monoids with
zero as special cases of $E$-demigroups and described how they all arose. We
now justify the claims made there.

###### Proposition 3.2

Suppose $S$ is a monoid with $1\in E\subseteq E(S)$.

  1. 1.

If we define $d(s)=1$ for all $s\in S$, then $S$ is a left $E$-monoid, and
every left $E$-monoid arises in this way.

  2. 2.

If $S$ has zero and is integral, meaning that it has no zero divisors (so
$S\backslash\\{0\\}$ is a subsemigroup), with $0,1\in E\subseteq E(S)$ and we
define $d(0)=0$ with $d(s)\neq 0$ if $s\neq 0$, then $S$ is a left $E$-monoid
with zero. Moreover every left $E$-monoid with zero arises in this way.

Proof. (1) is immediate. For (2), if $S$ is integral, $0,1\in E\subseteq E(S)$
and we define $d$ as above, an easy case analysis verifies the left $E$-monoid
with zero properties. Conversely, if $S$ is a left $E$-monoid with zero, we
must only show that $S$ is integral. But if $st=0$ then $0=d(st)=d(sd(t))$, so
$sd(t)=0$; if $t\neq 0$ then $d(t)=1$ so $s=0$. $\Box$

If $S$ is an $E$-demigroup, the normality of $C^{d}_{E}(S)$ depends only on
the domain elements $D(C_{E}(S))=\\{(e,e)\mid e\in E\\}=D(C^{d}_{E}(S))$. The
condition that $(e,e)\circ(f,f)$ and $(f,f)\circ(e,e)$ are both defined if and
only if $(e,e)=(f,f)$ is equivalent to the condition that $ef=e$ and $fe=f$
imply $e=f$, and so we obtain the following.

###### Proposition 3.3

For an $E$-demigroup $S$, $C^{d}_{E}(S)$ is normal if and only if $E$ is right
pre-reduced.

The third main example of an $E$-demigroup arises from any demigroup $S$,
where we set $E=d(S)=\\{d(s)\mid s\in S\\}$. The membership condition
$(e,s)\in C^{d}_{E}(S)$ then becomes $es=s$ and $d(e)=d(s)$, that is,
$e=d(s)$, so then $C^{d}_{E}(S)=\\{(d(s),s)\mid s\in S\\}$, and
$(d(s),s)\circ(d(t),t)$ exists if and only if $sd(t)=s$, in which case it
equals $(d(s),st)=(d(st),st)$. This is evidently isomorphic to the
constellation product $\circ$ obtained from the demigroup $S$ as in [20]: that
$s\circ t=st$ should exist if and only if $sd(t)=s$.

###### Proposition 3.4

Suppose $S$ is an $E$-demigroup, with $E,E^{\prime}$ two right-equivalent
right pre-reduced subsets of $E(S)$ (with for all $e\in E$,
$e\sim_{r}e^{\prime}\in E^{\prime}$). Suppose $d(S)\subseteq E^{\prime}$ and
$d(e)=d(e^{\prime})$ for all $e\in E$. Then $S$ is an $E^{\prime}$-demigroup
with respect to the same demigroup operation $d$, and the normal
constellations $P=C^{d}_{E}(S)$ and $P^{\prime}=C^{d}_{E^{\prime}}(S)$ are
isomorphic. In particular, if $S$ is an $E$-monoid, then $C_{E}(S)\cong
C_{E^{\prime}}(S)$, and if $S$ is an $E$-monoid with zero, then
$C^{0}_{E}(S)\cong C^{0}_{E^{\prime}}(S)$

Proof. To show that $S$ is an $E^{\prime}$-demigroup, note that for all
$e^{\prime}\in E^{\prime}$,
$e^{\prime}d(e^{\prime})=e^{\prime}ed(e)=e^{\prime}e=e^{\prime}$. Now define
$\rho:P\rightarrow P^{\prime}$ by setting
$\rho((e,s))=(e^{\prime},e^{\prime}s)$. This is well-defined since
$e^{\prime}(e^{\prime}s)=e^{\prime}s$, and
$d(e^{\prime}s)=d(e^{\prime}d(s))=d(e^{\prime}d(e))=d(e^{\prime}e)=d(e^{\prime})$.
Evidently, $\rho$ has inverse $\rho^{\prime}:P^{\prime}\rightarrow P$ given by
$\rho^{\prime}((e^{\prime},s))=(e,es)$, and each is a radiant, hence an
isomorphism, as follows using Lemma 2.2 several times. For if
$(e,s)\circ(f,t)$ exists in $P$ then $sf=s$, so $sf^{\prime}=s$ and so
$\rho((e,s))\circ\rho((f,t))=(e^{\prime},e^{\prime}s)\circ(f^{\prime},f^{\prime}t)$
exists in $P^{\prime}$, and equals
$(e^{\prime},e^{\prime}sf^{\prime}t)=(e^{\prime},e^{\prime}st)=\rho((e,st))=\rho((e,s)\circ(f,t))$.
Moreover,
$\rho(D((e,s)))=\rho((e,e))=(e^{\prime},e^{\prime})=D((e^{\prime},e^{\prime}s))=D(\rho((e,s)))$.
$\Box$

In [15], Lawson showed that it is possible to extend the multiplication in
certain types of small categories so that it is defined universally, giving a
certain class of bi-unary semigroups: these categories he called Ehresmann.
Lawson was able to establish an isomorphism between such small categories and
what he dubbed Ehresmann semigroups, referred to in Section 2.2, which
specialised to an ismorphism between inductive categories and two-sided
restiction semigroups. Natural examples of Ehresmann semigroups include
algebras of binary relations under composition, domain and range.

From the point of view of semigroup theory, an interesting question therefore
arises: for a semigroup $S$ and set of idempotents $E$, when is $Cat_{E}(S)$
inductive? For in such cases, it can be turned into an Ehresmann semigroup. In
fact, this problem does not seem to have an easy answer. The elements of an
inductive category are ordered in two ways, and there is no obvious way to
impose a partial order on $Cat_{E}(S)$.

However, for an $E$-demigroup $S$, $C^{d}_{E}(S)$ is a constellation, and
hence has its natural quasiorder. So it is possible to characterise those
choices of $E$-demigroup $S$ for which $C^{d}_{E}(S)$ is an inductive
constellation.

###### Proposition 3.5

Suppose $S$ is an $E$-demigroup. If $P=C^{d}_{E}(S)$ is inductive, then $E$ is
right pre-reduced, and

  1. (I1)

for all $t\in S$ and $e\in E$, there is $t\cdot e\in E$ such that for all
$s\in S$: ($ste=st$ and $sd(t)=s$) if and only if $s(t\cdot e)=s$, and

  2. (I2)

$(E,\leq_{r})$ is a meet-semilattice, and for all $s\in S$ and $e,f\in E$,
$se=sf=s\Rightarrow s(e\wedge f)=s$.

Proof. Now $P$ is normal so $E$ is right pre-reduced by Proposition 3.3.

Pick $t\in S$ and $e\in E$. Then $(d(t),t)\in P$ since $d(d(t))=d(t)$. By
Lemma 2.6, there is $(d(t),t)\cdot(e,e)\in D(P)$, which we denote by $(t\cdot
e,t\cdot e)$ for some $t\cdot e\in E$, such that for all $s\in S$,
$(d(s),s)\in P$, and so $((d(s),s)\circ(d(t),t))\circ(e,e)$ exists if and only
if $(d(s),s)\circ(t\cdot e,t\cdot e)$ exists, which is to say that $sd(t)=s$
and $ste=st$ if and only if $s(t\cdot e)=s$.

For $e,f\in E$, it follows from Proposition 3.1 that $(e,e)\leq(f,f)$ in
$D(C_{E}(S))$ if and only if $ef=e$ in $E$, that is, $e\leq_{r}f$ in $E$. So
as a poset under $\leq_{r}$, $E$ is isomorphic to $D(C_{E}(S))=D(P)$ under its
natural order. In particular, $(E,\leq_{r})$ is a meet-semilattice, and
working in the induced left restriction semigroup on $P$,
$(e,e)(f,f)=(e,e)\wedge(f,f)=(e\wedge f,e\wedge f)$ where “$\wedge$” is
interpreted appropriately in each case.

Next suppose $se=s=sf$ for $s\in S$ and $e,f\in E$. Then

$(d(s),s)\circ(e,e)=(d(s),s)=(d(s),s)\circ(f,f),$

so in the induced left restriction semigroup on $P$,

$(d(s),s)=(d(s),s)(e,e)=(d(s),s)(f,f)=(d(s),s)(e,e)(f,f)=(d(s),s)(e\wedge
f,e\wedge f),$

so $(d(s),s)\circ(e\wedge f,e\wedge f)=(d(s),s)$, and so $s(e\wedge f)=s$.
$\Box$

We use the above result to define the notion of an inductive $E$-demigroup.

###### Definition 3.6

Suppose $S$ is an $E$-demigroup. We say $S$ is inductive if $E$ is right pre-
reduced and there is a function $\cdot:S\times E\rightarrow E$ satisfying (I1)
and (I2) in Proposition 3.5 above.

Proposition 3.5 may be rephrased by saying that if $S$ is an $E$-demigroup and
$C^{d}_{E}(S)$ is inductive then $S$ is inductive. We now prove its converse.

###### Proposition 3.7

If $S$ is an inductive $E$-demigroup, then $C^{d}_{E}(S)$ is an inductive
constellation in which

$(f,s)|(e,e)=(f\wedge(s\cdot e),(f\wedge(s\cdot e))s).$

Proof. Pick $(f,s),(e,e)\in C^{d}_{E}(S)$ and let $h=f\wedge(s\cdot e)$. Then
for all $(g,t)\in C^{d}_{E}(S)$, the following are equivalent:

  * •

the constellation product $((g,t)\circ(f,s))\circ(e,e)$ exists;

  * •

$tf=t$ and $tse=ts$;

  * •

$tf=t$, $td(s)=t$ and $tse=ts$;

  * •

$tf=t$ and $t(s\cdot e)=t$;

  * •

$t(f\wedge(s\cdot e))=t$;

  * •

the constellation product $(g,t)\circ(h,h)$ exists.

The second line above implies the third because, given that $d(f)=d(s)$ (since
$(f,s)\in C^{d}_{E}(S)$), if $tf=t$ then $td(s)=tfd(s)=tfd(f)=tf=t$. So by
Lemma 2.6, $C_{E}(S)$ is inductive, and
$(f,s)|(e,e)=D((f,s)|(e,e))\circ(f,s)=(h,h)\circ(f,s)=(h,hs)$. $\Box$

###### Corollary 3.8

Let $S$ be an inductive $E$-demigroup, and let $P=C^{d}_{E}(S)$. Then $P$ can
be made into a left restriction semigroup by defining
$(e,s)(f,t)=(e\wedge(s\cdot f),(e\wedge(s\cdot f))st)$ for all $(e,s),(f,t)\in
P$, and $D((e,s))=(e,e)$. Moreover $(e,s)\leq(f,t)$ under the natural order if
and only if $e\leq_{r}f$ and $s=et$.

Proof. As already noted, multiplication in the induced left restriction
semigroup is given by $(e,s)(f,t)=((e,s)|(f,f))\circ(f,t)=(e\wedge(s\cdot
f),(e\wedge(s\cdot f))s)\circ(f,t)=(e\wedge(s\cdot f),(e\wedge(s\cdot f))st)$.
By Proposition 3.1, the natural order is as stated. $\Box$

###### Definition 3.9

Let $S$ be an inductive left $E$-demigroup. Denote by $Rest_{d}(E,S)$ the
induced left restriction semigroup structure on $C^{d}_{E}(S)$ as in Corollary
3.8.

Note that for an inductive $E$-demigroup $S$, $Rest_{d}(E,S)$ has the same
underlying set as $C^{d}_{E}(S)$, the unary domain operation is the same in
both, and multiplication on $Rest_{d}(E,S)$ agrees with that on $C^{d}_{E}(S)$
whenever the latter is defined. Moreover the extension of the partial
multiplication on $C^{d}_{E}(S)$ to that on $Rest_{d}(E,S)$ is entirely
determined by the structure of $C^{d}_{E}(S)$ as a constellation. By
Proposition 3.4, we therefore obtain the following.

###### Corollary 3.10

If $S$ is an inductive $E$-demigroup, and $E^{\prime}\sim_{r}E$ with $E\ni
e\sim_{r}e^{\prime}\in E^{\prime}$, and $d(e^{\prime})=d(e)$ for all $e\in E$,
then $S$ is also an inductive $E^{\prime}$-demigroup. Moreover,
$Rest_{d}(E,S)\cong Rest_{d}(E^{\prime},S)$.

In the case of a demigroup $S$ viewed as a $d(S)$-demigroup, the definition of
inductive agrees with that of an inductive demigroup as in [20], and we
recover Theorem $5.1$ there as a special case of the last two results by
identifying $(d(s),s)\in Rest_{d}(E,S)$ with $s\in S$. But here, the most
important special cases arise from left $E$-monoids and left $E$-monoids with
zero.

Viewing a left $E$-monoid $S$ as an $E$-demigroup in the usual way (by setting
$d(s)=1$ for all $s\in S$), the following is immediate from Propositions 3.5
and 3.7.

###### Corollary 3.11

Let $S$ be a left $E$-monoid viewed as an $E$-demigroup as in Proposition 3.2.
Then $S$ is inductive if and only if $E$ is right pre-reduced, and the
following hold:

  1. (I1′)

for all $t\in S$ and $e\in E$, there is $t\cdot e\in E$ such that for all
$s\in S$, $ste=st$ if and only if $s(t\cdot e)=s$, and

  2. (I2′)

$(E,\leq_{r})$ is a meet-semilattice, and for all $s\in S$ and $e,f\in E$,
$se=sf=s\Rightarrow s(e\wedge f)=s$.

Note that (I1′) simply asserts that $(te,t)$ has a (necessarily unique) left
equalizer in $E$.

###### Proposition 3.12

Let $S$ be a left $E$-monoid with zero. Then $S$ is inductive when viewed as
an $E$-demigroup as in Proposition 3.2 if and only if it is inductive when
viewed as a left $E$-monoid, and multiplication in the induced left
restriction semigroup of $C^{0}_{E}(S)$ agrees with that in $C_{E}(S)$.

Proof. Suppose $S$ is inductive when viewed as an $E$-demigroup as in
Proposition 3.2. Pick $t\neq 0$ and $e\in E$; then $d(t)=1$, and the first
condition in Proposition 3.5 asserts that $(te,t)$ has an equalizer $t\cdot e$
in $E$. Now let $t=0$ so that $d(t)=0$, and then we see that $(t,te)=(0,0)$
have equalizer $1\in E$. So the first, and trivially also the second,
conditions for inductive left $E$-monoids are satisfied.

Conversely, suppose $S$ is inductive when viewed as a left $E$-monoid. View it
as an $E$-demigroup as before. Again, for $t\neq 0$, $d(t)=1$ and the first
condition in Corollary 3.11 is the same as the first in Proposition 3.5. For
$t=0$, $d(0)=0$ and then the first condition in Proposition 3.5 becomes $0=0$
and $s0=s$ if and only if $s(0\cdot e)=s$, which is true for all $s$ if
$0\cdot e$ is chosen to be $0$. So $S$ is inductive.

In the above, note that the choice of equalizer of $(t,te)$ is the same in
either way of viewing $S$, providing $t\neq 0$. Hence in $C^{0}_{E}(S)$, the
product $(e,s)(f,t)=(e\wedge(s\cdot f),(e\wedge(s\cdot f))st)$ is the same
under either interpretation of $S$ providing $s\neq 0$. But if $s=0$ then
$e=0$ and so we obtain $(0,0)$ under either interpretation. $\Box$

This shows that the notion of inductive is the same in left $E$-monoids and
left $E$-monoids with zero. Next we specialise Definition 3.9 to our two
important special cases.

###### Definition 3.13

Let $S$ be an inductive left $E$-monoid. Viewing $S$ as an $E$-demigroup as in
Proposition 3.2, write $Rest(E,S)$ rather than $Rest_{d}(E,S)$, the semigroup
left $E$-completion of $S$. If $S$ is integral, viewing it as an $E$-demigroup
as in Proposition 3.2, write $Rest_{0}(E,S)$ rather than $Rest_{d}(E,S)$, the
zero-reduced semigroup left $E$-completion of $S$. If $S$ is an inductive
right $E$-monoid, denote by $RRest(S,E)$ and $RRest_{0}(S,E)$ the obvious
dually defined right restriction monoids.

##  4 Characterising left restriction monoids that are semigroup left
$E$-completions

Building on the results of Section 3, we may ask which left restriction
semigroups $M$ arise as $Rest_{d}(E,S)$ for some inductive $E$-demigroup $S$.
But the answer is trivial: all of them. Given a left restriction semigroup
$M$, let $S=M$, $d=D$, and then $Rest_{d}(d(S),S)$ is isomorphic to the
demonization $S_{d}$ of $S$ constructed from $S$ using the approach of [20],
as noted previously, which in turn is isomorphic to $S$ since it was a left
restriction semigroup already, and so $M\cong Rest_{d}(d(S),S)$.

The situation is more complex and interesting if we take $S$ to be a left
$E$-monoid or a left $E$-monoid with zero and extend it via $Rest(E,S)$ or
$Rest_{0}(E,S)$. Moreover several important examples have this form, as we see
in Section 7.

Recall that if $S$ is a left restriction monoid, $S_{1}$ is the submonoid
$\\{s\in S\mid D(s)=1\\}$.

###### Definition 4.1

The left restriction monoid $S$ has enough large idempotents if for all non-
zero $e\in D(S)$, there exists $f\in E(S_{1})$ such that $e\sim_{r}f$. It has
precisely enough large idempotents if it has enough large idempotents and for
all $f\in E(S_{1})$ there is $e\in D(S)$ such that $e\sim_{r}f$. Let
$E\subseteq E(S)$ consist of exactly one $e^{\prime}\in E(S_{1})$ for each
non-zero $e\in D(S)$ such that $e^{\prime}\sim_{r}e$, as well as $0\in D(S)$
if $S$ has a zero; then we say $E$ is a set of enough large idempotents.

###### Proposition 4.2

Suppose $S$ is an inductive left $E$-monoid. Then $M=Rest(E,S)$ has enough
large idempotents. If $S$ is integral then $M=Rest_{0}(E,S)$ has enough large
idempotents.

Proof. For $e\in E$, note that $e\cdot e=1$. A typical non-zero element of
$D(M)$ is $(e,e)$ where $e\neq 0$. Then $(1,e)\in M$, and
$(1,e)(1,e)=(1,e)\circ(1,e)=(1,ee)=(1,e)$, so $(1,e)\in E(M_{1})$, similarly
$(e,e)(1,e)=(e,ee)=(e,e)$, and $(1,e)(e,e)=(1,ee)=(1,e)$, so
$(e,e)\sim_{r}(1,e)$. So $M$ has enough large idempotents. $\Box$

Note that if $S$ is an inductive left $E$-monoid, then in $M=Rest(E,S)$,
$M_{1}\cong S$ as monoids, under the mapping $(1,s)\mapsto s$ for all $s\in
S$, while if $S$ is integral, then in $M=Rest_{0}(E,S)$,
$M_{1}\cup\\{0\\}\cong S$ under the mapping $(1,s)\mapsto s$ for all non-zero
$s\in S$ with $(0,0)\mapsto 0$.

Conversely, we have the following.

###### Theorem 4.3

Let $S$ be a left restriction monoid with enough large idempotents, for each
non-zero $e\in D(S)$, let $e^{\prime}\in F$ be such that
$e\sim_{r}e^{\prime}$, and if $S$ has zero, let $0^{\prime}=0$. Let
$E=\\{e^{\prime}\mid e\in D(S)\\}$. If $S$ does not have zero, let
$S^{\prime}=S_{1}$, while if $S$ has zero, let $S^{\prime}=S_{1}\cup\\{0\\}$.
Then $S^{\prime}$ is an inductive left $E$-monoid, integral if $S$ has zero,
in which

  * •

if $t\in S^{\prime}$ and $t\neq 0$ then $t\cdot e^{\prime}=D(te)^{\prime}$ for
all $e^{\prime}\in E$, and

  * •

if $S$ has zero then $0\cdot g=1$ for all $g\in E$,

and $S\cong Rest_{0}(E,S^{\prime})$ if $S$ has zero, with $S\cong
Rest(E,S^{\prime})$ otherwise.

Proof. First note that $E$ is right pre-reduced, as if
$e^{\prime}\sim_{r}f^{\prime}$ then $e\sim_{r}f$ and so $e=f$, so
$e^{\prime}=f^{\prime}$. Moreover, if $e\sim_{r}1$ for some $e\in E$, then
$e=1$, so $1\in E$, which corresponds to $1\in D(S)$. So $S^{\prime}$ is an
$E$-monoid. Note also that $E$ is a meet-semilattice under $\leq_{r}$ since
$E$ and $D(S)$ are isomorphic as posets under $\leq_{r}$ as discussed prior to
Lemma 2.2.

We first show that $S$ satisfies (I1′) in Proposition 3.11. If $S$ has zero
and $t=0$, then we must show that for any $g\in E$, $s0g=s0$ if and only if
$s1=s$, which is trivially true. So suppose $t\in S^{\prime}$ is non-zero. For
$f^{\prime}\in E$, we want to show that for all $s\in S^{\prime}$,
$stf^{\prime}=st$ if and only if $s=sD(tf)^{\prime}$. By the first part of
Lemma 2.2, it is necessary and sufficient to show that $stf=st$ if and only if
$sD(tf)=s$. Now if $stf=st$ then $sD(tf)=D(stf)s=D(st)s=D(sD(t))s=s$ since
$D(t)=1$, while if $sD(tf)=s$ then $stf=sD(tf)t=st$.

Now we show $S^{\prime}$ satisfies (I2′) in Proposition 3.11. We must show
that for $s\in S^{\prime}$ and $e^{\prime},f^{\prime}\in E$,
$s=se^{\prime}=sf^{\prime}$ imply $s=s(e^{\prime}\wedge
f^{\prime})=s(ef)^{\prime}$; again by the first part of Lemma 2.2, it is
necessary and sufficient to show that $se=sf=s$ implies $sef=s$, for all
$s,t\in S^{\prime}$ and $e,f\in D(S)$. But this is almost immediate.

If $S$ has zero and $s,t\in S_{1}$ then $D(st)=D(sD(t))=D(s)=1$ by the left
congruence property, so $st\neq 0$ and so $S^{\prime}$ is integral.

Let $T=Rest_{0}(E,S^{\prime})$ if $S$ has zero, and $T=Rest(E,S^{\prime})$
otherwise. We claim that the map $\theta:T\rightarrow S$ given by
$\theta((e^{\prime},s))=es$ if $e^{\prime}\neq 0$, with $\theta((0,0))=0$ if
$S$ has zero, is an isomorphism.

First, suppose $(e^{\prime},s),(f^{\prime},t)\in T$. If $M$ has zero and
$(e^{\prime},s)\neq(0,0)$, then $\theta((e^{\prime},s))=es\neq 0$ since $S$ is
integral, so $\theta((e^{\prime},s))\neq\theta((0,0))$. Suppose neither
$(e^{\prime},s)$ nor $(f^{\prime},t)$ is $(0,0)$. If
$\theta((e^{\prime},s))=\theta((f^{\prime},t))$ then $es=ft$, and by the left
congruence property, $D(es)=D(eD(s))=D(e)=e$, and similarly $D(ft)=f$, so
$e=f$, and so $es=et$, so $s=e^{\prime}s=e^{\prime}t=t$ by the second part of
part of Lemma 2.2. So $(e,s)=(f,t)$. Moreover neither $es$ nor $ft$ is zero.
So $\theta$ is injective.

Now pick $s\in S$, $s\neq 0$. Let $t=D(s)^{\prime}s$, so
$D(t)=D(D(s)^{\prime}s)=D(D(s)^{\prime}D(s))=D(D(s)^{\prime})=1$, so $t\in
S_{1}$, and $D(s)t=D(s)D(s)^{\prime}s=D(s)s=s$, so $s\leq t$ in $S$. Then
$\theta((D(s)^{\prime},t))=D(s)t=s$. Furthermore, if $S$ has a zero then
$\theta((0,0))=0$. So $\theta$ is surjective, and is therefore a bijection.

Now suppose $(e^{\prime},s),(f^{\prime},t)\in T$. If neither is $(0,0)$, then
$\theta((e^{\prime},s)(f^{\prime},t))=\theta((e^{\prime}\wedge(s\cdot
f^{\prime}),(e^{\prime}\wedge(s\cdot
f^{\prime}))st)=eD(sf)st=esft=\theta((e^{\prime},s))\theta((f^{\prime},t))$.
If $S$ has zero, then because $\theta((0,0))=0$, it is immediate that
$\theta((0,0)(f,t))=\theta((e,s)(0,0))=\theta((0,0))=0=\theta((e,s))\theta((0,0))=\theta((0,0))\theta((f,t))$.
So $\theta$ is a semigroup homomorphism.

Finally, we must show $D$ is respected by $\theta$. But if $e^{\prime}\neq 0$,
then
$\theta(D((e^{\prime},s)))=\theta((e^{\prime},e^{\prime}))=ee^{\prime}=e$,
while $D(\theta((e^{\prime},s)))=D(es)=D(eD(s))=D(e1)=e$ also, and if $S$ has
zero, then $\theta(D((0,0))=\theta((0,0))=0=D(0)=D(\theta((0,0)))$.

So $\theta$ is an isomorphism and so $S\cong T$ as left restriction monoids.
$\Box$

###### Proposition 4.4

If $S$ is an inductive left $E$-monoid, then $E$ is maximal right pre-reduced
if and only if $Rest(E,S)$ has precisely enough large idempotents (if and only
if $Rest_{0}(E,S)$ has precisely enough large idempotents if $S$ is integral).

Proof. Suppose $S$ is an inductive left $E$-monoid.

If $E$ is maximal right pre-reduced, and $(1,s)\in E(Rest(E,S)_{1})$
($=E(Rest_{0}(E,S)_{1})$ if $S$ is integral), then $s^{2}=s$ in $S$ and so
there is $f\in E$ such that $fs=f$ and $sf=s$, and so
$(f,f)(1,s)=(f,fs)=(f,f)$ and $(1,s)(f,f)=(s\cdot f,(s\cdot
f)sf)=(1,sf)=(1,s)$, so $Rest(E,S)$ (and $Rest_{0}(E,S)$ if $S$ is integral)
has precisely enough large idempotents.

Conversely, if $Rest(E,S)$ (or $Rest_{0}(E,S)$ if $S$ is integral) has
precisely enough large idempotents, then for $(1,s)\in
E(Rest(E,S)_{1})(=E(Rest_{0}(E,S)_{1})$ if $S$ is integral), $s\in E(S)$ and
there exists (non-zero) $(e,e)\in D(Rest(E,S))$ such that $(e,e)(1,s)=(e,e)$
and $(1,s)(e,e)=(1,s)$, so $(e,es)=(e,e)$ and $(s\cdot e,(s\cdot e)se)=(1,s)$,
so $es=e$, and $s\cdot e=1$ so $se=s$, and so $s\sim_{r}e$, showing that $E$
is maximal right pre-reduced. $\Box$

###### Corollary 4.5

If a left restriction monoid $S$ has precisely enough large idempotents, then
it is isomorphic to $Rest_{0}(E,S^{\prime})$ if $S$ has zero or to
$Rest(E,S^{\prime})$ if not, where $E$ and $S^{\prime}$ are as in Theorem 4.3
and $E$ is maximal right pre-reduced in $E(S)$.

##  5 Inductive left $E$-monoids in more detail

Their signficance established, in this section we consider inductive left
$E$-monoids for their own sake. We show how in every monoid there is a single
largest (modulo $\sim_{r}$) choice of $E$ with respect to which it is an
inductive left $E$-monoid. But first, it proves useful to consider actions
satisfying only the first condition of the inductive property for left
$E$-monoids.

###### Definition 5.1

Suppose $S$ is a left $E$-monoid. Then $S$ is modal if $E$ is right pre-
reduced and (I1′) holds, that is, for all $t\in S$, $e\in E$, $(te,t)$ have a
(necessarily unique) left equalizer in $E$, denoted by $t\cdot e$. When
extended to all of $S\times E$, we call the induced mapping $(t,e)\mapsto
t\cdot e$ the left $E$-modal operation on $S$.

Note that the definition could instead have specified that for all $t\in S$,
$e\in E$, $(te,t)$ have a unique left equalizer in $E$, and then the right
pre-reduced property would have followed: for if $e\sim_{r}f$ for some $e,f\in
E$, then $Eq(1,1e)=Eq(1,e)=Se$, so $e$ equalizes $(1,1e)$, and since
$e\sim_{r}f$, so does $f$ by Proposition 2.5, and so $e=f$ by uniqueness.

###### Proposition 5.2

If $S$ is a modal left $E$-monoid with $s\in S$ and $e\in E$, then for all
$f\in E$, $f\in Eq(se,s)$ if and only if $f\leq_{r}s\cdot e$.

Proof. The following are equivalent: $f\leq_{r}s\cdot e$; $f\in S(s\cdot e)$;
$f\in Eq(s,se)$. $\Box$

It follows that in a modal left $E$-monoid $S$, $s\cdot e$ is the largest
$f\in E$ (with respect to $\leq_{r}$) such that $fs=fse$.

###### Example 5.3

A small non-inductive yet modal left $E$-monoid.

Let $S=\\{0,e,f,1\\}$ be the band in which $0$ is a zero, $1$ is an identity,
$ef=fe=0$, and $E=\\{e,f,1\\}$. Then $S$ is easily verified to be a modal left
$E$-monoid, and $e,f\leq_{r}1$ but $e,f$ have no lower bound in $E$ under
$\leq_{r}$.

We next give a description of left $E$-modal operations which makes clear that
they are indeed “actions” in the usual sense.

###### Proposition 5.4

Suppose $S$ is a left $E$-monoid, and there is a function $\cdot:S\times
E\rightarrow E$. Then $S$ is modal with $\cdot$ the left $E$-modal operation
if and only if $E$ is right pre-reduced and the following laws hold. For all
$e,f\in E$ and $s,t\in S$:

  1. (M1)

$e\cdot e=1$,

  2. (M2)

$s\cdot 1=1$,

  3. (M3)

$(s\cdot e)s=(s\cdot e)se$,

  4. (M4)

$(st)\cdot e=s\cdot(t\cdot e)$.

$S$ is an inductive left $E$-monoid if and only if the above laws hold and $E$
is a meet-semilattice with respect to $\leq_{r}$ such that the following law
holds:

  1. (M5)

$s\cdot(e\wedge f)=(s\cdot e)\wedge(s\cdot f)$, where $\wedge$ is meet in
$(E,\leq_{r})$.

Proof. Suppose $S$ is modal. Then $E$ is right pre-reduced, and the first
three laws are immediate. For the fourth, letting $s,t\in S$ and $e\in E$, and
letting $f=(st)\cdot e$ and $g=s\cdot(t\cdot e)$, we see that $fst=fste$, so
$fs(t\cdot e)=fs$, and so $f\leq_{r}s\cdot(t\cdot e)=g$ by Proposition 5.2.
Conversely, $gs=gs(t\cdot e)$, so $gst=gs(t\cdot e)t=gs(t\cdot e)te=gste$, and
so $g\leq_{r}(st)\cdot e=f$ using the same result. Because $E$ is right pre-
reduced, $f=g$. So (M4) is now established.

Conversely, suppose (M1)–(M4) all hold and $E$ is right pre-reduced. Suppose
$ste=st$ for some $s,t\in S$ and $e\in E$. Then using (M1), (M2) and (M4),

$s\cdot(t\cdot e)=(st)\cdot e=(ste)\cdot e=(st)\cdot(e\cdot e)=(st)\cdot 1=1,$

so by (M3),

$s(t\cdot e)=1s(t\cdot e)=(s\cdot(t\cdot e))s(t\cdot e)=(s\cdot(t\cdot
e))s=s.$

Conversely, if $s(t\cdot e)=s$ then by the third law, $ste=s(t\cdot
e)te=s(t\cdot e)t=st$. Hence $Eq(te,t)=S(t\cdot e)$ and so $S$ is modal.

Now suppose $S$ is an inductive left $E$-monoid. Note that if $e,f\in E$ with
$e\leq_{r}f$, then $e=ef$, so $(s\cdot e)sf=(s\cdot e)sef=(s\cdot e)se=(s\cdot
e)s$, so $s\cdot e\leq_{r}s\cdot f$ by Proposition 5.2. Hence because $e\wedge
f\leq_{r}e,f$, $s\cdot(e\wedge f)\leq_{r}(s\cdot e)\wedge(s\cdot f)$.
Conversely, suppose $g\leq_{r}s\cdot e,g\leq_{r}s\cdot f$. Then $gse=g(s\cdot
e)se=g(s\cdot e)s=gs$ and similarly $gsf=gs$, so $gs(e\wedge f)=gs$, and so
$g\leq_{r}s\cdot(e\wedge f)$. So (M5) holds.

Conversely, suppose $E$ is a meet semilattice with respect to $\leq_{r}$, and
(M5) holds. Then $\leq_{r}$ is a partial order and so $E$ is right pre-
reduced. Moreover, if $sf=s=sg$ for some $s\in S$ and $f,g\in E$, then $s\cdot
f=(sf)\cdot f=s\cdot(f\cdot f)=s\cdot 1=1$ and similarly $s\cdot g=1$, so
$s\cdot(e\wedge f)=(s\cdot e)\wedge(s\cdot f)=1\cdot 1=1$, and so $s(e\wedge
f)=(s\cdot(e\wedge f))s(e\wedge f)=(s\cdot(e\wedge f))s=s$. So $S$ is
inductive. $\Box$

If $S$ is a left $E$-modal monoid, it follows easily that $1\cdot e=e$ for all
$e\in E$, so all the conditions in the definition of an action of a monoid $S$
on a semilattice $E$ are satisfied when $S$ is an inductive left $E$-monoid.

Next we show that a left $E$-modal monoid is also left $E^{\prime}$-modal
providing $E^{\prime}\sim_{r}E$, and moreover if the former is inductive then
so is the latter.

###### Proposition 5.5

Let $S$ be a left $E$-monoid, with $E^{\prime}\sim_{r}E$, and suppose that for
each $e\in E$, $e^{\prime}\in E^{\prime}$ is such that $e\sim_{r}e^{\prime}$.
Then $S$ is modal as a left $E^{\prime}$-monoid, with left $E^{\prime}$-modal
operation $s\cdot e^{\prime}=(s\cdot e)^{\prime}$, for all $e\in E$. If $S$ is
inductive as a left $E$-monoid, then it is inductive as a left
$E^{\prime}$-monoid, and $(e\wedge f)^{\prime}=e^{\prime}\wedge f^{\prime}$
for all $e,f\in E$.

Proof. First, $E^{\prime}$ is right pre-reduced. Further, for $s,t\in S$ and
$e^{\prime}\in E^{\prime}$, using the fact that $S$ is left $E$-modal as well
as Lemma 2.2, the following are seen to be equivalent: $tse^{\prime}=ts$;
$tse=ts$; $t(s\cdot e)=t$; $t(s\cdot e)^{\prime}=t$; $t(s\cdot e^{\prime})=t$.
So the left $E^{\prime}$-monoid $S$ is also modal.

If $S$ is an inductive left $E$-monoid then $C_{E}(S)$ is inductive by
Proposition 3.7. But by Proposition 3.4, $C_{E}(S)\cong C_{E^{\prime}}(S)$, so
the latter is inductive, and so by Proposition 3.5, $S$ is an inductive left
$E^{\prime}$-monoid. Since $(E,\leq_{r})$ and $(E^{\prime},\leq_{r})$ are
isomorphic as posets, it follows that $(e\wedge f)^{\prime}=e^{\prime}\wedge
f^{\prime}$ for all $e,f\in E$. $\Box$

Even in a modal left $E$-monoid, where meets of elements of $E$ need not
exist, we obtain the following.

###### Lemma 5.6

Let $S$ be a modal left $E$-monoid, with $e\in E(S)$ and $f\in E$. Then
$(e\cdot f)e$ is a greatest lower bound of $e,f$ in $E(S)$ with respect to
$\leq_{r}$, and if $se=sf=s$ for some $s\in S$, then $s(e\cdot f)e=s$.

Proof. Choose $e\in E(S)$, $f\in E$. Then using Proposition 5.4, $e\cdot
f=(ee)\cdot f=e\cdot(e\cdot f)$, so

$(e\cdot f)e=(e\cdot(e\cdot f))ee=(e\cdot(e\cdot f))e(e\cdot f)e=(e\cdot
f)e(e\cdot f)e,$

and so $(e\cdot f)e\in E(S)$. If $s\in S$ is such that $se=sf=s$, then
$sef=se$, so $s(e\cdot f)=s$, and so $s(e\cdot f)e=se=s$.

Finally, $(e\cdot f)e=(e\cdot f)ef$ and so $(e\cdot f)e\leq_{r}e,f$ in $E(S)$.
If $g\leq_{r}e,f$ for some $g\in E(S)$, then $ge=g=gf$, so letting $s=g$ in
what was just shown gives $g(e\cdot f)e=g$, and so $g\leq_{r}(e\cdot f)e$.
$\Box$

This last result ensures that the meet of elements of $E$ in an inductive left
$E$-monoid admits a description “modulo $\sim_{r}$”. But more can be said.

###### Proposition 5.7

Let $S$ be a modal left $E$-monoid. Then it is inductive if and only if for
all $e,f\in E$, $(e\cdot f)e\sim_{r}g$ for some $g\in E$, in which case
$e\wedge f=g$. In this case, $e\wedge f=e\wedge(e\cdot f)$. If $S$ is
inductive and $E$ is right reduced, then $e\wedge f=(e\cdot f)e$.

Proof. Suppose that for all $e,f\in E$, the idempotent $(e\cdot f)e\sim_{r}g$
for some $g\in E$. Now $(e\cdot f)e$ is a greatest lower bound within $E(S)$
of $e,f\in E$ by Lemma 5.6. Hence $g$ must be their greatest lower bound in
$E$. If $se=s=sf$ for some $s\in S$, then by Lemma 5.6, $s(e\cdot f)e=s$, and
so by the first part of Lemma 2.2, $sg=s$ as well. Hence $S$ is inductive.

Conversely, suppose $S$ is inductive. By Lemma 5.6, $(e\cdot f)e$ is a
greatest lower bound of $e,f$ in $E(S)$, so $e\wedge f\leq_{r}(e\cdot f)e$.
Conversely, $(e\cdot f)ee=(e\cdot f)e$ and $(e\cdot f)ef=(e\cdot f)e$, so
$((e\cdot f)e)(e\wedge f)=(e\cdot f)e$, so $(e\cdot f)e\leq_{r}e\wedge f$. So
$e\wedge f\sim_{r}(e\cdot f)e$.

Again, if $S$ is inductive, then, for $e,f\in E$, working in $Rest(E,S)$ we
have $(e\wedge f,e\wedge f)=(e,e)(f,f)=(e\wedge(e\cdot f),e\wedge(e\cdot f))$,
so $e\wedge f=e\wedge(e\cdot f)$.

Suppose $E$ is right reduced. Then $\leq_{r}$ is the natural order $\leq$ on
$E$. Hence for all $e,f\in E$, $(e\wedge f)ef=(e\wedge f)e$, so $e\wedge f\leq
e\cdot f$, and so because $e\wedge f\leq e$ and $(e\cdot f)e\sim_{r}e\wedge
f$, we have

$(e\cdot f)e=(e\cdot f)e(e\wedge f)=(e\cdot f)(e\wedge f)=e\wedge f,$

as claimed. $\Box$

###### Definition 5.8

The modal left $E$-monoid has definable meets if $(e\cdot f)e\in E$ for all
$e,f\in E$.

From the previous result, a modal left $E$-monoid with definable meets is
inductive, with meet in $E$ given by $e\wedge f=(e\cdot f)e$ for all $e,f\in
E$; moreover any modal left $E$-monoid in which $E$ is right reduced has
definable meets.

Another way to think about modal left $E$-monoids is in terms of arbitrary
sets of idempotents.

###### Definition 5.9

Let $S$ be a monoid with $1\in E\subseteq E(S)$. We say $S$ is (left)
$E$-protomodal if for every $e\in E$, and $s\in S$, $Eq(s,se)$ is non-empty
and generated as a left ideal by a member of $E$. If $E=E(S)$, we say $S$ is
protomodal.

So if $E$ is right pre-reduced, then “left $E$-protomodal = left $E$-modal”.

###### Definition 5.10

Let $S$ be a monoid with $1\in E\subseteq E^{\prime}\subseteq E(S)$. We say
$E$ is maximal right pre-reduced in $E^{\prime}$ if $E$ is right pre-reduced
and every element of $E^{\prime}$ is related by $\sim_{r}$ to a (necessarily
unique) member of $E$.

If $E^{\prime}=E(S)$ in the above, then we recover the definition of $E$ being
maximal right pre-reduced. Evidently if $F,G$ are maximal right pre-reduced in
$E\subseteq E(S)$, then $F\sim_{r}G$.

Not surprisingly, $E$-protomodal monoids are closely related to left $E$-modal
monoids.

###### Proposition 5.11

Let $S$ be a monoid with $1\in F\subseteq E(S)$, and suppose $E$ is right pre-
reduced in $F$. Then $1\in E$, and $S$ is $F$-protomodal if and only if $S$ is
a modal left $E$-monoid. If also $S$ is integral and $0\in F$, then $0\in E$
and $S$ is $F$-protomodal if and only if $S$ is a modal left $E$-monoid with
zero.

Proof. Let $S,F$ and $E$ be as in the proposition statement.

Now $e\sim_{r}1$ for some $e\in E$, so $1=1e=e$, and so $1\in E$. If $S$ is
integral and $0\in F$. then $f\sim_{r}0$ for some $f\in E$, so $f=f0=0$, and
so $0\in E$.

Suppose $S$ is $F$-protomodal. Pick $e\in E\subseteq F$. Then for $s\in S$,
$Eq(s,se)$ is generated by some $f\in F$, hence by some $f^{\prime}\in E$ with
$f\sim_{r}f^{\prime}$ by Proposition 2.5. Because $E$ is right pre-reduced,
$S$ is a modal left $E$-monoid. If $S$ is integral and $0\in F$, then as above
$0\in E$ and so $S$ is a left $E$-monoid with zero, hence a modal one.

Conversely, suppose $S$ is a modal left $E$-monoid (with or without zero). For
$s\in S$ and $e^{\prime}\in F$, there is $e\in E$ such that
$e\sim_{r}e^{\prime}$, and then there is $f\in E\subseteq F$ that generates
$Eq(s,se)=Eq(s,se^{\prime})$ (using Proposition 2.5), so $S$ is
$F$-protomodal. $\Box$

###### Corollary 5.12

Let $S$ be a monoid. The following are equivalent:

  1. 1.

$S$ is a modal left $E$-monoid for some maximal right pre-reduced $E\subseteq
E(S)$;

  2. 2.

$S$ is a modal left $E$-monoid for every maximal right pre-reduced $E\subseteq
E(S)$;

  3. 3.

$S$ is protomodal.

There are monoids which are not protomodal. Let $S=\\{0,1,a\\}$ with $0$ a
zero, $1$ an identity and $a^{2}=0$; then $Eq(a,a0)=Eq(a,0)=\\{0,a\\}$, which
is not generated by an idempotent, so $S$ is not protomodal.

Even if a monoid is not protomodal, it will always have at least a rather
trivial inductive left $E$-monoid structure for some choice of $E$.

###### Proposition 5.13

Every monoid $S$ is an inductive left $\\{1\\}$-monoid, with $t\cdot 1=1$ for
all $t\in S$. Every integral monoid with zero is an inductive left
$\\{0,1\\}$-monoid, with $t\cdot 1=1$ for all $t\in S$, and $t\cdot 0=0$ for
non-zero $t$, with $0\cdot 0=1$.

Proof. The first assertion is almost trivial.

For the second, clearly $Eq(t1,t)=S1$. For non-zero $t$, $st0=st$ if and only
if $s=0=s0$, so $Eq(t0,t)=S0$, and $Eq(0,0^{2})=S=S1$. So $S$ is
$\\{0,1\\}$-protomodal, and hence is a modal $\\{0,1\\}$-monoid since
$\\{0,1\\}$ is obviously right pre-reduced. The condition (I2′) is easily
checked by a case analysis. $\Box$

More interestingly, we next show that every monoid has a largest $E$ (modulo
$\sim_{r}$) such that it is left $E$-modal, and in that case it is inductive
as well. (Indeed in the above three-element example $S$, this largest choice
is obviously $E=\\{1\\}$.)

###### Proposition 5.14

Let $S$ be a monoid, and define

$G=\bigcup\\{E\subseteq E(S)\mid S\mbox{ is $E$-protomodal}\\}.$

Then $S$ is $G$-protomodal, and if $S$ is also $H$-protomodal, then
$H\subseteq G$. Choosing $E^{\prime}$ to be maximal right pre-reduced in $G$,
$S$ is a modal left $E^{\prime}$-monoid, and $E^{\prime}$ is largest possible
in the sense that if $S$ is a modal left $E$-monoid, then $E$ is right-
equivalent to a subset of $E^{\prime}$. Moreover the left $E^{\prime}$-monoid
$S$ is inductive.

Proof. First note that $G\neq\emptyset$ by Proposition 5.13. Suppose $s\in S$
and $e\in G$. Then $e\in E$ for some $E\subseteq E(S)$ for which $S$ is
$E$-protomodal, so there is $f\in E\subseteq G$ that generates $Eq(s,se)$. So
$S$ is $G$-protomodal, and so by Proposition 5.11, $S$ is a modal left
$E^{\prime}$-monoid. Otherwise, only the final statement does not follow
immediately.

Define $F=\\{(e\cdot f)e\mid e,f\in E^{\prime}\\}$. Then $E^{\prime}\subseteq
F$ since for all $e\in E$, $e=(e\cdot e)e\in F$. Let $s\in S$ and $e\in F$.
Then $e=(f\cdot g)f$ for some $f,g\in E^{\prime}$. We show that $Eq(s,se)$ is
generated by $h=((s\cdot f)\cdot(s\cdot g))(s\cdot f)\in F$, as computed in
the modal left $E^{\prime}$-monoid $S$. Because $(s\cdot f)sf=(s\cdot f)s$,
$(s\cdot g)sg=(s\cdot g)s$ and $h(s\cdot f)=h(s\cdot f)(s\cdot g)$, we have
that $hsfg=hsg=hs=hsf$, so in particular, $hs\in Eq(fg,g)$, and so
$hse=hs(f\cdot g)f=hsf=hs$, so $h\in Eq(se,s)$. Suppose $t\in
Eq(se,s)=Eq(s(f\cdot g)f,s)$. Then $ts=ts(f\cdot g)f=ts(f\cdot g)fg$, so
$ts=tsf=tsg$, so $t(s\cdot f)=t(s\cdot g)=t$, and so by Lemma 5.6, $th=t$. So
$Eq(se,s)=Sh$. So $S$ is $F$-protomodal and so $F\subseteq G$. It follows from
the definition of $E^{\prime}$ that for all $e,f\in E^{\prime}$, there is
$g\in E^{\prime}$ such that $g\sim_{r}(e\cdot f)e\in F\subseteq G$, so by
Proposition 5.7, the modal left $E^{\prime}$-monoid $S$ is inductive. $\Box$

###### Corollary 5.15

Every modal left $E$-monoid $S$ is an inductive left $E^{\prime}$-monoid for
some $E^{\prime}$ containing $E$.

###### Corollary 5.16

If $S$ is a modal left $E$-monoid in which $E$ is maximal right pre-reduced,
then it is inductive, and for $e,f\in E$, $e\wedge f\sim_{r}(e\cdot f)e$.

###### Corollary 5.17

If $S$ is protomodal, then for any maximal right pre-reduced $E\subseteq
E(S)$, $S$ is an inductive left $E$-monoid such that $e\wedge f\sim_{r}(e\cdot
f)e$ for all $e,f\in E$.

###### Definition 5.18

Suppose $S$ is protomodal. Then for $E,E^{\prime}$ maximal right pre-reduced
sets of idempotents, $Rest(E,S)\cong Rest(E^{\prime},S)$ as left restriction
monoids, and if $S$ is integral then $Rest_{0}(E,S)\cong
Rest_{0}(E^{\prime},S)$.

Proof. Now $S$ is an inductive left $E$-monoid and an inductive left
$E^{\prime}$-monoid, integral if $S$ is integral as a monoid. Of course
$E\sim_{r}E^{\prime}$, so by Proposition 3.12, $Rest(E,S)\cong
Rest(E^{\prime},S)$, and if $S$ is integral, $Rest_{0}(E,S)\cong
Rest_{0}(E^{\prime},S)$. $\Box$

###### Definition 5.19

Suppose $S$ is protomodal. If $E$ is a maximal right pre-reduced set of
idempotents of $S$, denote the isomorphism class of $Rest(E,S)$ (and
$Rest_{0}(E,S)$ if $S$ is integral) by $Rest(S)$ (respectively $Rest_{0}(S)$).

Informally, we will write “$A\cong Rest(S)$” rather than “$A\in Rest(S)$”. In
fact we can also obtain $Rest(S)$ as a left restriction semigroup defined
independent of the choice of $E$, as follows. (We omit the details, which are
routine to check.)

Suppose $S$ is protomodal, and form the constellation $Q=C_{E(S)}(S)$. Define
the equivalence relation $\theta$ on $Q$ as follows: set
$(e,s)\mathrel{\theta}(f,t)$ if and only if $e\sim_{r}f$ and $es=et$
(equivalently, $fs=ft$). This turns out to be a congruence on $Q$ which when
factored out gives a constellation $Q/\theta\cong C_{E}(S)$ where $E$ is any
maximal right pre-reduced set of idempotents of $S$, and so the induced left
restriction semigroup on the inductive constellation $Q/\theta$ is in
$Rest(S)$. Something very similar can be done for $Rest_{0}(S)$. This approach
highlights the irrelevance of the choice of any particular maximal right pre-
reduced set of idenpotents $E\subseteq E(S)$, since all of $E(S)$ is used in
the construction.

###### Example 5.20

A small example.

Consider the monoid $S=\\{1,e,f,g,s\\}$, given by the following multiplication
table. (It is routine to check that $T=\\{e,f,g,s\\}$ is a subalgebra which is
a semigroup, indeed a band, and so $S$ is $T$ with adjoined identity element.)

$\begin{array}[]{c|ccccc}\times&e&1&f&g&s\\\ \hline\cr e&e&e&e&e&e\\\
1&e&1&f&g&s\\\ f&e&f&f&e&e\\\ g&s&g&s&g&s\\\ s&s&s&s&s&s\end{array}.$

Let $E=\\{1,e,f,g\\}$, a maximal right pre-reduced subset of $E(S)=S$, since
$e\sim_{r}s$ but otherwise no two elements of $S$ are $\sim_{r}$-related.
Clearly $e\leq_{r}f,g\leq_{r}1$. It is not hard to check that there is a left
$E$-modal operation defined as follows:

$\begin{array}[]{c|cccc}\cdot&e&1&f&g\\\ \hline\cr e&1&1&1&1\\\ 1&e&1&f&g\\\
f&g&1&1&g\\\ g&f&1&f&1\\\ s&1&1&1&1\end{array}.$

Since $E$ is maximal right pre-reduced, the modal left $E$-monoid $S$ is
inductive by Corollary 5.16. Note that $f\wedge g=e$ but $(f\cdot g)f=gf=s$.
The only other maximal right pre-reduced choice involves replacing $e$ by $s$
in $E$ to give $E^{\prime}=\\{1,s,f,g\\}$; it follows from Proposition 5.5
that $S$ is an inductive left $E^{\prime}$-monoid also. So letting
$e^{\prime}=s,s^{\prime}=e$ with $f^{\prime}=f,g^{\prime}=g$ and
$1^{\prime}=1$, we see that as computed in $S$, $(g^{\prime}\cdot
f^{\prime})g^{\prime}=(g\cdot f)^{\prime}g^{\prime}=f^{\prime}g^{\prime}=e=g$,
while $g^{\prime}\wedge f^{\prime}=(g\wedge f)^{\prime}=e^{\prime}=s$ so they
are still unequal. This shows that there are protomodal left $E$-monoids
having no choice of maximal right pre-reduced $E$ for which the associated
inductive $E$-monoid has definable meets.

Note that $S^{\prime}=\\{e,1,f,s\\}$ is a submonoid of $S$ above. Letting
$E^{\prime\prime}=\\{1,f,s\\}$, it is easy to see that $S^{\prime}$ is an
inductive left $E^{\prime\prime}$-monoid, and indeed that $h\wedge k=(h\cdot
k)h$ for all $h,k\in E^{\prime\prime}$, yet $E^{\prime\prime}$ is not right
reduced. So a modal left $E$-monoid with definable meets need not have $E$
right reduced, showing that the converse of the final part of Proposition 5.7
does not hold in general.

##  6 Connection with the Zappa-Szép product

At this point it is worth noting that one could use an inductive $E$-monoid
$S$ to define a semidirect product in the usual way, since $S$ acts on the
semilattice $E$. Thus, we could define, for all $(e,s),(f,t)\in E\times S$,

$(e,s)*(f,t)=(e\wedge(s\cdot f),st),\ D((e,s))=(e,1),$

and the result is well-known to be a proper left restriction semigroup which
we call $P(E,S)$ here; see [16] for example. This is different to our
definition of both domain and multiplication in $Rest(E,S)$, and the
underlying set is all of $E\times S$. However, we do have the following.

###### Proposition 6.1

Let $S$ be an inductive left $E$-monoid. Then the mapping
$\psi:P(E,S)\rightarrow Rest(E,S)$ given by $\psi((e,s))=(e,es)$ is a
surjective left restriction semigroup homomorphism which separates domain
elements.

Proof. First, note that $\psi$ is surjective, since it fixes all elements of
$C_{E}(S)\subseteq P(E,S)$. If $(e,s)\in P(E,S)$, then
$\psi(D((e,s)))=\psi((e,1)=(e,e)=D((e,es))=D(\psi((e,s))$, so $\psi$ respects
$D$. For $(e,s),(f,t)\in P(E,S)$, first note that for any $g\in E$, the
following are equivalent: $g\leq_{r}e\wedge((es)\cdot f)$; $g\leq_{r}e$ and
$g\leq_{r}(es)\cdot f$; $g=ge$ and $ges=gesf$; $g=ge$ and $gs=gsf$;
$g\leq_{r}e$ and $g\leq_{r}s\cdot f$; $g\leq_{r}e\wedge(s\cdot f)$. Hence
$e\wedge((es)\cdot f)=e\wedge(s\cdot f)$. Thus,

$\displaystyle\psi((e,s))\psi((f,t))$ $\displaystyle=$
$\displaystyle(e,es)(f,ft)$ $\displaystyle=$ $\displaystyle(e\wedge((es)\cdot
f),(e\wedge((es)\cdot f))esft)$ $\displaystyle=$ $\displaystyle(e\wedge(s\cdot
f),(e\wedge(s\cdot f))esft)$ $\displaystyle=$ $\displaystyle(e\wedge(s\cdot
f),(e\wedge(s\cdot f))sft)$ $\displaystyle=$ $\displaystyle(e\wedge(s\cdot
f),(e\wedge(s\cdot f))(s\cdot f)sft)$ $\displaystyle=$
$\displaystyle(e\wedge(s\cdot f),(e\wedge(s\cdot f))(s\cdot f)st)$
$\displaystyle=$ $\displaystyle(e\wedge(s\cdot f),(e\wedge(s\cdot f))st)$
$\displaystyle=$ $\displaystyle\psi((e\wedge(s\cdot f),st)$ $\displaystyle=$
$\displaystyle\psi((e,s)*(f,t))$

so $\psi$ respects multiplication. Trivially $\psi$ separates domain elements.
$\Box$

So every left restriction monoid with enough large idempotents is a domain-
separating homomorphic image of a proper left restriction semigroup,
specifically of a semidirect product of a monoid with a semilattice. Theorem
4.6 in [16] shows that every left restriction semigroup is a projection-
separating homomorphic image of a proper one which in this case is only a
subsemigroup of a semidirect product of a monoid with a semilattice.

In many cases, there is a nice connection with Zappa-Szép products as in [14];
these generalise semidirect products. For groups, monoids and indeed
semigroups, we say $S$ is an internal Zappa-Szép product of subsemigroups
$M_{1},M_{2}$ if every $s\in S$ may be uniquely expressed as $s=m_{1}m_{2}$
where $m_{1}\in M_{1},m_{2}\in M_{2}$. If $S$ is a group/monoid, we require
$M_{1},M_{2}$ to be subgroups/submonoids, and in these cases there is an
external characterisation of Zappa-Szép products in terms of actions.

Very generally, one may define an external Zappa-Szép product of semigroups if
each acts on the other in a certain way. We here follow the notational
conventions used in [24], modified to have some notational similarity with the
current situation. Thus suppose $S,E$ are semigroups with multiplication in
$S$ denoted by juxtaposition and in $E$ by $\wedge$, and that we have actions
$S\times E\rightarrow E$ given by $(s,e)\mapsto s\cdot e$, and $S\times
E\rightarrow S$ given by $(s,e)\mapsto s^{e}$, satisfying the following four
conditions: for all $s,t\in S$ and $e,f\in E$,

  1. (ZS1)

$(st)\cdot e=s\cdot(t\cdot e)$,

  2. (ZS2)

$s\cdot(e\wedge f)=(s\cdot e)\wedge(s^{e}\cdot f)$,

  3. (ZS3)

$(s^{e})^{f}=s^{e\wedge f}$,

  4. (ZS4)

$(st)^{e}=s^{t\cdot e}t^{e}$.

If these conditions hold, then define, for all $(e,s),(f,t)\in E\times S$,

$(e,s)\otimes(f,t)=(e\wedge(s\cdot f),(s^{f})t)=(e\wedge(s\cdot f),(s\cdot
f)st).$

Then $\otimes$ is an associative operation, and $E\bowtie S=(E\times
S,\otimes)$ is the external Zappa-Szép product of $E$ and $S$. There is an
obvious similarity with the definition of multiplication in $Rest(E,S)$, but
note that $(e,s)\in Rest(E,S)$ only if $es=s$.

For the external Zappa-Szép product to correspond to the internal version, at
least for monoids, one assumes four further conditions involving the identity
elements, but there is still interest in external Zappa-Szép products of
semigroups satisfying only (ZS1) to (ZS4).

###### Proposition 6.2

Let $S$ be an inductive left $E$-monoid. Define $s\cdot e$ using the left
$E$-modal operation and $s^{e}=(s\cdot e)s$. Then Laws (ZS1), (ZS2) and (ZS4)
hold. Moreover (ZS3) holds if and only if $E$ has definable meets, and in that
case, $Rest(E,S)$ is a subsemigroup of the Zappa-Szép product $E\bowtie S$.

In this case, ${\widehat{E}}=\\{(e,e)\mid e\in E\\}$ is a semilattice
isomorphic to $(E,\wedge)$, and $Rest(E,S)$ is the maximum left restriction
subsemigroup of $E\bowtie S$ with set of domain elements ${\widehat{E}}$. If
$S$ is with zero, then $(0,0)$ is a zero element of $E\bowtie S$ and
$Rest_{0}(E,S)$ is the maximum left restriction subsemigroup with zero of
$E\bowtie S$ with set of domain elements ${\widehat{E}}$.

Proof. (ZS1) is immediate. For (ZS2),

$(s\cdot e)\wedge(s^{e}\cdot f)=(s\cdot e)\wedge(((s\cdot e)s)\cdot f)=(s\cdot
e)\wedge((s\cdot e)\cdot(s\cdot f))=(s\cdot e)\wedge(s\cdot f)=s\cdot(e\wedge
f)$

using Proposition 5.7. For (ZS4), $s^{t\cdot e}t^{e}=(s\cdot(t\cdot
e))s(t\cdot e)t=(s\cdot(t\cdot e))st=((st)\cdot e)st=(st)^{e}$.

Now suppose $E$ has definable meets. Then for $s\in S$ and $e,f\in E$,

$(s^{e})^{f}=(((s\cdot e)s)\cdot f)((s\cdot e)s)=((s\cdot e)\cdot(s\cdot
f))(s\cdot e)s=((s\cdot e)\wedge(s\cdot f))s=(s\cdot(e\wedge f))s=s^{e\wedge
f},$

establishing (ZS3). Conversely, if (ZS3) holds, note that for all $e\in E$,
$1^{e}=(1\cdot e)1=e$, and so putting $s=1$ in (ZS3) gives
$(1^{e})^{f}=1^{e\wedge f}$ for all $e,f\in E$, which is to say that
$e^{f}=e\wedge f$, so $(e\cdot f)e=e\wedge f$, so $E$ has definable meets.

So if $E$ has definable meets, then for $(e,s),(f,t)\in E\bowtie S$ for which
$es=s$ and $ft=t$, we have $(e\wedge(s\cdot f))s=(e\cdot(s\cdot
f))es=((es)\cdot f)es=(s\cdot f)s$, and so

$(e,s)\otimes(f,t)=(e\wedge s\cdot f,(s\cdot f)st)=(e\wedge(s\cdot
f),(e\wedge(s\cdot f)st)=(e,s)(f,t)$

as in $Rest(E,S)$.

Assuming definable meets, the fact that $\widehat{E}$ is as described is
easily seen, as is the fact that for $(e,s)\in E\bowtie S$, if
$(f,f)\otimes(e,s)=(e,s)$ for some $f\in E$, then

$(e,s)=(f\wedge(f\cdot e),(f\cdot e)fs)=(f\wedge e,(f\wedge e)s),$

so $f\wedge e=e$ and $(f\wedge e)s=s$, so $e\leq_{r}f$ and $es=s$, so
$(e,s)\in Rest(E,S)$. So any left restriction semigroup in $E\bowtie S$ with
domain elements ${\widehat{E}}$ is a subset of $Rest(E,S)$. If $S$ is an
inductive left $E$-monoid with zero, then for $(e,0)\in E\bowtie S$, we have

$(e,0)(0,0)=(e\wedge(0\cdot 0),(0\cdot 0)0)=(e,0),$

so any left restriction subsemigroup of $E\bowtie S$ which has zero $(0,0)$
cannot include elements $(e,0)$ if $e\neq 0$. So $Rest_{0}(E,S)$ is the
largest such. $\Box$

Starting with a left restriction semigroup $S$, a similar construction to the
above is used in Section 3 of [24], by letting $E=D(S)$, and by setting
$s\cdot e=D(se)$ and $s^{e}=se=D(se)s=(s\cdot e)s$. It is shown that
(ZS1)–(ZS4) are satisfied in this case, and so $E\bowtie S$ exists, and the
subset $T=\\{(e,s)\in E\times S\mid es=s\\}$ is shown to be the largest left
restriction subsemigroup of $E\bowtie S$ in which $D(T)=\\{(e,e)\mid e\in
D(S)\\}$ (see Theorem $3.4$ of [24]). However, this is not a special case of
our result since $S$ equipped with the above action is not a modal left
$E$-monoid even if $S$ has identity, since $s\cdot 1=D(s)$ rather than $1$.
This is manifest in the structure of $T$ since the induced constellation
product $(e,s)\circ(f,t)$ exists if and only if $e=D(s)$ and $sf=s$, a
stronger condition than ours.

##  7 Applications

Courtesy of the results of Section 4, it is quite straightforward to identify
and then describe specific left restriction monoids as semigroup left
$E$-completions. In this section, we do this for three important classes of
examples.

###  7.1 Transformations and partial functions.

The canonical examples of semigroups and left restriction semigroups are
$T_{X}$ and $PT_{X}$ respectively. We begin with a result relating them.

First, we note that the idempotent elements of $T_{X}$ are precisely the
projections onto non-empty subsets of $X$: mappings that fix their range. It
is easy to see that for $e,f\in E(T_{X})$, $e\leq_{r}f$ if and only if
$\mbox{ran}(e)\subseteq\mbox{ran}(f)$ (where $\mbox{ran}(e)$ denotes the range
of $e$), and so $e\sim_{r}f$ if and only if $\mbox{ran}(e)=\mbox{ran}(f)$.
Hence, a maximal right pre-reduced subset of $T_{X}$ consists of precisely one
projection onto every possible non-empty subset of $X$.

If $S$ is protomodal, recall the definitions of $Rest(S)$ (and $Rest_{0}(S)$
where it makes sense) as in Definition 5.19. Recall also that for a semigroup
$S$, $S^{0}$ denotes $S$ with adjoined zero.

###### Theorem 7.1

$T_{X}^{0}$ is a protomodal monoid, and $PT_{X}\cong Rest_{0}(T_{X}^{0})$.

Proof. Since $D(0)=0$, the empty function, $PT_{X}$ is a left restriction
monoid with zero. We identify $S=(PT_{X})_{1}$ with $T_{X}$ as a monoid. For
each non-zero $e\in D(PT_{X})$, pick precisely one $e^{\prime}\in E(T_{X})$
for which $\mbox{ran}(e^{\prime})=\mbox{ran}(e)=\mbox{dom}(e)$, and also set
$0^{\prime}=0$. It follows easily that $e^{\prime}e=e^{\prime}$ and
$ee^{\prime}=e$, since $e^{\prime}$ fixes its range, and so
$e\sim_{r}e^{\prime}$. Hence $F=\\{e^{\prime}\mid e\in D(PT_{X}),e\neq 0\\}$
is a set of enough large idempotents of $PT_{X}$. It follows from Theorem 4.3
that $T_{X}^{0}$ is an integral inductive left $E$-monoid in which
$E=F\cup\\{0\\}$ is right pre-reduced, and the left $E$-modal operation is
$s\cdot e^{\prime}=D(se)^{\prime}$ if $s\neq 0$, with $0\cdot e^{\prime}=1$,
for all $e^{\prime}\in E$, and $PT_{X}\cong Rest_{0}(E,T_{X}^{0})$. But
choosing any $f\in E(T_{X})$, pick $e\in D(PT_{X})$ such that
$\mbox{ran}(e^{\prime})=\mbox{ran}(e)=\mbox{dom}(e)$; again, $f\sim_{r}e$, and
so $PT_{X}$ has precisely enough large idempotents. It follows from
Proposition 4.4 that $E$ is maximal right pre-reduced, so $T_{X}^{0}$ is
protomodal by Corollary 5.12, and so $PT_{X}\cong Rest_{0}(T_{X}^{0})$. $\Box$

Hence the entire structure of the (left restriction) monoid $PT_{X}$ may be
recovered from that of the protomodal monoid $T_{X}^{0}$ via zero-reduced left
$E$-completion, where $E$ is any maximal right pre-reduced set of idempotents
in $E(T_{X}^{0})$. By contrast, consider the symmetric inverse monoid $I_{X}$
on the set $X$, which is a sub-left restriction monoid of $PT_{X}$ in which
$D(s)=ss^{\prime}$ for all $s\in I_{X}$. If $X$ is finite, then $(I_{X})_{1}$
is the symmetric group on $X$, and so certainly does not have enough large
idempotents and so $I_{X}$ cannot be a left $E$-completion, zero-reduced or
not.

Because every left restriction semigroup embeds in $PT_{X}$ for some $X$, we
immediately obtain the following.

###### Corollary 7.2

Every left restriction semigroup embeds in $Rest(S)$ for some protomodal
monoid $S$.

There are choices of maximal right pre-reduced $E$ in $E(T_{X}^{0})$ that are
right reduced, and this allows us to relate our results to Zappa-Szép products
of semigroups using Proposition 6.2. To show this for arbitrary $X$, we need
one form of the axiom of choice (namely, the well-ordering theorem).

Let $X$ be a set, and equip it with a well-order $\leq$. Then for $e\in
E(T_{X})$, denote by $u_{e}\in X$ the smallest element of its range under
$\leq$.

###### Lemma 7.3

Define $E\subseteq E(T_{X})$ as follows:

$E=\\{e\in E(T_{X})\mid e(x)\neq x\mbox{ implies }e(x)=min(\mbox{ran}(e))\\}.$

Then $E$ is maximal right pre-reduced and indeed is right reduced.

Proof. Define $E$ as above. Evidently there is precisely one choice of $e\in
E$ for every possible range, so $E$ is maximal right pre-reduced. Suppose
$e,f\in E$ and $ef=e$, so $\mbox{ran}(e)\subseteq\mbox{ran}(f)$. Now for
$x\in\mbox{ran}(f)$, $xfe=xe$, while for $x\not\in\mbox{ran}(f)$,
$xfe=u_{f}e=u_{e}=xe$ since either $u_{f}=u_{e}$ or else
$u_{f}\not\in\mbox{ran}(e)$. So $fe=e$. Hence $E$ is right reduced. $\Box$

It is now straightforward to add $0$ to such $E$ to get a right reduced
maximal right pre-reduced subset of $E(T_{X}^{0})$. From Lemma 7.3, Theorem
7.1 and Proposition 6.2, we obtain the following.

###### Corollary 7.4

Let $E$ be a right reduced maximal right pre-reduced subset of $E(T_{X}^{0})$.
Then $PT_{X}$ embeds as the largest left restriction semigroup with zero
within the Zappa-Szép product $E\bowtie S$ having domains elements
${\widehat{E}}$ as in Proposition 6.2.

###### Example 7.5

Constructing $PT_{X}$ from $T_{X}^{0}$ when $|X|=2$.

To give an illustration of the construction in the simplest non-trivial case,
let $X=\\{x,y\\}$ be a two-element set. Then $S=T_{X}^{0}=\\{1,0,i,e,f\\}$,
where $1$ is the identity map, $0$ is the adjoined zero,
$i=\\{(x,y),(y,x)\\}$, $e=\\{(x,x),(y,x)\\}$ and $f=\\{(x,y),(y,y)\\}$. There
is only one possible choice of $E$ in this case, namely
$E=E(S)=\\{0,1,e,f\\}$, which is therefore right reduced. The elements of
$Rest_{0}(E,S)$ are then easily seen to be

$(0,0),(e,e),(f,f),(e,f),(f,e),(1,1),(1,i),(1,e),(1,f),$

corresponding to partial functions as follows

$(0,0)\leftrightarrow\emptyset,\ (e,e)\leftrightarrow\\{(x,x)\\},\
(f,f)\leftrightarrow\\{(y,y)\\},\ (e,f)\leftrightarrow\\{(x,y)\\},$
$(f,e)\leftrightarrow\\{(y,x)\\},\ (1,1)\leftrightarrow 1,\
(1,i)\leftrightarrow i,\ (1,e)\leftrightarrow e,\ (1,f)\leftrightarrow f.$

For example, since $D((e,f))=(e,e)$, and $(e,f)=(e,e)(1,f)$, we interpret
$(e,f)$ as “the restriction of $f$ to $\mbox{dom}(e)$”.

Now the constellation $Q=C_{E}(T_{X}^{0})$ correctly enumerates the elements
of $PT_{X}$, and the straightforwardly calculated constellation product in $Q$
correctly calculates compositions of partial functions whenever the former are
defined. For example, $(e,f)(1,i)$ is just the constellation product
$(e,f)\circ(1,i)=(e,fi)=(e,e)$, corresponding to calculating $\\{(x,y)\\}$
followed by $i$ to give $\\{(x,x)\\}=e$. However, for general compositions, we
use multiplication in $Rest_{0}(E,T_{X}^{0})$. Reversing the order in the
previous example gives $(1,i)(e,f)$, which requires calculation of $i\cdot e$.
Now $Eq(ie,i)=Eq(e,i)=\\{0,f\\}=Sf$, so $i\cdot e=f$, and so

$(1,i)(e,f)=(1\wedge(i\cdot e),(i\cdot e)if)=(f,fif)=(f,ef)=(f,f),$

corresponding to $e$ followed by $\\{(x,y)\\}$, which equals $f$.

###  7.2 Binary relations under demonic composition.

$PT_{X}$ is the canonical example of a left restriction semigroup, but other
naturally arising examples exist. Next we consider binary relations under the
operations of domain and so-called demonic composition, to be introduced
shortly.

First, we extend the definitions of domain and range to cover binary relations
in the usual way: for $s\in Rel_{X}$, let

$\displaystyle\mbox{dom}(s)$ $\displaystyle=\\{x\in X\mid(x,y)\in s\mbox{ for
some }y\in X\\},$ $\displaystyle\mbox{ran}(s)$ $\displaystyle=\\{y\in
X\mid(x,y)\in s\mbox{ for some }x\in X\\}.$

On $Rel_{X}$, define demonic composition $\circledast$ via

$\rho\circledast\tau=\\{(x,y)\in\rho\tau\mid\mbox{ for all }z\in
X,(x,z)\in\rho\Rightarrow z\in\mbox{dom}(\tau)\\},$

where $\rho\tau$ denotes the usual composition of $\rho,\tau\in Rel_{X}$. As
noted by various authors, $\circledast$ is associative; indeed if we define
$D$ on $Rel_{X}$ exactly as for $PT_{X}$ in terms of domains,
$(Rel_{X},\circledast,D)$ is a left restriction monoid (for example, see [2])
with identity the diagonal relation (the identity function on $X$).

Denote by $TRel_{X}$ the set of left total binary relations on $X$: those
$s\in Rel_{X}$ for which $\mbox{dom}(s)=X$. Usual and demonic composition
coincide on $TRel_{X}$, which is therefore a submonoid of $Rel_{X}$ under each
of these operations. Note that $T_{X}$ is a submonoid of $TRel_{X}$. All of
these observations carry over when we adjoin $0$ to the various semigroups.

###### Theorem 7.6

$(Rel_{X},\circledast,D)\cong Rest_{0}(E,TRel^{0}_{X})$, where $E$ is maximal
right pre-reduced within $E(T_{X}^{0})$ as in Example 7.1.

Proof. Since $D(Rel_{X})=D(PT_{X})$, $Rel_{X}$ has enough large idempotents
(the same as for $PT_{X}$), and obviously satisfies $D(0)=0$. Evidently
$(Rel_{X})_{1}$ gives a copy of $TRel_{X}$, and so the result follows by
Theorem 4.3 on letting $E$ be chosen as in Theorem 7.1. $\Box$

Though not a left restriction semigroup, the demigroup $S=(Rel_{X},;,D)$, in
which ; is ordinary relational composition and $D$ is domain, is a left
Ehresmann semigroup, meaning that it satisfies certain weaker conditions than
being a left restriction semigroup. It was noted in [20] that
$Rest^{D}_{D(S)}(S)$, the left $(D,D(S))$-completion of $S$, is isomorphic to
$(Rel_{X},\circledast,D)$, giving a different way to obtain the latter, not as
an extension of $Rel_{X}$ but in effect by redefining multiplication on
$Rel_{X}$ itself.

Note also that multiplication in the constellation $C_{E}(TRel^{0}_{X})$
agrees with the restricted product (defined for any demigroup at the end of
Section 2.3) obtained from either $(Rel_{X},;,D)$ or $(Rel_{X},\circledast,D)$
(since standard and demonic composition of $\rho,\tau$ agree when
$\mbox{ran}(\rho)\subseteq\mbox{dom}(\tau))$. However, the semigroup
$E$-completion is only capable of reproducing the demonic composition.

Because $E$ is the same as in Theorem 7.1, it may be chosen to be right
reduced, and then we obtain the following.

###### Corollary 7.7

Let $E$ be a right reduced maximal right pre-reduced subset of $E(T_{X}^{0})$.
Then $(Rel_{X},\circledast,D)$ embeds as the largest left restriction
semigroup with zero within the Zappa-Szép product $E\bowtie TRel_{X}^{0}$
having domains elements ${\widehat{E}}$ as in Proposition 6.2.

We note that the choice of $E$ in Theorem 7.6 is never maximal right pre-
reduced in $E((TRel_{X})^{0})$. For example, for the full relation $\nabla$ on
$X$, there is no $e\in E$ for which $\nabla\sim_{r}e$, as is easily seen.
However, this does not imply $TRel_{X}^{0}$ is not protomodal.

###### Example 7.8

Constructing $Rel_{X}$ from $TRel_{X}^{0}$ when $|X|=2$.

Again, let $X=\\{x,y\\}$. This time,
$S=TRel_{X}^{0}=T_{X}^{0}\cup\\{g,h,\nabla,a,b\\}$, where $T_{X}^{0}$ is
represented as in Example 7.5, and $g=\\{(x,x),(x,y),(y,y)\\}$,
$h=\\{(x,x),(y,x),(y,y)\\}$, $\nabla$ is the full relation,
$a=\\{(x,x),(x,y),(y,x)\\}$, and $b=\\{(x,y),(y,x),(y,y)\\}$. Now
$E(S)=\\{0,1,e,f,g,h,\nabla\\}$ (which happens to be right pre-reduced but not
right reduced since $eh=e$ yet $he=\nabla$), and let $E$ be $\\{0,1,e,f\\}$ as
in Example 7.5. There are 16 elements of $Rest_{0}(S,E)$, namely the nine
elements of $Rest_{0}(T_{X}^{0},E)$,

$(0,0),(e,e),(f,f),(e,f),(f,e),(1,1),(1,i),(1,e),(1,f),$

together with five additional elements capturing the non-functional left-total
relations over $X$,

$(1,g),(1,h),(1,\nabla),(1,a),(1,b),$

and the two further elements $(e,\nabla),(f,\nabla)$, corresponding to
restricting the domain of $\nabla$ to $\mbox{dom}(e),\mbox{dom}(f)$
respectively, giving $\\{(x,x),(x,y)\\}$ and $\\{(y,x),(y,y)\\}$.

Again, whenever it exists the constellation product in $C_{E}(TRel_{X}^{0})$
faithfully calculates not only demonic but also standard compositions of
relations. For general demonic compositions, we use multiplication in
$Rest_{0}(E,TRel_{X}^{0})$. As an example, consider
$a\circledast\\{(x,x),(x,y)\\}=\\{(y,x),(y,y)\\}$. Working instead in
$Rest_{0}(E,TRel_{X}^{0})$ gives $(1,a)(e,\nabla)=(1\wedge a\cdot e,(a\cdot
e)\nabla)$. But $Eq(ae,a)=Eq(e,a)=\\{0,f\\}=Sf$, so $a\cdot e=f$ and we obtain
$(1,a)(e,\nabla)=(f,f\nabla)=(f,\nabla)$, which does indeed correspond to
$\\{(y,x),(y,y)\\}$.

Note that $TRel_{X}^{0}$ in this example is not protomodal: it is routine to
verify that the equalizing set $Eq(a,a\nabla)=Eq(a,\nabla)=\\{a,\nabla,e,h\\}$
is not generated as a right ideal by any member of $E(S)$.

Indeed one can check that for any other idempotent in $E(TRel_{X}^{0})$ aside
from those in $E$, there exists $s\in TRel_{X}^{0}$ for which $Eq(s,se)$ is
not generated by any member of $E(S)$. It follows that $E$ is already largest
possible (as in Proposition 5.14): no bigger $E^{\prime}$ exists for which
$TRel_{X}^{0}$ is an inductive $E^{\prime}$-monoid. We do not know if $E$ as
in Theorem 7.6 is largest possible for arbitrary $X$.

###  7.3 Transformations and left total partitions.

In Subsection 7.1, $T_{X}^{0}$ was seen to be a (left) protomodal monoid, and
$PT_{X}\cong Rest_{0}(T_{X}^{0})$ as a left restriction monoid. In fact,
$T_{X}$ is also right protomodal, leading to an unexpected connection with the
partition monoid on the set $X$.

We do not here intend to give an exhaustive introduction to partition monoids,
and instead point the interested reader to introductions to the topic
appearing in the literature, for example [3] and [4], where the notation and
definitions are consistent with those we use here.

Let $X$ be a non-empty set. A partition is an equivalence relation on $X\cup
X^{\prime}$ where $X^{\prime}$ is a copy of $X$. The partitions on $X$ may be
endowed with a special type of multiplication which makes them into a regular
$*$-semigroup (an involuted semigroup satisfying the law $xx^{*}x=x$) called
the partition monoid on $X$, here denoted $P_{X}$. (Again, we refer the reader
to work such as [3] and [4] for the precise definition.)

The partition monoid concept came from work in [11] and [23], where in the
finite case the authors related partition monoids to partition algebras
(already considered by many authors), via the notion of a twisted semigroup
algebra.

Now denote by $P^{lt}_{X}$ the submonoid of $P_{X}$ consisting of the left
total partitions, meaning partitions having domain all of $X$: $\rho$ is one
such if for all $x\in X$ there is $y\in X^{\prime}$ such that $(x,y)\in\rho$
(this is denoted $P^{fd}_{X}$ in [4]). Let $F$ consist of all idempotents in
the copy of the dual symmetric inverse monoid (see [6]) in $P^{lt}_{X}$; so
the elements of $F$ correspond with the equivalence relations on $X$. $F$ is a
semilattice with multiplication corresponding to join of equivalence
relations, and so for $e,f\in E$, $e$ is finer than $f$ if and only if $e\leq
f$, which means that $ef=f=fe$. View $T_{X}$ as embedded in $P^{lt}_{X}$ by
identifying $t\in T_{X}$ with $\rho_{t}$ which puts everything in $X$ not in
the range of $t$ into a block by itself.

It is convenient to draw partitions as graphs with vertex set $X\cup
X^{\prime}$ which have as their connected components the blocks of the
partition, with vertices in $X$ appearing in an upper row and vertices in
$X^{\prime}$ below them. For example, in Figure 1, in which
$X=\\{1,2,3,4,5\\}$ and
$X^{\prime}=\\{1^{\prime},2^{\prime},3^{\prime},4^{\prime},5^{\prime}\\}$, the
first graph represents the left total partition $\rho$ given by
$\\{1,2,1^{\prime}\\},\\{3,4,5,4^{\prime},5^{\prime}\\},\\{2^{\prime},3^{\prime}\\}$.
(Note that every element of $X$ is in a cell with something from $X^{\prime}$,
so $\rho\in P^{lt}_{X}$, which is true of the next two examples as well.) The
second represents the transformation in which $1\mapsto 1,2\mapsto 1,3\mapsto
3,4\mapsto 3,5\mapsto 5$ as the partition $t\in T_{X}$ given by
$\\{1,2,1^{\prime}\\},\\{3,4,3^{\prime}\\},\\{5,5^{\prime}\\},\\{2^{\prime}\\},\\{4^{\prime}\\}$
(note that there is precisely one element of $X^{\prime}$ in every cell), and
the third represents the equivalence relation determined by the partition of
$X$ having cells $\\{1\\},\\{2,3\\},\\{4,5\\}$ as the partition $e\in F$ given
by
$\\{1,1^{\prime}\\},\\{2,3,2^{\prime},3^{\prime}\\},\\{4,5,4^{\prime},5^{\prime}\\}$.

Figure 1: Graphical depictions of the left total partitions $\rho,t$ and $e$.

Note that the identity element $1$ in $P_{X}$ (hence also in $P^{lt}_{X}$) is
the equivalence relation in which each cell is a singleton, which in the five-
element base set example above is represented by the partition
$\\{1,1^{\prime}\\},\\{2,2^{\prime}\\},\ldots,\\{5,5^{\prime}\\}$.

The following is noted in [4] (see Proposition $4.14$ there).

###### Proposition 7.9

$P^{lt}_{X}$ is a submonoid without zero of $P_{X}$ which is a right
restriction monoid in which $R(P^{lt}_{X})=F$.

Proof. For all $\rho\in P^{lt}_{X}$, let $R(\rho)$ be the coarsest $e\in F$
such that $\rho e=\rho$, which is simply the member of $F$ corresponding to
the range-side partition determined by $\rho$, hence the largest $e\in F$
under $\leq$ on the join-semilattice $F$ such that $\rho e=\rho$ (under the
meet-semilattice order on $F$). So as in the discussion of Section 2.2, $R$
defines an RC-semigroup operation on $M=P^{lt}_{X}$ in the sense of [12], with
$R(M)=F$. Note that for any $t\in T_{X}$ and $e\in F$, $R(te)=e$. It therefore
only remains to show that for all $\rho,\tau\in P^{lt}_{X}$, $R(\rho)\tau=\tau
R(\rho\tau)$. To do this, it suffices to show that
$R(\rho\tau)=R(R(\rho)\tau)$, and for all $e\in R(P^{lt}_{X})$ and $\rho\in
S$, $e\rho=\rho R(e\rho)$.

For $\rho\in P^{lt}_{X}$, let $t$ be any one transformation that takes
everything in each domain block of $\rho$ to one particular element of the
corresponding range block; it then follows fairly easily that $\rho=tR(\rho)$.
In particular, for $s\in T_{X}$ and $e\in R(P^{lt}_{X})$, $es\in P^{lt}_{X}$
can have $t$ chosen to be $s$ itself, and so $es=sR(es)$. Also, for any $e\in
R(P^{lt}_{X})$ and $\rho=tR(\rho)$ for some $t\in T_{X}$, $R(\rho
e)=R(tR(\rho)e)=R(\rho)e$.

Hence for $\rho,\tau\in P^{lt}_{X}$, writing $\rho=sR(\rho)$ and
$\tau=tR(\tau)$ for suitable $s,t\in T_{X}$, we see that

$R(R(\rho)\tau)=R(R(\rho)tR(\tau))=R(R(\rho)t)R(\tau),$

while

$\displaystyle R(\rho\tau)$ $\displaystyle=$ $\displaystyle
R(sR(\rho)tR(\tau))$ $\displaystyle=$ $\displaystyle R(stR(R(\rho)t)R(\tau))$
$\displaystyle=$ $\displaystyle R(R(\rho)t)R(\tau)$ $\displaystyle=$
$\displaystyle R(R(\rho)tR(\tau))$ $\displaystyle=$ $\displaystyle
R(R(\rho)\tau),$

and for any $e\in R(P^{lt}_{X})$,
$e\rho=esR(\rho)=sR(es)R(\rho)=sR(\rho)R(esR(\rho))=\rho R(e\rho)$. $\Box$

In Figure 1, observe that $R(\rho)=e$, while $R(t)=1$, and of course $R(e)=e$.
Generally, in the right restriction monoid $P^{lt}_{X}$, $(P^{lt}_{X})_{1}$
consists of those $\rho\in P^{lt}_{X}$ such that $R(\rho)=1$, that is, those
$\rho$ for which $\rho e=\rho$ for some $e\in E$ implies $e=1$. It follows
that such a $\rho$ must be a left total partition such that $\rho$ restricted
to its range row must be the diagonal relation. So the elements of
$(P^{lt}_{X})_{1}$ may be viewed as transformations (with those $x\in X$ not
in the image of $\rho$ being in cells by themselves), such as $t$ above.
Composition in $(P^{lt}_{X})_{1}$ is then easily seen to correspond to
transformation composition, so $(P^{lt}_{X})_{1}\cong T_{X}$, and we identify
the two monoids.

Again, recall that the idempotents of $T_{X}$ are projections, but this time
we are interested in $\leq_{l}$ on $E(T_{X})$. Recall that the kernel of $s\in
T_{X}$ is the equivalence relation $\\{(x,y)\in X\times X\mid s(x)=s(y)\\}$.
It is easy to check that for $e,f\in E(T_{X})$, $e\leq_{l}f$ (that is, $fe=e$)
if and only if the kernel of $e$ contains the kernel of $f$. Hence $E\subseteq
E(T_{X})$ is maximal left pre-reduced if and only if it consists of precisely
one projection for every possible element of $F\subseteq E(P^{lt}_{X})$.

###### Theorem 7.10

$T_{X}$ is a right protomodal monoid, and $P^{lt}_{X}\cong RRest(T_{X})$.

Proof. For $e\in F=R(P^{lt}_{X})$, there is
$e^{\prime}\in(P^{lt}_{X})_{1}=T_{X}$ such that
$ee^{\prime}=e^{\prime},e^{\prime}e=e$: let $e^{\prime}$ be any projection
having kernel the equivalence relation associated with $e$ (with elements of
$X$ not in the range in cells on their own). So $P^{lt}_{X}$ has enough large
idempotents (noting it has no zero), and so by (the dual of) Theorem 4.3,
$P^{lt}_{X}\cong RRest((P^{lt}_{X})_{1},E^{\prime})\cong RRest(T_{X})$, where
$E^{\prime}=\\{e^{\prime}\mid e\in R(P^{lt}_{X})\\}$ is left pre-reduced. But
for each $f\in E(T_{X})$, select $e\in F$ such that $e\sim_{r}f$ (so $e$ is
the kernel of $f$); this shows $P^{lt}_{X}$ has precisely enough large
idempotents, so arguing as in Theorem 7.1, $E^{\prime}$ is maximal left pre-
reduced and so $T_{X}$ is right protomodal. $\Box$

So in particular, there is an isomorphism $\psi:P^{lt}_{X}\rightarrow
RRest(T_{X},E)$, where $E$ consists of precisely one projection for each
possible member of $F$. As an example, if $e^{\prime}$ is the projection in
$E$ corresponding to $e$ in Figure 1, then $te^{\prime}=t$, and indeed
$\psi(\rho)=(t,e^{\prime})$. It was noted in [4] that one could (non-uniquely)
factorise elements of $P^{lt}_{X}$ into products of elements of
$T_{X}=(P^{lt}_{X})_{1}$ with elements of $F=R(P^{lt}_{X})$: in our example,
$\rho=te$. This is true of any right restriction monoid $S$ with enough large
idempotents $E$: for in its isomorphic copy $RRest(S_{1},E)$, we have
$(s,e)=(s,1)(e,e)$.

The opposite monoid $S$ of $P^{lt}_{X}$ is a left restriction monoid, hence is
functionally representable. But even more can be said, because $P^{lt}_{X}$
comes equipped with a domain operation given by $D(s)=ss^{*}\in
R(P^{lt}_{X})$; dualizing gives a range operation on the left restriction
monoid $S$, which can easily be shown to satisfy the laws given in [17] that
characterise semigroups of partial functions equipped with $D$ and $R$. So
$P^{lt}_{X}$ can be viewed as a kind of dual structure to $PT_{X}$. This
extends the relationship between the dual symmetric inverse monoid and the
familiar symmetric inverse monoid $I_{X}$ considered in [6] (noting that these
embed as right restriction monoids in $P^{lt}_{X}$ and $PT_{X}$ respectively),
and was also noted in [4] since both arise within $P_{X}$. It remains to be
determined whether there is a formal categorical duality as for symmetric and
dual symmetric inverse monoids as in [6].

As in the previous example, we can re-phrase things in terms of Zappa-Szép
products since there are choices of maximal left pre-reduced $E$ in $E(T_{X})$
that are left reduced. Again, the well-ordering theorem is needed for this.
Let $X$ be a set, and equip it with a well-order $\leq$. Define $E\subseteq
T_{X}$ such that, for each partition of $X$, we form the projection which maps
each cell of the partition to its smallest member. Evidently there is
precisely one member of $E$ for each equivalence relation on $X$, so $E$ is
maximal left pre-reduced.

###### Lemma 7.11

The set $E\subseteq E(T_{X})$ defined above is left reduced.

Proof. Suppose $e,f\in E$ and $ef=f$, so $ker(e)\subseteq ker(f)$. Now for
$x\in\mbox{ran}(e)$, $e^{-1}(x)$ is a cell of the equivalence relation
$ker(e)=\\{(a,b)\in X\times X\mid e(a)=e(b)\\}$, which is the disjoint union
of cells of $ker(f)$, one of which therefore contains $x$. Since $x$ was the
smallest member of its cell in $ker(e)$, it will be the smallest member of the
not larger cell in $ker(f)$ containing it, so by definition
$x\in\mbox{ran}(f)$. Hence $\mbox{ran}(e)\subseteq\mbox{ran}(f)$, and so
$fe=f$. Hence $E$ is left reduced. $\Box$

###### Corollary 7.12

Let $E$ be a left reduced maximal left pre-reduced subset of $E(T_{X}^{0})$.
Then $P^{lt}_{X}$ embeds as the largest right restriction semigroup within the
Zappa-Szép product $T_{X}\bowtie E$ (defined in the obvious dual way to
$E\bowtie S$) in terms of having range elements ${\widehat{E}}$ as in (the
dual of) Proposition 6.2.

Proof. $P^{lt}_{X}\cong RRest(E,T_{X})\subseteq T_{X}\bowtie E$. Now use the
dual of Proposition 4.4. $\Box$

##  8 Further work

Operations on the monoid $PT_{X}$ other than domain have been considered, for
example intersection, range and antidomain. Each is entirely determined by the
structure of the left restriction semigroup, since a given left restriction
semigroup admits an operation modelling intersection, range or antidomain in
at most one way. Hence, it must be possible to determine properties of
inductive left $E$-monoids that give rise to these operations in their left
$E$-completions. In future work, we shall show that an operation behaving like
intersection exists in $Rest(E,S)$ (resp. $Rest_{0}(E,S)$ if $S$ is integral)
if and only if $S$ is such that left equalizers of any two arbitrary elements
exist, and moreover this assumption forces $S$ to be protomodal.

In the case of $Rel_{X}$ as in Example 7.2, other operations and relations,
such as union and inclusion, can be defined on $TRel_{X}$, and should extend
to $Rel_{X}$ to give demonic counterparts of union and inclusion. Again, we
plan to explore this in future work.

## Acknowledgements

I would like to thank James East for discussions relating to the submonoid
$P^{lt}_{X}$ of $P_{X}$, as well as for assistance with the generation of
figures to represent partitions on finite sets.

## References

  * [1] Batbedat, A.: $\gamma$-demi-groups, demi-modules, produit demi-directs. In Semigroups, Proceedings, Oberwolfalch, Germany 1978, Lecture Notes in Mathematics 855, Springer-Verlag, pp. 1–18 (1981)
  * [2] J. De Carufel and J. Desharnais, Demonic Algebra with Domain, Relations and Kleene Algebra in Computer Science, Lecture Notes in Computer Science Volume 4136, 2006, pp 120–134.
  * [3] J. East, Generators and relations for partition monoids and algebras, Journal of Algebra 339 (2011) 1–26.
  * [4] J. East and R. Gray, “Ehresmann theory and partition monoids”, arXiv 2011.00663v1
  * [5] C. Ehresmann, “Oeuvres complètes et commentées” (A. C. Ehresmann, Ed.), Suppl. Cahiers Top Géom. Diff., Amiens, 1980-1984.
  * [6] D.P. Fitzgerald and J. Leech, Dual symmetric inverse monoids and representation theory, J. Austral. Math. Soc. 64 (1998), 345–367
  * [7] G. Grätzer, Universal Algebra, 2nd edn. Springer, New York (1979).
  * [8] Gould, V., Hollings, C.: Restriction semigroups and inductive constellations. Comm. Algebra 38, 261–287 (2009)
  * [9] Gould, V., Hollings, C. Actions and partial actions of inductive constellations. Semigroup Forum 82, 35–60 (2011).
  * [10] Gould, V., Stokes, T.: Constellations and their relationship with categories, Algebra Universalis 77 (2017), 271–304.
  * [11] T. Halverson, A. Ram, Partition algebras, European J. Combin. 26 (6) (2005) 869–921.
  * [12] M. Jackson and T. Stokes, ‘An invitation to C-semigroups’, Semigroup Forum 62, 279–310 (2001).
  * [13] M. Jackson and T. Stokes, ‘Agreeable semigroups’, J. Algebra 266 (2) (2003), 393–417.
  * [14] M. Kunze, ‘Zappa products’, Acta Math. Hung. 41, 225–239 (1983)
  * [15] M.V. Lawson, Semigroups and ordered categories I: the reduced case. J. Algebra 141, 422–462 (1991)
  * [16] E. Manes, ‘Guarded and Banded Semigroups’, Semigroup Forum 72, 94–120 (2006).
  * [17] B.M. Schein, ‘Restrictively multiplicative algebras of transformations’, _Izv. Vysš. Učebn. Zaved. Matematika_ 1970 (1970) no. 4 (95), 91–102 [Russian].
  * [18] B. M. Schein, On the theory of inverse semigroups and generalised groups, Amer. Math. Soc. Transl. 133 (1979), 89-122.
  * [19] T. Stokes, ‘Generalised domain and E-inverse semigroups’, Semigroup Forum 97, 32–52 (2018).
  * [20] T. Stokes, ‘How to generalise demonic composition’, Semigroup Forum Online First. DOI: 10.1007/s00233-020-10117-2.
  * [21] B. Tilson, ‘Categories as algebra: an essential ingredient in the theory of monoids’, J. Pure Appl. Algebra 48, 83–-198 (1987)
  * [22] V.S. Trokhimenko, ‘Menger’s function systems’, Izv. Vysš. Učebn. Zaved. Matematika 11 , 71–78 (1973) [Russian].
  * [23] S. Wilcox, Cellularity of diagram algebras as twisted semigroup algebras, J. Algebra 309 (1) (2007) 10–31.
  * [24] R. Zenab, Algebraic properties of Zappa–Szép products of semigroups and monoids, Semigroup Forum 96, 316-332 (2018).

Tim Stokes
Department of Mathematics
University of Waikato
Hamilton 3216
New Zealand.
email<EMAIL_ADDRESS>