2.1. Ehresmann and restriction semigroups

We now define the main objects of study of this paper. For more information, we refer the reader to the survey [Reference Gould12], see also the recent papers on the subject [Reference Branco, Gomes and Gould3–Reference Carson, Dolinka, East, Gould and Zenab5].

Definition 2.1. (Ehresmann semigroups)

A left Ehresmann semigroup is an algebra $(S; \cdot \,, ^+)$, where $(S;\cdot)$ is a semigroup and ⁺ is a unary operation satisfying the following identities:

(2.1)\begin{equation} x^+x=x, \quad (x^+y^+)^+=x^+y^+=y^+x^+, \quad (xy)^+=(xy^+)^+. \end{equation}

Dually, a right Ehresmann semigroup is an algebra $(S; \cdot \,, ^*)$, where $(S;\cdot)$ is a semigroup and $^*$ is a unary operation satisfying the following identities:

(2.2)\begin{equation} xx^*=x, \quad (x^*y^*)^*=x^*y^*=y^*x^*, \quad (xy)^*=(x^*y)^*. \end{equation}

A two-sided Ehresmann semigroup, or just an Ehresmann semigroup, is an algebra $(S; \cdot\, , ^*, ^+)$, where $(S;\cdot\, , ^+)$ is a left Ehresmann semigroup, $(S;\cdot\, , ^*)$ is a right Ehresmann semigroup and the operations $^*$ and ⁺ are connected by the following identities:

(2.3)\begin{equation}(x^+)^\ast=x^+,\hspace{1em}(x^\ast)^+=x^\ast.\end{equation}

Restriction semigroups form an important subclass of Ehresmann semigroups. They are defined as follows.

Definition 2.2. (Restriction semigroups)

A left restriction semigroup is an algebra $(S; \cdot \,, ^+)$, which is a left Ehresmann semigroup and in addition satisfies the identity

(2.4)\begin{equation} xy^+ = (xy)^+x. \end{equation}

Dually, a right restriction semigroup is an algebra $(S; \cdot \,, ^*)$, which is a right Ehresmann semigroup and in addition satisfies the identity

(2.5)\begin{equation} x^*y = y(xy)^*. \end{equation}

A two-sided restriction semigroup or just a restriction semigroup is an algebra $(S; \cdot\, , ^*, ^+)$, which is a left and a right restriction semigroup and Equation (2.3) holds.

Restriction semigroups, in turn, generalize inverse semigroups. Recall that a semigroup S is called an inverse semigroup if for each $a\in S$ there exists unique $b\in S$ such that aba = a and bab = b. The element b is called the inverse of a and is denoted by a ⁻¹. If $(S, \cdot)$ is an inverse semigroup and $a\in S$, we define $a^+=aa^{-1}$ and $a^*=a^{-1}a$. Then $(S; \cdot\, , ^*, ^+)$ is a restriction semigroup (and thus an Ehresmann semigroup).

An Ehresmann semigroup possessing an identity element is called an Ehresmann monoid.

Left Ehresmann semigroups and right Ehresmann semigroups are usually considered as $(2,1)$-algebras and Ehresmann semigroups as $(2,1,1)$-algebras. It is immediate from the definition that left Ehresmann semigroups, right Ehresmann semigroups, Ehresmann semigroups, left restriction semigroups, right restriction semigroups and restriction semigroups form varieties of algebras. Morphisms, congruences and subalgebras of all these algebras are taken with respect to their signatures.

Let S be an Ehresmann semigroup. In view of Equations (2.1), (2.2) and (2.3), the set

\begin{equation*} P(S)=\{s^*\colon s\in S\}=\{s^+\colon s\in S\} \end{equation*}

is closed with respect to the multiplication. Furthermore, it is a semilattice and $e^*=e^+=e$ holds for all $e\in P(S)$. It is called the semilattice of projections of S, and its elements are called projections. A projection is necessarily an idempotent, but an Ehresmann semigroup may contain idempotents that are not projections.

We will often use the following identities, which can be easily derived from the definitions:

(2.6)\begin{equation}\forall s\in S,e\in P(S): \hspace{1em} (se)^\ast=s^\ast e,\hspace{1em}(es)^+=es^+.\end{equation}

The next identities hold in restriction semigroups and are often called the left ample identity and the right ample identity, respectively,

(2.7)\begin{equation}\forall s\in S,e\in P(S): \hspace{1em} se=(se)^+s,\hspace{1em}es=s(es)^\ast.\end{equation}

Let S be an Ehresmann semigroup. For $a,b\in S$, we put

• • $a\leq_l b$ if there is $e\in P(S)$ such that a = eb;

• • $a\leq_r b$ if there is $e\in P(S)$ such that a = be;

• • $a\leq b$ if there are $e,f \in P(S)$ such that a = ebf.

The relations $\leq_l$, $\leq_r$ and ≤ are partial orders on S and are called the natural left partial order, the natural right partial order and the natural partial order, respectively. Clearly $\leq = \leq_l \circ \leq_r = \leq_r \circ \leq_l$, where $\circ$ stands for the product of relations. It is easy to see that $a\leq_l b$ holds if and only if $a=a^+b$ and, dually, $a\leq_r b$ holds if and only if $a=ba^*$. Restricted to P(S), all the orders coincide and $e\leq f$, where $e,f\in P(S)$, holds if and only if e = ef. In addition, P(S) is an order ideal, that is, $e\leq f$, where $f\in P(S)$, implies that $e\in P(S)$. Moreover, if S is a restriction semigroup, all the orders coincide too.

The following is an easy but useful observation.

It is easy to see that in a left Ehresmann semigroup $a\leq_l b$ implies $a^+\leq b^+$. Indeed, let $a=a^+b$. Then $a^+=(a^+b)^+=(a^+b^+)^+=a^+b^+$.

A reduced Ehresmann semigroup is an Ehresmann semigroup S for which $|P(S)|=1$. Then, necessarily, S is a monoid and $P(S)=\{1\}$ so that $s^*=s^+=1$ holds for all $s\in S$. On the other hand, any monoid S can be endowed with the structure of an Ehresmann semigroup by putting $s^*=s^+= 1$ for all $s\in S$. Hence, reduced Ehresmann semigroups can be identified with monoids.

By σ we denote the minimum congruence on an Ehresmann semigroup S that identifies all elements of P(S). Observe that if τ is a semigroup congruence that identifies all of P(S), then $a\, {\tau}\, b$ of course implies $a^+\, {\tau}\, b^+$ and $a^*\, {\tau}\, b^*$. So semigroup congruences and $(2,1,1)$-congruences identifying all the projections coincide. Thus, $S/\sigma$ is the maximum quotient of S, which is a reduced Ehresmann semigroup. The σ-class which contains $a\in S$ will be denoted by $[a]_{\sigma}$. If $a\leq b$, then clearly $a\, {\sigma}\, b$. If S is a restriction semigroup, each of the following statements is equivalent to $s\, {{\sigma}}\, t$ (see [Reference Gould13, Lemma 8.1]):

1. (i) There is $e\in P(S)$ such that es = et.

2. (ii) There is $e \in P(S)$ such that se = te.

A left (respectively, right) restriction semigroup is called proper if $a^+=b^+$ (respectively, $a^*=b^*$), and $a\, {\sigma}\, b$ imply that a = b. A restriction semigroup is proper if it is proper as a left and as a right restriction semigroup.

2.2. The monoid of binary relations on a set and its submonoids

Let X be a non-empty set. By ${\mathcal B}(X)$ we denote the monoid of binary relations on X with the operation of the composition of relations. Let $\tau\in {\mathcal B}(X)$ and $x,y\in X$. We write $x\tau = \{z\in X\colon (x,z)\in \tau\}$ and $\tau y = \{z\in X\colon (z,y)\in\tau\}$. In case where $x\tau =\{y\}$, we write $x\tau =y$, and similarly if $\tau y=\{x\}$, we write $\tau y = x$. By ${\mathrm{id}}_X=\{(x,x)\colon x\in X\}$, we denote the identity relation, and by $\varnothing$, we denote the empty relation. The reverse relation τ ⁻¹ of the relation $\tau\in {\mathcal B}(X)$ is defined by $\tau^{-1} = \{(y,x)\colon (x,y)\in \tau\}$. The partial transformation monoid ${\mathcal{PT}}(X)$ is a submonoid of the monoid ${\mathcal B}(X)$ consisting of all $\tau\in {\mathcal B}(X)$ such that $|x\tau|\leq 1$ for all $x\in X$. Let ${\mathcal{PT}}^c(X)$ be the submonoid of ${\mathcal B}(X)$ consisting of all $\tau \in {\mathcal B}(X)$ such that $|\tau y|\leq 1$ for all $y\in X$. Clearly, ${\mathcal{PT}}^c(X)$ is anti-isomorphic to ${\mathcal{PT}}(X)$ via the map $\tau\mapsto \tau^{-1}$. The symmetric inverse monoid ${\mathcal I}(X)$ equals ${\mathcal{PT}}(X)\cap {\mathcal{PT}}^c(X)$. It consists of all $\tau\in {\mathcal B}(X)$ such that $|x\tau|\leq 1$ and $|\tau x|\leq 1$ for all $x\in X$.

It is well known that ${\mathcal B}(X)$ is an Ehresmann monoid if one defines $\tau^+$ and $\tau^*$ by

\begin{equation*}\tau^+=\mathrm{dom}(\tau)=\{(x,x)\in X\times X\colon \exists y\in X\ \text{such that}\ (x,y)\in \tau\},\end{equation*}

\begin{equation*}\tau^*=\mathrm{ran}(\tau)=\{(y,y)\in X\times X\colon \exists x\in X\ \text{such that}\ (x,y)\in \tau\}.\end{equation*}

Note that $P({\mathcal B}(X)) = \{\tau\in {\mathcal B}(X)\colon \tau \subseteq id_X\}$; hence, the semilattice $P({\mathcal B}(X))$ is isomorphic to the powerset of X with respect to the operation of intersection of subsets. It follows that ${\mathcal{PT}}(X)$, ${\mathcal{PT}}^c(X)$ and ${\mathcal I}(X)$ are $(\cdot, ^+,^*,1)$-subalgebras of ${\mathcal B}(X)$. It is well known and easy to check that ${\mathcal{PT}}(X)$ is a left restriction monoid. Dually, ${\mathcal{PT}}^c(X)$ is a right restriction monoid. Furthermore, ${\mathcal{I}}(X)$ is a restriction monoid (of course, ${\mathcal{I}}(X)$ is also an inverse monoid).

In this paper, we consider ${\mathcal B}(X)$, ${\mathcal{PT}}(X)$, ${\mathcal{PT}}^c(X)$ and ${\mathcal I}(X)$ equipped with the partial order $\subseteq$ of inclusion of relations. It is known and easy to check that this partial order is compatible with the multiplication. The inclusion order on each of ${\mathcal{PT}}(X)$, ${\mathcal{PT}}^c(X)$ and ${\mathcal I}(X)$ coincides with the natural partial order. However, the inclusion order on ${\mathcal B}(X)$ contains the natural partial order ≤ but does not coincide with it. For example, if $X=\{1,2,3,4\}$, $\tau = \{(1,3), (1,4),(2,3),(2,4)\}$ and $\mu = \{(1,3), (2,4)\}$, then $\mu\subseteq \tau$, but $\mu\not\leq \tau$.

3.1. Matching factorizations

Let S be an Ehresmann semigroup.

A matching factorization of an element $s\in S$ is a tuple $(s_1,\dots, s_n)$, where $n\in {\mathbb N}$ and $s_1,\dots, s_n\in S$ are such that $s=s_1\cdots s_n$ and $s_i^* = s_{i+1}^+$ for all $i=1, \dots, n-1$. We say that a matching factorization $(s_1,\dots, s_n)$ of $s\in S$ has n factors.

We record several easy properties of matching factorizations.

3.2. Proper Ehresmann semigroups

Let S be an Ehresmann semigroup. Recall that by σ we denote the minimum congruence on S that identifies all the elements of P(S).

Definition 3.4. (Proper elements)

An element $s\in S$ will be called proper, if

\begin{equation*}\forall t\in S:\hspace{0.2em}t^+=s^+,\hspace{0.2em}t^\ast=s^\ast\hspace{0.2em}\text{and}\hspace{0.5em}t\sigma s\hspace{0.2em}\text{imply that}\hspace{0.2em}t=s.\end{equation*}

In other words, an element s is proper if it is uniquely determined by $s^+$, $s^*$ and $[s]_{\sigma}$.

If $(s_1, \dots, s_n)$ is a matching factorization where all s_i are proper (or all s_i belong to some subset Y of S, etc.), we will say that $(s_1, \ldots, s_n)$ is a matching factorization of s into a product of proper elements (respectively, into a product of elements of Y, etc.).

Let $s\in S$ and $(s_1, \ldots, s_n)$ be a matching factorization of s into a product of proper elements. If there are $i,j\in \{1,2,\dots, n\}$, where $i\leq j$ such that $s_i\cdots s_j = t$ is a proper element then $(s_1,\ldots, s_{i-1}, t, s_{j+1} ,\ldots, s_n)$ is also a matching factorization of s into a product of proper elements. In this case, we write $(s_1,\ldots, s_n) \to (s_1,\ldots, s_{i-1}, t, s_{j+1}, \ldots, s_n)$. Clearly, the relation → is reflexive. Let ≡ be its symmetric and transitive closure.

We say that two matching factorizations $(s_1,\ldots, s_n)$ and $(t_1,\ldots, t_k)$ of s into products of proper elements are equivalent if $(s_1,\ldots, s_k) \equiv (t_1,\ldots, t_k)$, that is, if the factorization $(t_1,\ldots, t_k)$ can be obtained from the factorization $(s_1,\ldots, s_k)$ by a finite number of applications of the relation → or its inverse relation.

We say that S is strictly proper if all of its elements are proper. It is easy to see that a strictly proper Ehresmann semigroup is proper (in Definition 3.5, one just takes Y = S).

It is immediate that a proper restriction semigroup S is strictly proper as an Ehresmann semigroup. It follows that proper and strictly proper Ehresmann semigroups generalize proper restriction semigroups.

3.3. Labelled directed graphs with compatible restrictions and co-restrictions and their attached categories of paths

By the label of a path in ${\mathcal G}$, we mean the product of labels of the consecutive edges of this path.

The following diagrams illustrate the operations of restriction and co-restriction.

From now till the end of this section, let E be a semilattice, T a monoid and ${\mathcal G}$ a labelled directed graph with vertex set E and edges labelled by elements T, which has compatible restrictions and co-restrictions. By ${{\mathcal C}}({\mathcal G})$ we denote the path semicategory of ${\mathcal G}$. By definition, the objects of ${{\mathcal C}}({\mathcal G})$ are elements of E, and its arrows are non-empty (labelled) directed paths in ${\mathcal G}$. If p is a path in ${\mathcal G}$ with consecutive edges $(e_0, t_1, e_1), \ldots, (e_{n-1}, t_n, e_n)$, $n\geq 1$, we sometimes denote it by $p=(e_0, t_1, e_1, \ldots, e_{n-1}, t_n, e_n)$. We say that n is the length of the path p. We put $e_0={\mathbf d}(p)$ and $e_n={\mathbf r}(p)$ to be the initial and the terminal vertices of p, respectively, and ${\mathbf l}(p) = t_1\cdots t_n$ to be the label of p. Paths p and q are composable if ${\mathbf r}(p) = {\mathbf d}(q)$, in which case their product is their concatenation, denoted pq.

We extend the definition of restriction and co-restriction from edges of ${\mathcal G}$ to non-empty directed paths in ${\mathcal G}$ recursively as follows: let $p=(e_0, t_1, e_1, \ldots, e_{n-1}, t_n, e_n)$ be a path and put $p_1=(e_0, t_1, e_1), \ldots, p_n=(e_{n-1}, t_n, e_n)$.

1. (RPath) Let $e_0^{\prime}\leq e_0$. We put $e_{1}^{\prime} = {\mathbf r}(_{e_0^{\prime}}|p_1),$ $e_{2}^{\prime} = {\mathbf r}(_{e_{1}^{\prime}}|p_{2}), \dots, e_n^{\prime} = {\mathbf r}(_{e_{n-1}^{\prime}}|p_n).$ We then define $_{e_0^{\prime}}|p = (e_0^{\prime},t_1,e_1^{\prime},t_2,e_2^{\prime},\ldots, e_{n-1}^{\prime}, t_n, e_n^{\prime})$.

2. (CRPath) Let $e_n^{\prime}\leq e_n$. We put $e_{n-1}^{\prime} = {\mathbf d}(p_n|_{e_n^{\prime}}),$ $e_{n-2}^{\prime} = {\mathbf d}(p_{n-1}|_{e_{n-1}^{\prime}}),$ $\dots,$ $e_0^{\prime} = {\mathbf d}(p_1|_{e_1^{\prime}}).$ We then define $p|_{e_n^{\prime}}= (e_0^{\prime},t_1,e_1^{\prime},t_2,e_2^{\prime},\dots, e_{n-1}^{\prime}, t_n, e_n^{\prime})$.

In the following lemma, we extend axioms (R1)–(R5), (CR1)–(CR5) and (C) from edges of ${\mathcal G}$ to non-empty paths in ${\mathcal G}$.

Remark that (R4a) and (CR4a) can be extended to products of more than two paths.

Proof. (R4a) Let $p= p_1\cdots p_k$, $q=p_{k+1}\cdots p_n$, where $p_i = (e_{i-1},t_{i}, e_i)$ for all $i=1,\dots, n$. Put $e_0^{\prime}=e$, $e_1^{\prime} = {\mathbf r}(_{e_0^{\prime}}|p_1), \dots, e_n^{\prime} = {\mathbf r}(_{e_{n-1}^{\prime}}|p_{n})$. By (RPath), we have that $_e|(pq) = (e_0^{\prime}, t_1, e_1^{\prime},\ldots, e_{n-1}^{\prime}, t_n, e_n^{\prime})$ and also

\begin{equation*} _e|p = (e_0^{\prime}, t_1, e_1^{\prime},\ldots, e_{k-1}^{\prime}, t_k, e_k^{\prime}), \qquad {}_{{\mathbf r}(_e|p)}|q = {}_{e_k^{\prime}}|q = (e_k^{\prime}, t_{k+1}, e_{k+1}^{\prime}, \ldots, e_{n-1}^{\prime}, t_n, e_n^{\prime}).\end{equation*}

The equality $_e|(pq) = {}_e|p \, {}_{{\mathbf r}(_e|p)}|q$ follows.

All other items (excluding (Ca)) can be proved easier or similarly, and we leave the details to the reader.

We finally prove (Ca). If p has length 1, then the statement holds by (C). Suppose that $n\geq 2$ and that (Ca) holds for all paths of length n − 1. Denote $p=rp_n$, where $r=(e_0,t_1,e_1,\ldots, e_{n-2}, t_{n-1}, e_{n-1})$ and $p_n = (e_{n-1}, t_n, e_n)$. Put $e_0^{\prime}=e$, $e_{n-1}^{\prime} = {\mathbf r}(_{e_0^{\prime}}|r)$ and $e_n^{\prime} = {\mathbf r}(_{e_{n-1}^{\prime}}|p_n)$. Put also $e_n^{\prime\prime} = f$ and $e_{n-1}^{\prime\prime} = {\mathbf d}(p_n|_{e_n^{\prime\prime}})$, $e_0^{\prime\prime} = {\mathbf d}(r|_{e_{n-1}^{\prime\prime}})$. Observe that ${\mathbf r}(_{e_0^{\prime}}|p) = e_n^{\prime}$. Indeed, $_{e_0^{\prime}}|p = {} _{e_0^{\prime}}|(rp_n)$, which by (R4a) equals $_{e_0^{\prime}}|r\, _{{\mathbf r}(_{e_0^{\prime}}|r)}|p_n = {}_{e_0^{\prime}}|r\, _{e_{n-1}^{\prime}}|p_n$. It follows that ${\mathbf r}(_{e_0^{\prime}}|p) = {\mathbf r}(_{e_{n-1}^{\prime}}|p_n) = e_n^{\prime}$. Similarly, we have ${\mathbf d}(p|_{e_n^{\prime\prime}}) = e_0^{\prime\prime}$. This can be illustrated with the following diagram:

Applying (C) and the inductive hypothesis, we have

(3.1)\begin{equation} (_{e_{n-1}^{\prime}}|p_n)|_{e_n^{\prime}e_n^{\prime\prime}} = {}_{e_{n-1}^{\prime}e_{n-1}^{\prime\prime}}|(p_n|_{e_n^{\prime\prime}}), \end{equation}

(3.2)\begin{equation} {}_{e_0^{\prime}e_0^{\prime\prime}}|(r|_{e_{n-1}^{\prime\prime}}) = (_{e_0^{\prime}}|r)|_{e_{n-1}^{\prime}e_{n-1}^{\prime\prime}}. \end{equation}

It follows that

\begin{align*} (_{e_0^{\prime}}|p)|_{e_n^{\prime}e_n^{\prime\prime}} & = ((_{e_0^{\prime}}|r)(_{e_{n-1}^{\prime}}|p_n))|_{e_n^{\prime}e_n^{\prime\prime}} & (\text{by (R4a)}) \\ & = (_{e_0^{\prime}}|r)|_{e_{n-1}^{\prime}e_{n-1}^{\prime\prime}} \, {}_{e_{n-1}^{\prime}e_{n-1}^{\prime\prime}}|(p_n|_{e_n^{\prime\prime}}) & (\text{by (CR4a) and}\ (3.1))\\ & = {}_{e_0^{\prime}e_0^{\prime\prime}}|(r|_{e_{n-1}^{\prime\prime}}) {}_{e_{n-1}^{\prime}e_{n-1}^{\prime\prime}}|(p_n|_{e_n^{\prime\prime}}) & (\text{by}\ (3.1))\\ & = {}_{e_0^{\prime}e_0^{\prime\prime}}|(r|_{e_{n-1}^{\prime\prime}}p_n|_{e_n^{\prime\prime}}) & (\text{by (R4a) and}\ (3.2))\\ & = {}_{e_0^{\prime}e_0^{\prime\prime}}|(p|_{e_n^{\prime\prime}}), \end{align*}

which completes the proof.

For any edges $p_1=(e_0,t_1,e_1), \dots, p_n=(e_{n-1},t_n,e_n) \in {\mathrm E}({\mathcal G})$ such that $(e_0,t_1\cdots t_n,e_n) \in {\mathrm E}({\mathcal G})$, where $n\geq 2$, we put $p_1\cdots p_n \equiv (e_0,t_1\cdots t_n,e_n)$. Note that if $p\equiv q$, then ${\mathbf d}(p) = {\mathbf d}(q)$, ${\mathbf r}(p) = {\mathbf r}(q)$. Let ∼ be the congruence on the semicategory ${{\mathcal C}}({\mathcal G})$ generated by the relation ≡. By ${{\widetilde{\mathcal C}}}({\mathcal G})$ we denote the quotient semicategory of ${{\mathcal C}}({\mathcal G})$ by ∼. For any $c\in {{\widetilde{\mathcal C}}}({\mathcal G})$, we have that ${\mathbf d}(c) = {\mathbf d}(p)$ and ${\mathbf r}(c) = {\mathbf r}(p)$, where p is an arbitrary representative of c. In addition, since $p\sim q$ implies ${\mathbf l}(p) = {\mathbf l}(q)$, for any $c\in {{\widetilde{\mathcal C}}}({\mathcal G})$, we can define ${\mathbf l}(c)$ to be equal to ${\mathbf l}(p)$, where p is an arbitrary representative of c. For $p\in {{\mathcal C}}({\mathcal G})$ by $[p]$, we denote the ∼-class that contains p. Observe that ${{\widetilde{\mathcal C}}}({\mathcal G})$ is in fact a category. Indeed, if e is a vertex of ${\mathcal G}$, then $[(e,1,e)]\in {{\widetilde{\mathcal C}}}({\mathcal G})$ is the identity morphism at e in ${{\widetilde{\mathcal C}}}({\mathcal G})$.

Proof. It is enough to assume that $p=ap_1\cdots p_nb$, where $n\geq 2$, $p_i=(e_{i-1}, t_i, e_i)$, $i\in \{1,\ldots, n\}$, and $q= a(e_0, t_1\cdots t_n, e_n)b$, $a,b\in {{\mathcal C}}({\mathcal G})$. Let $h= {\mathbf r}(_e|a)$. Then

\begin{equation*}_e|p = {}_e|a \, {}_h|(p_1\cdots p_nb) \quad \text{and } \quad _e|q = {}_e|a \, {}_h|((e_0, t_1\cdots t_n, e_n)b)\end{equation*}

by (R4a). Hence, it suffices to show that $_h|(p_1\cdots p_nb) \sim {}_h|((e_0, t_1\cdots t_n, e_n)b)$. By the definition of ∼, we have $p_1\cdots p_n \sim (e_0, t_1\cdots t_n, e_n)$, thus, applying (R4) and (RPath), also $_h|(p_1\cdots p_n)\sim {}_h|(e_0, t_1\cdots t_n, e_n)$. Let $h^{\prime}={\mathbf r}(_h|(p_1\dots p_n)) = {\mathbf r}(_h|(e_0, t_1\cdots t_n, e_n))$. Then

\begin{equation*}_h|(p_1\cdots p_nb) = {}_h|(p_1\dots p_n)\, _{h^{\prime}}|b \sim {}_h|(e_0, t_1\cdots t_n, e_n)\,_{h^{\prime}}|b = {}_h|((e_0, t_1\cdots t_n, e_n)b),\end{equation*}

as needed.

For $p|_f\sim q|_f$, the proof is similar.

It follows that for $c\in {{\widetilde{\mathcal C}}}({\mathcal G})$ and $e\leq {\mathbf d}(c), f\leq {\mathbf r}(c)$, we can define the restriction of c to e by $_e|c = [_e|p]$ and the co-restriction of c to f by $c|_f=[p|_f]$, where p is an arbitrary representative of c.

The following is an analogue of Lemma 3.8 for ${{\widetilde{\mathcal C}}}({\mathcal G})$.

Proof. The proofs follow from (R1a)–(R5a), (CR1a)–(CR5a) and (Ca) using the definition of restriction and co-restriction in ${{\widetilde{\mathcal C}}}({\mathcal G})$. We prove, for example, (R4b): Let $q\in cd$. Then $q=pp^{\prime}$, where $p\in c$ and $p^{\prime}\in d$. We have

\begin{equation*}_e|(cd) = {}_e|([pp^{\prime}]) = [{}_e|(pp^{\prime})] = [{}_e|p \, {}_{{\mathbf r}(_e|p)}|p^{\prime}] = [{}_e|p] [{}_{{\mathbf r}(_e|p)}|p^{\prime}] = {}_e|[p] \, {}_{{\mathbf r}(_e|p)}|[p^{\prime}] = {}_e|c \, {}_{{\mathbf r}(_e|c)}|d,\end{equation*}

as needed. All other items are proved similarly.

3.4. From a labelled directed graph with compatible restrictions and co-restrictions to a proper Ehresmann semigroup

Let T be a monoid, E a semilattice and ${\mathcal G}$ a labelled directed graph with the vertex set E and edges labelled by elements of T, which has compatible restrictions and co-restrictions (see Definition 3.7).

Let $E\rtimes_{\mathcal G} T$ be the set which coincides with the underlying set of the category ${{\widetilde{\mathcal C}}}({\mathcal G})$. On this set, we define the operations ·, ⁺ and $^*$ as follows:

(3.3)\begin{equation}\forall c,d\in E\rtimes_{\mathcal G}T: \hspace{0.2em} {}cd=c\vert_{\mathbf r(c)\mathbf d(d)}{}{}_{\mathbf r(c)\mathbf d(d)}\vert d,\end{equation}

(3.4)\begin{equation}\forall c\in E\rtimes_{\mathcal G}T: \hspace{0.5em} c^+=\lbrack(\mathbf d(c),1,\mathbf d(c))\rbrack\hspace{0.5em}\text{and}\hspace{0.5em}c^\ast=\lbrack(\mathbf r(c),1,\mathbf r(c))\rbrack.\end{equation}

Remark that in (4) above and in what follows the symbol ≤ denotes both the natural partial order on $E\rtimes_{\mathcal G} T$ and also the order on the semilattice E. It is always clear from the context which of these two orders is being used.

Proof. (1) We start from showing that the multiplication · is associative. Let $a, b,c\in E\rtimes_{\mathcal G} T$. Denote $f= {\mathbf r}(a)$, $g={\mathbf d}(b)$, $h={\mathbf r}(b)$ and $e={\mathbf d}(c)$. Let further $m=f{\mathbf d}(b|_{he})$ and $k={\mathbf r}(_{fg}|b)e$. For convenience, in this proof, we denote the multiplication in the category ${{\widetilde{\mathcal C}}}({\mathcal G})$ by $\circ$. We calculate

\begin{align*} (a\cdot b)\cdot c & = (a|_{fg} \circ \space{}_{fg}|b)\cdot c & (\text{by the definition of}\ \cdot)\\ & = \left(\left(a|_{fg}\circ \space{}_{fg}|b\right)|_{k}\right) \circ \space{}_{k}|c & (\text{by the definition of}\ \cdot)\\ & = \left((a|_{fg})|_{{\mathbf{d}}\left((_{fg}|b)|_{k}\right)} \circ (_{fg}|b)|_{k}\right) \circ \space{}_{k}|c & ( \text{by (CR4b)})\\ & = \left(a|_{{\mathbf{d}}\left((_{fg}|b)|_{k}\right)} \circ (_{fg}|b)|_{k}\right) \circ \space{}_{k}|c & ( \text{by (CR3b)})\\ & = a|_{{\mathbf{d}}\left((_{fg}|b)|_{k}\right)} \circ \left((_{fg}|b)|_{k} \circ \space{}_{k}|c \right). & ( \text{since } \circ \text{is associative}) \end{align*}

Denote $a^{\prime}= a|_{{\mathbf{d}}\left((_{fg}|b)|_{k}\right)}$, $b^{\prime}=(_{fg}|b)|_{k}$ and $c^{\prime}={}_{k}|c$. On the other hand, we have

\begin{align*} a\cdot (b\cdot c) & = a\cdot \left( b|_{he}\circ \space{}_{he}|c\right) & (\text{by the definition of}\ \cdot) \\ &= a|_{m} \circ \space{}_m|\left(b|_{he}\circ \space{}_{he}|c\right) & (\text{by the definition of}\ \cdot)\\ & = a|_{m} \circ \left(\space{}_m|(b|_{he})\circ \space{}_{{\mathbf{r}}(_m|(b|_{he}))}|c\right). & (\text{by (R4b) and (R3b)}) \end{align*}

Denote $a^{\prime\prime} = a|_{m}$, $b^{\prime\prime}={}_m|(b|_{he})$, $c^{\prime\prime} = {}_{{\mathbf{r}}(_m|(b|_{he}))}|c$. Observe that

\begin{align*} {{b^{\prime}}} & = {(_{fg}}|b){|_{{\mathbf{r}}{(_{fg}}|b)e}} & \\ & = {(_{fg}}|b){|_{{\mathbf{r}}{(_{fg}}|b)he}} & ({\text{since}}\,{\mathbf{r}}{(_{fg}}|b) \leq h{\text{by (CR1b)}}) \\ & = {_{{\mathbf{d}}(b{|_{he}})fg}}|(b{|_{he}})& ({\text{by (Cb)}}) \\ & = {_{{\mathbf{d}}(b{|_{he}})f}}|(b{|_{he}}) & ({\text{since}}\,{\mathbf{d}}(b{|_{he}}) \leq g{\text{by (CR1b)}}) \\ & = {{b^{\prime\prime}}} & \end{align*}

It follows that ${\mathbf{d}}((_{fg}|b)|_{k}) = {\mathbf d}(b^{\prime})={\mathbf d}(b^{\prime\prime}) = m$ and similarly ${{\mathbf{r}}(_m|(b|_{he}))} = k$. Hence, $a^{\prime}= a|_{{\mathbf{d}}\left((_{fg}|b)|_{k}\right)} = a|_m = a^{\prime\prime}$ and similarly $c^{\prime}=c^{\prime\prime}$. Thus, $(a\cdot b)\cdot c = a^{\prime}\circ (b^{\prime}\circ c^{\prime}) = a^{\prime\prime}\circ (b^{\prime\prime}\circ c^{\prime\prime}) = a\cdot (b\cdot c)$.

Let $a\in E\rtimes_{\mathcal G} T$. Applying the definition of ·, (R2b) and (CR2b), we have

\begin{equation*}a\cdot a^* = a\cdot [({\mathbf r}(a),1,{\mathbf r}(a))] = a|_{{\mathbf r}(a)} \circ {}_{{\mathbf r}(a)}|[({\mathbf r}(a),1,{\mathbf r}(a))] = a \circ [({\mathbf r}(a),1,{\mathbf r}(a))] = a.\end{equation*}

Hence, $a\cdot a^* = a$.

Let $a,b\in E\rtimes_{\mathcal G} T$. Put $f={\mathbf r}(a)$, $g={\mathbf r}(b)$. Then applying (R5b) and (CR5b), we have

\begin{align*}a^*\cdot b^* = [(f,1,f)] \cdot [(g,1,g)] & = [(f,1,f)]|_{fg}\circ \space{}_{fg}|[(g,1,g)] \\ & = [(fg,1,fg)]\circ [(fg,1,fg)] = [(fg,1,fg)^2] = [(fg,1,fg)]. \end{align*}

It follows that $(a^*\cdot b^*)^*=a^*\cdot b^* = b^*\cdot a^*$ holds.

Let $a, b\in E\rtimes_{\mathcal G} T$. Put $f={\mathbf r}(a)$, $g={\mathbf d}(b)$. Then $(a\cdot b)^* = (a|_{fg} \circ\space{}_{fg}|b)^* = [({\mathbf r}(_{fg}|b),1,{\mathbf r}(_{fg}|b))]$ and $(a^*\cdot b)^* = ([(f,1,f)]|_{fg} \circ {} _{fg}|b)^* = [({\mathbf r}(_{fg}|b),1,{\mathbf r}(_{fg}|b))]$. It follows that $(a\cdot b)^* = (a^*\cdot b)^*$.

We have verified that $(E\rtimes_{\mathcal G} T, \cdot, ^*)$ is a right Ehresmann semigroup. Dually, it follows that $(T\rtimes_{\mathcal G} E, \cdot, ^+)$ is a left Ehresmann semigroup. In addition, it is easy to see that $(a^*)^+ = a^*$ and $(a^+)^* = a^+$ for all $a\in E\rtimes_{\mathcal G} T$. Therefore, $(E\rtimes_{\mathcal G} T, \cdot, ^+, ^*)$ is an Ehresmann semigroup.

(2) Let $a\in E\rtimes_{\mathcal G} T$ be a projection. Then $a=a^+=[(\textbf{d}(a),1, \textbf{d}(a))]$ and also clearly any $[(e,1,e)]$, $e\in E$, is a projection. Now, since $[(e,1,e)]\cdot [(f,1,f)] = [(ef,1,ef)]$, it follows that $P(E\rtimes_{\mathcal G} T)$ is a semilattice and the map $[(e,1,e)]\to e$ is an isomorphism of semilattices. By Lemma 2.3, $E\rtimes_{\mathcal G} T$ is a monoid if and only if it has a maximum projection. As we have shown, this is the case if and only if E has a maximum element.

(3) Let $\varphi\colon E\rtimes_{\mathcal G} T\to T$ be the map given by $a\mapsto {\mathbf l}(a)$, where T is a reduced Ehresmann semigroup. It is easy to see that it is a $(2,1,1)$-morphism. Note that φ is surjective because for every $t\in T$, there is a path in ${\mathcal G}$ labelled by t. So T is a reduced quotient of $E\rtimes_{\mathcal G} T$. Hence, T is a quotient of $(E\rtimes_{\mathcal G} T)/\sigma$. It follows that $a {\sigma} b$ implies that $\varphi(a)=\varphi(b)$, that is, ${\mathbf l}(a) = {\mathbf l}(b)$, which proves (3).

(4) Let $c,d \in E\rtimes_{\mathcal G} T$ be such that $c\leq_l d$. This means that there is a projection $[(e,1,e)]$ such that $c=[(e,1,e)]\cdot d$. Applying Equation (3.3) and (CR5b), this is equivalent to $c =[(e\textbf{d}(d),1,e\textbf{d}(d))] \circ {}_{e\textbf{d}(d)}|d = {}_{e\textbf{d}(d)}|d$. The statement for $\leq_r$ is dual, and the statement for ≤ follows from those for $\leq_l$ and $\leq_r$.

(5) Suppose that $c {\sigma} d$ holds if and only if ${\mathbf l}(c) = {\mathbf l}(d)$ for all $c, d\in E\rtimes_{\mathcal G} T$. It follows from (4) that $Y=\{[(e,s,f)]\colon (e,s,f)\in {\mathrm E}({\mathcal G})\}$ is an order ideal of $E\rtimes_{\mathcal G} T$ with respect to the natural partial order.

If $c= [(e,s,f)], d=[(g,t,h)]\in Y$ are such that $c^+=d^+$, $c^*=d^*$ and $c\,\sigma\,d$, then, clearly, $s = {\mathbf l}(c) = {\mathbf l}(d) = t$ and also e = g and f = h, so c = d. It follows that all elements of Y are proper. In addition, Y contains all the projections of $E\rtimes_{\mathcal G} T$, by the definition of ${\mathcal G}$.

Now each element of $E\rtimes_{\mathcal G} T$ decomposes as a matching product of elements of Y, and, moreover, the definition of ∼ yields that such a factorization is unique up to equivalence. Therefore, the Ehresmann semigroup $E\rtimes_{\mathcal G} T$ is proper. By the assumption, the map $(E\rtimes_{\mathcal G} T)/\sigma \to T$ given by $[a]_\sigma \mapsto {\mathbf l}(a)$ is well defined and injective. Since for every $t\in T$, there is a path in ${\mathcal G}$ labelled by t, this map is surjective. It is also a monoid homomorphism, and thus an isomorphism. Hence, $(E\rtimes_{\mathcal G} T)/\sigma \simeq T$.

In what follows, the multiplication in $E\rtimes_{\mathcal G} T$ will be often denoted by juxtaposition.

Since $E\rtimes_{\mathcal G} T$ and ${{\widetilde{\mathcal C}}}({\mathcal G})$ have the same underlying set, the relations $\leq_l$, $\leq_r$ and ≤ are also partial orders on the category ${{\widetilde{\mathcal C}}}({\mathcal G})$. It is routine to show that, equipped with $\leq_l$ and $\leq_r$, the category ${{\widetilde{\mathcal C}}}({\mathcal G})$ is an Ehresmann category in the sense of Lawson [Reference Lawson22]. After this, the fact that $E\rtimes_{\mathcal G} T$ is an Ehresmann semigroup becomes also a consequence of [Reference Lawson22, Theorem 4.21].

Observe that the partial orders $\leq_l$ and $\leq_r$ can be defined already on ${\mathrm{E}}({\mathcal G})$ by $u \leq_l v$ if there is some $e\leq {\mathbf d}(v)$ such that $u={}_e|v$ and $u\leq_r v$ if there is some $f\leq {\mathbf r}(v)$ such that $u=v|_f$. Using (C), one can see that $\leq_l \circ \leq_r = \leq_r \circ \leq_l$, denote this relation by ≤. Clearly, $u\leq_l v$ (respectively, $u\leq_r v$ or $u\leq v$) in $E(\mathcal{G})$ implies $[u]\leq [v]$ (respectively, $[u]\leq_r [v]$ or $[u]\leq [v]$) in $\widetilde{\mathcal{C}}(\mathcal{G})$.

We now single out a special case for which the assumption of Theorem 3.11(5) holds.

3.5. The structure theorem

Let S be a proper Ehresmann semigroup and Y be a proper generating ideal of S (see Definition 3.5). Denote $T=S/\sigma$ and recall that for $a\in S$ by $[a]_{\sigma}\in T$, we denote the σ-class of a. The underlying graph ${\mathcal G}_{S,Y}$ of S with respect to Y is the labelled directed graph defined as follows. Vertices of ${\mathcal G}_{S,Y}$ are elements of P(S), and for all $e,f\in P(S)$, edges of ${\mathcal G}_{S,Y}$ from e to f are triples $(e,t,f)$, where $t\in T$ and there is a (necessarily unique) $a\in Y$ such that $e=a^+$, $f=a^*$ and $t=[a]_\sigma$. It is immediate that $a\mapsto (a^+,[a]_{\sigma},a^*)$ is a bijection between Y and edges of ${\mathcal G}_{S,Y}$.

Let $p=(e,t,f)\in {\mathrm E}({\mathcal G}_{S,Y})$ and let $a\in Y$ be such that $p=(a^+,[a]_{\sigma},a^*)$. For a projection $g\leq e$, we define the restriction $_g|p$ of p to g by

(3.5)\begin{equation} _g|p = ((ga)^+, [ga]_{\sigma}, (ga)^*) = (g, [a]_{\sigma}, (ga)^*). \end{equation}

Similarly, for $h\leq f$, we define the co-restriction $p|_h$ of p to h

(3.6)\begin{equation} p|_h = ((ah)^+, [ah]_{\sigma}, (ah)^*) = ((ah)^+, [a]_{\sigma}, h). \end{equation}

These are well defined since $ga, ah\leq a$ and Y is an order ideal.

Proof. Since $P(S)\subseteq Y$ and by the definition of ${\mathcal G}_{S,Y}$, we have that for every $e\in P(S)$, the graph ${\mathcal G}_{S,Y}$ has an edge $(e,1,e)$. In addition, for each $t\in S/\sigma$, the graph ${\mathcal G}_{S,Y}$ has a path labelled by t.

Let $p=(a^+,[a]_{\sigma},a^*)\in {\mathrm E}({\mathcal G}_{S,Y})$ and $g\leq a^+$. Then $_g|p = (g, [a]_{\sigma}, (ga)^*)$, and since $(ga)^*a^*=(gaa^*)^* = (ga)^*$, we have $(ga)^*\leq a^*$ so that (R1) holds.

Let $p=(a^+,[a]_{\sigma},a^*)\in {\mathrm E}({\mathcal G}_{S,Y})$. Then $_{a^+}|p = (a^+, [a]_{\sigma}, (a^+a)^*)= p$, so that (R2) holds.

Let us verify that condition (R3) holds. Let $h\leq g\leq a^+$. Then

\begin{equation*} _h|(_g|p) = \space{}_h|((ga)^+,[ga]_{\sigma},(ga)^*) = ((hga)^+, [hga]_{\sigma}, (hga)^*) = ((ha)^+, [ha]_{\sigma}, (ha)^*) = \space{}_h|p, \end{equation*}

as needed.

To show (R4), let $p_1=(a_1^+,[a_1]_{\sigma},a_1^*), \dots, p_n=(a_n^+,[a_n]_{\sigma},a_n^*) \in {\mathrm E}({\mathcal G}_{S,Y})$, where $a_i^*=a_{i+1}^+$ for all $i=1,\dots, n-1$ be such that $(a_1^+,[a_1\cdots a_n]_{\sigma}, a_n^*) \in {\mathrm E}({\mathcal G}_{S,Y})$ where $n\geq 2$. Put $e_0 = a_1^+$ and let $e_0^{\prime}\leq e_0$. Define $e_{1}^{\prime} = {\mathbf r}(_{e_0^{\prime}}|p_1)=(e_0^{\prime}a_1)^*$, $e_{2}^{\prime} = {\mathbf r}(_{e_{1}^{\prime}}|p_{2})=((e_0^{\prime}a_1)^*a_2)^* = (e_0^{\prime}a_1a_2)^*, \dots, e_n^{\prime} = {\mathbf r}(_{e_{n-1}^{\prime}}|p_n)=((e_0^{\prime}a_1\cdots a_{n-1})^*a_n)^* = (e_0^{\prime}a_1\cdots a_{n-1}a_n)^*$. Now

\begin{equation*}_{e_0^{\prime}}|(a_1^+,[a_1\cdots a_n]_{\sigma}, a_n^*)=(e_0^{\prime}, [a_1]_{\sigma}\cdots [a_n]_{\sigma}, (e_0^{\prime}a_1\cdots a_{n-1}a_n)^*) = (e_0^{\prime}, [a_1]_{\sigma}\cdots [a_n]_{\sigma}, e_n^{\prime}),\end{equation*}

as needed.

If $e,f\in P(S)$ are such that $f\leq e$, then we have

\begin{equation*}_f|(e,1,e) = {}_f|(e^+,[e]_{\sigma},e^*) = (f,[e]_{\sigma},(ef)^*) = (f,1,f),\end{equation*}

so that (R5) holds.

Axioms (CR1)–(CR5) follow dually.

We finally verify axiom (C). Let $p=(a^+,[a]_{\sigma},a^*)\in {\mathcal G}_{S,Y}$ and $g\leq a^+$, $h\leq a^*$. We calculate

\begin{align*} (_g|p)|_{{\mathbf r}(_g|p)h} & = ((ga)^+, [a]_{\sigma}, (ga)^*)|_{(ga)^*h} & (\text{by}\ (3.5))\\ & = ((ga(ga)^*h)^+, [a]_{\sigma}, (ga)^*h) & (\text{by}\ (3.6))\\ & = ((gah)^+, [a]_{\sigma}, (ga)^*h) & (\text{by}\ (2.2)) \\ & = (g(ah)^+, [a]_{\sigma}, (ga)^*h) & (\text{by}\ (2.6)) \\ & = (g{\mathbf d}(p|_h), [a]_{\sigma}, {\mathbf r}(_g|p)h). & (\text{by}\ (3.5)\ \text{and}\ (3.6)) \end{align*}

The equality $_{{\mathbf d}(p|_h)g}|(p|_h) = (g{\mathbf d}(p|_h), [a]_{\sigma}, {\mathbf r}(_g|p)h)$ follows dually.

Therefore, we can construct the Ehresmann semigroup $P(S) \rtimes_{{\mathcal G}_{S,Y}} S/\sigma$.

The following theorem describes the structure of proper Ehresmann semigroups in terms of labelled directed graphs with compatible restrictions and co-restrictions. We will show in § 6 that this result generalizes the structure result on proper restriction semigroups in terms of partial actions [Reference Cornock and Gould6, Reference Kudryavtseva19] and is thus a wide-ranging extension of the McAlister theorem on the structure of E-unitary inverse semigroups, formulated in terms of partial actions [Reference Kellendonk and Lawson18, Reference Petrich and Reilly31].

Proof. Let $a\in S$ and let $(a_1,\dots, a_n)$ be a matching factorization of a into a product of elements of Y. We define $(a_1,\dots, a_n)\overline{\Psi}= (a_1^+, [a_1]_{\sigma}, a_2^+, [a_2]_{\sigma}, \ldots, a_{n}^+, [a_n]_{\sigma}, a_n^*) \in {\mathcal C}({\mathcal G}_{S,Y})$. Suppose that $t=a_ia_{i+1}\cdots a_j\in Y$, where $1\leq i \lt j \leq n$ and let $(a_1,\dots, a_{i-1},t, a_{j+1},\dots, a_n)$ be the matching factorization of a into a product of elements of Y obtained by the replacement of $(a_i,a_{i+1},\dots, a_j)$ with t. The definition of the congruence ∼ on ${\mathcal C}({\mathcal G}_{S,Y})$ yields that $(a_1,\ldots, a_{i-1},t,a_{j+1},\ldots, a_n)\overline{\Psi} \sim (a_1,\dots, a_n)\overline{\Psi}$. It follows that $\overline{\Psi}$ maps equivalent matching factorizations of a into products of elements of Y to equivalent paths in ${\mathcal C}({\mathcal G}_{S,Y})$. Therefore, we can define the map $\Psi\colon S\to P(S) \rtimes_{{\mathcal G}_{S,Y}} S/\sigma$ by

\begin{equation*}a\Psi = [(a_1^+, [a_1]_{\sigma}, a_2^+, [a_2]_{\sigma}, \ldots, a_{n}^+, [a_n]_{\sigma}, a_n^*)],\end{equation*}

where $(a_1,\ldots, a_n)$ is a matching factorization of a into a product of elements of Y.

It is immediate from the definitions that Ψ is a bijection. Let us show that it preserves the multiplication. Let $a,b\in S$ and let $(a_1,\ldots, a_n)$ and $(b_1,\ldots, b_m)$ be matching factorizations of a and b into products of elements of Y. Let $a_{n}^{\prime} = a_nb_1^+$, $a_{n-1}^{\prime} = a_{n-1}(a_{n}^{\prime})^+$, $\dots$, $a_1^{\prime} = a_1(a_{2}^{\prime})^+$ and $b_1^{\prime} = a_n^* b_1$, $b_2^{\prime} = (b_1^{\prime})^*b_2$, $\ldots$, $b_m^{\prime} = (b_{m-1}^{\prime})^* b_m$. Note that $(a^{\prime}_n)^* = (a_nb_1^+)^* = a_n^*b_1^+ = (a_n^*b_1)^+ = (b^{\prime}_1)^+$. By Lemma 3.2 and its dual, we see that $(a_1^{\prime},\ldots, a_n^{\prime},b_1^{\prime},\ldots, b_m^{\prime})$ is a matching factorization of ab into a product of elements of Y, thus

\begin{equation*} (ab)\Psi = [((a_1^{\prime})^+, [a_1]_{\sigma}, \ldots, (a_{n}^{\prime})^+, [a_n]_{\sigma}, (a_n^{\prime})^*, [b_1]_{\sigma}, (b_1^{\prime})^*, \ldots, [b_m]_{\sigma}, (b_m^{\prime})^*)]. \end{equation*}

From Equation (3.3), we have that

\begin{equation*} (a\Psi) (b\Psi) = [(a_1^+, [a_1]_{\sigma}, \ldots, a_{n}^+,[a_n]_{\sigma}, a_n^*)]|_{a_n^*b_1^+} {}_{a_n^*b_1^+}| [(b_1^+, [b_1]_{\sigma},\ldots, b_m^+, [b_m]_{\sigma}, b_m^*)] , \end{equation*}

which, in view of Equations (3.5), (RPath) and (CRPath), equals

\begin{equation*} [((a_1^{\prime})^+, [a_1]_{\sigma}, \ldots, (a_{n}^{\prime})^+, [a_n]_{\sigma}, (a_n^{\prime})^*][((b_1^{\prime})^+, [b_1]_{\sigma}, (b_1^{\prime})^*, \ldots, [b_m]_{\sigma}, (b_m^{\prime})^*)] = (ab)\Psi. \end{equation*}

Let $(a_1,\ldots, a_n)$ be a matching factorization of a into a product of elements of Y. Then,

\begin{equation*} (a^+)\Psi = (a_1^+)\Psi = [(a_1^+,[a_1^+]_{\sigma},a_1^+)] = [(a_1^+, [a_1]_{\sigma}, a_2^+, [a_2], \ldots, [a_n]_{\sigma}, a_n^*)]^+ = (a\Psi)^+. \end{equation*}

It follows that Ψ preserves the operation +. Dually, it also preserves $*$. Hence, Ψ is a $(2,1,1)$-isomorphism.

Combining Theorems 3.11 and 3.14, we obtain the following result.

6.1. Partial multiactions of monoids on sets

The identity arrow of ${\mathcal G}$ at x is $(x,1,x)$. We have ${\mathbf d}(x,t,y) = x$ and ${\mathbf r}(x,t,y) = y$.

Remark 6.2. Recall [Reference Lawson24] that the Cauchy completion of a semigroup S is the category

\begin{equation*}C(S) = \{(e, s, f )\in E(S) \times S \times E(S)\colon esf = s\},\end{equation*}

with the composition rule $(e,s,f)(f,t,g)=(e, st,g)$. If we extend the definition of a partial multiaction from monoids to semigroups by requiring that (PM) holds, then C(S) becomes an example of a partial multiaction of the semigroup S with $X=E(S)$.

Let us show that the notion of a partial multiaction of T on X subsumes those of both left and right partial actions of T on X. Recall that a right partial action of T on X is a partially defined map $X\times T \to X$, $(x,t)\mapsto x\cdot t$, such that for every $t\in T$, there is $x\in X$ such that $x\cdot t$ is defined and

1. (i) if $x\cdot s$ and $(x\cdot s)\cdot t$ are defined, then $x\cdot st$ is defined and $(x\cdot s)\cdot t=x\cdot st$.

2. (ii) for all $x\in X$, we have that $x\cdot 1$ is defined and $x\cdot 1 =x$.

Left partial actions of T on X are defined dually.

Suppose that the (partially defined) assignment $(x,t)\mapsto x\cdot t$ defines a right partial action of T on X and define ${\mathcal G}$ to be the labelled directed graph with vertex set X, edges labelled by elements of T and ${\mathrm{E}}({\mathcal G}) = \{(x,t,x\cdot t) \colon x\cdot t\ \text{is defined}\}$. Then ${\mathcal G}$ is a partial multiaction of T on X and also satisfies the following condition:

1. (LD) (Left determinism) For all $t\in T$ and $x\in X$, there exists at most one $y\in X$ such that $(x,t,y)\in {\mathrm{E}}({\mathcal G})$.

In this way, right partial actions of T on X are in a bijective correspondence with partial multiactions of T on X, which satisfy condition (LD). Dually, given a left partial action $(t,x)\mapsto t\cdot x$ of T on X, we define ${\mathcal G}$ to be the labelled directed graph with vertex set X, edges labelled by elements of T and ${\mathrm{E}}({\mathcal G}) = \{(t\cdot x,t,x) \colon t\cdot x \ \text{is defined}\}$. Then ${\mathcal G}$ is a partial multiaction of T on X and also satisfies the following condition:

1. (RD) (Right determinism) For all $t\in T$ and $y\in X$, there exists at most one $x\in X$ such that $(x,t,y)\in {\mathrm{E}}({\mathcal G})$.

Hence, left partial acitons of T on X are in a bijective correspondence with partial multiactions of T on X, which satisfy condition (RD).

6.2. Partial multiactions and premorphisms

We now introduce the notion of a premorphism from a monoid T to the monoid ${\mathcal B}(X)$ and relate it with the notion of a partial multiaction of T on X.

We call a partial multiaction ${\mathcal{G}}$ and the premorphism φ defined in Proposition 6.4(1) attached to each other.

Observe that if ${\mathcal G}$ satisfies condition (LD), then for its attached premorphism $\varphi\colon T\to {\mathcal B}(X)$, condition (Prem1) reduces to $\varphi_1={\mathrm{id}}_X$. In addition, we have $\varphi_s\subseteq \varphi_t$ if and only $\varphi_s\leq \varphi_t$, where ≤ is the natural partial order on ${\mathcal{PT}}(X)$. This leads to the following corollary of Proposition 6.4.

6.3. Partial multiactions of monoids on semilattices with compatible restrictions and co-restrictions

Let T be a monoid, E a semilattice and ${\mathcal G}$ a labelled directed graph with compatible restrictions and co-restrictions (see Definition 3.7). In this subsection, we additionally suppose that ${\mathcal G}$ is a partial multiaction of T on E (see Definition 6.1). This means that if $(e,t,f), (f,s,g)\in {\mathrm{E}}({\mathcal G})$, then $(e,ts,g)\in {\mathrm{E}}({\mathcal G})$. We then call the category ${\mathcal G}$ a partial multiaction of T on E with compatible restrictions and co-restrictions. Note that every ≡-class of the path semicategory ${\mathcal C}(\mathcal G)$ contains a unique path of length 1, which is an edge of ${\mathcal G}$. It follows that the category ${{\widetilde{\mathcal C}}}({\mathcal G})$ is isomorphic to ${\mathcal G}$ via the identity map on objects and the map $[(e,t,f)]\mapsto (e,t,f)$ on the arrows. From now on, we identify ${{\widetilde{\mathcal C}}}({\mathcal G})$ with ${\mathcal G}$. In particular, the underlying set of the Ehresmann semigroup $E\rtimes_{\mathcal G} T$ coincides with ${\mathrm{E}}({\mathcal G})$.

For a strictly proper Ehresmann semigroup S, we put ${\mathcal G}_S$ to be the underlying graph ${\mathcal G}_{S,S}$ of S with respect to the proper generating ideal S. Applying Theorem 3.11(5), we obtain the following statement.

6.4. Strictly proper Ehresmann semigroups arising from deterministic partial multiactions

Let ${\mathcal G}$ be a partial multiaction of a monoid T on a semilattice E with compatible restrictions and co-restrictions.

We now demonstrate that proper left (respectively, right) restriction Ehresmann semigroups arise from partial multiactions of monoids on semilattices with compatible restrictions and co-restrictions that satisfy condition (LD) (respectively, condition (RD)).

Proof. We consider only the case of condition (LD), the case with (RD) is dual, and the third case follows from the first two. From Lemma 6.8, it follows that the Ehresmann semigroup $E\rtimes_{\mathcal G} T$ is strictly proper with $(E\rtimes_{\mathcal G} T)/\sigma \simeq T$ via the map $[(e,s,f)]_{\sigma}\mapsto s$. We verify that $E\rtimes_{\mathcal G} T$ satisfies the left ample identity given in Equation (2.7). Let $a = (e,s,h)$ and $f=(g,1,g)$. Then by Equations (3.3) and (R5), we have $a\cdot f = (e,s,h)\cdot (g,1,g) = (e,s,h)|_{hg} \, {}_{hg}|(g,1,g)= (e^{\prime},s,hg) (hg,1,hg)=(e^{\prime},s,hg)$, where $e^{\prime} = {\mathbf d}((e,s,h)|_{hg})$. Hence, $(a\cdot f)^+ = (e^{\prime},1,e^{\prime})$ and

\begin{equation*} (a\cdot f)^+\cdot a = (e^{\prime},1,e^{\prime})\cdot (e,s,h) = \space{}_{e^{\prime}}|(e,s,h)=(e^{\prime}, s, h^{\prime}), \end{equation*}

where $h^{\prime}\leq h$ and for the last equality we applied (R1). Since $(e^{\prime},s, hg), (e^{\prime},s, h^{\prime}) \in {\mathrm{E}}({\mathcal G})$, condition (LD) yields $h^{\prime}=hg$. This implies that $a\cdot f = (a\cdot f)^+\cdot a$, as needed. We finally show that $E\rtimes_{\mathcal G} T$ is a proper left restriction semigroup. Assume that $a,b\in E\rtimes_{\mathcal G} T$ are such that $a^+=b^+$ and $a{\sigma} b$. This means that $a=(e,s,f)$ and $b=(e,s,g)$ for some $e,f,g\in E$ and $s\in T$. Condition (LD) now yields that f = g, that is, a = b.

The following statement shows that strictly proper Ehresmann semigroups generalize Ehresmann semigroups, which are proper left (or right) restriction, and they also generalize proper restriction semigroups. It follows directly from the definition of properness.

We now determine when an Ehresmann semigroup is proper left restriction (respectively, proper right restriction, or proper restriction).

As a corollary, we obtain a structure result for Ehresmann semigroups, which are proper left restriction (or proper right restriction) and of proper restriction semigroups.

6.5. The structure of proper restriction semigroups

In this subsection, we show that the known result on the structure of proper restriction semigroups [Reference Cornock and Gould6, Reference Kudryavtseva19] is equivalent to Corollary 6.12(2); thus, it can be recovered as a special case of Theorem 3.14.

For a semilattice E, let $\Sigma(E)$ be the inverse semigroup of all order isomorphisms between order ideals of E [Reference Petrich30, VI.7.1].

Let S be a proper restriction semigroup. Denote $T=S/\sigma$. Let $\varphi\colon T\to {\mathcal B}(P(S))$ be the premorphism attached to the partial multiaction ${\mathcal G}_S$. It follows from Theorem 6.11 that $\varphi(T)\subseteq \Sigma(P(S))$. Let $t\in T$. We have

\begin{equation*} \mathrm{dom}(\varphi_t) = \{e\in P(S)\colon \exists a\in S\ \text{such that } e=a^+ \text{and } [a]_{\sigma}=t\}. \end{equation*}

If $e\in\mathrm{dom}(\varphi_t)$, then $e\varphi_t=a^*$ and $a^*\varphi_t^{-1}=a^+$, where $a\in S$ is such that $[a]_{\sigma}=t$ and $a^+=e$. Since $\varphi e = e\varphi^{-1}$ for all $\varphi\in {\mathcal{I}}(E)$, the operations on $P(S)\rtimes_{{\mathcal{G}}_S} T$ can be written as follows:

\begin{align*} (e,s,e\varphi_s)\cdot (f,t,f\varphi_t) & = ((e\varphi_s\wedge f)\varphi_s^{-1},s,e\varphi_s\wedge f)\cdot(e\varphi_s\wedge f, t, (e\varphi_s\wedge f)\varphi_t)\\ & = ((e\varphi_s\wedge f)\varphi_s^{-1}, st, (e\varphi_s\wedge f)\varphi_t), \end{align*}

\begin{equation*}(e,s,e\varphi_s)^+=(e,1,e),\hspace{1em}(e,s,e\varphi_s)^\ast=(e\varphi_s,1,e\varphi_s).\end{equation*}

Since the third component of a triple $(e,s,e\varphi_s)$ is determined by the first two components, $(e,s,e\varphi_s)$ is determined by the pair (e, s). The set ${\mathcal A}$ of all such pairs is in a bijection with the underlying set of $P(S)\rtimes_{{\mathcal{G}}_S} T$. The operations on $P(S)\rtimes_{{\mathcal{G}}_S} T$ are translated to operations on ${\mathcal A}$ as follows:

(6.1)\begin{equation}(e,s)(f,t)=((e\varphi_s\wedge f)\varphi_s^{-1},st),\hspace{0.5em}(e,s)^+=(e,1),{}\hspace{0.5em}(e,s)^\ast=(e\varphi_s,1).\end{equation}

On the other hand, let φ be a partial action of T on E by partial bijections between order ideals such that $\mathrm{dom}(\varphi_t)\neq \varnothing$ for all $t\in T$. The graph assigned to φ has vertex set E and edges $(e,t,f)$, where $t\in T$, $e\in\mathrm{dom}(\varphi_t)$ and $f=e\varphi_t$. We define the restriction of $(e,t,f)$ to $g\leq e$ by $_g|(e,t,f) = (g,t,g\varphi_t)$ and the co-restriction of $(e,t,f)$ to $h\leq f$ by $(e,t,f)|_h = (h\varphi_t^{-1},t,h)$. It is routine to verify that then ${\mathcal{G}}$ is a partial multiaction with compatible restrictions and co-restrictions, which satisfies conditions (LD) and (RD). We have rediscovered the structure result on proper restriction semigroups, as it is formulated in [Reference Kudryavtseva19, Theorem 3].

We conclude the paper with the following open questions.

In other words, is it true that every element of $a \in FES(X)$ is uniquely determined by $a^*$, $a^+$ and $[a]_{\sigma}$? It is known [Reference Branco, Gomes and Gould3] and easy to see that, unlike what happens in proper restriction semigroups, an element $a\in FES(X)$ is not in general uniquely determined only by $a^+$ (or by $a^*$) and $[a]_{\sigma}$. For example, if $X=\{x,y\}$, the elements $xy^+$ and $(xy)^+x$ are different (because their underlying Kambites trees [Reference Kambites16] are different) and we have that $(xy^+)^+ = ((xy)^+x)^+$ and $xy^+ {\sigma} (xy)^+x$. However, $(xy^+)^* \neq ((xy)^+x)^*$.