Endomorphisms of semigroups of order-preserving partial transformations

Abstract

We characterize the monoids of endomorphisms of the semigroup of all order-preserving partial transformations and of the semigroup of all order-preserving partial permutations of a finite chain.

1 Introduction

Let n be a natural number. Let $\Omega _n$ be a finite set with n elements, say $\Omega _n=\{1,2,\ldots ,n\}$. We denote by $\mathscr {PT}_n$ the monoid (under composition) of all partial transformations of $\Omega _n$. The submonoids of $\mathscr {PT}_n$ of all full transformations and of all partial permutations are denoted by $\mathscr {T}_n$ and $\mathscr {I}_n$, respectively. Also, denote by $\mathscr {S}_n$ the symmetric group on $\Omega _n$, i.e., the subgroup of $\mathscr {PT}_n$ of all permutations of $\Omega _n$. For $s\in \mathscr {PT}_n$, we denote the domain of s by $\mathop {\mathrm {Dom}}\nolimits (s)$, the image of s by $\mathop {\mathrm {Im}}\nolimits (s)$, the kernel of s by $\ker (s)$, and the set of fix points of s by $\mathop {\mathrm {Fix}}\nolimits (s)$, i.e., $\mathop {\mathrm {Fix}}\nolimits (s)=\{x\in \mathop {\mathrm {Dom}}\nolimits (s)\mid xs=x\}$.

Let us consider $\Omega _n$ endowed with the usual (linear) order. An element $s\in \mathscr {PT}_n$ is said to be order-preserving if $x\le y$ implies $xs\le ys$, for all $x,y \in \mathop {\mathrm {Dom}}\nolimits (s)$. Denote by $\mathscr {PO}_n$ the submonoid of $\mathscr {PT}_n$ of all order-preserving partial transformations. As usual, we denote by $\mathscr {O}_n$ the monoid $\mathscr {PO}_n\cap \mathscr {T}_n$ of all full transformations that preserve the order and by $\mathscr {POI}_n$ its injective counterpart, i.e., the inverse monoid $\mathscr {PO}_n\cap \mathscr {I}_n$ of all order-preserving partial permutations of $\Omega _n$.

Semigroups of order-preserving transformations have been considered in the literature for over than fifty years. Starting in 1962, Aǐzenštat [1, 2] gave a presentation for $\mathscr {O}_n$, from which it can be deduced that, for $n>1$, $\mathscr {O}_n$ only has one non-trivial automorphism, and characterized the congruences of $\mathscr {O}_n$. Also in 1962, Popova [26] exhibited a presentation for $\mathscr {PO}_n$. In 1971, Howie [20] calculated the cardinal and the number of idempotents of $\mathscr {O}_n$ and later (1992), jointly with Gomes [18], determined the ranks and the idempotent ranks of $\mathscr {O}_n$ and $\mathscr {PO}_n$. More recently, Laradji and Umar [22, 23] presented more combinatorial properties of these two monoids. Certain classes of divisors of the monoid $\mathscr {O}_n$ were determined by Higgins [19] and by Vernitskii and Volkov [30] in 1995, by Fernandes [8] in 1997 and by Fernandes and Volkov [15] in 2010. On the other hand, the monoid $\mathscr {POI}_n$ has been object of study by the first author in several papers [8,9,10,11,12], by Derech [6], by Garba [17], by Cowan and Reilly [4], by Delgado and Fernandes [5], by Ganyushkin and Mazorchuk [16], by Dimitrova and Koppitz [7], among other authors and papers.

For general background on semigroups, we refer the reader to Howie’s book [21].

Let $n\ge 2$.

Let $S\in \{\mathscr {O}_n,\mathscr {POI}_n,\mathscr {PO}_n\}$. We have the following descriptions of the Green relations in the semigroups S:

• $s\mathcal {L}t$ if and only if $\mathop {\mathrm {Im}}\nolimits (s)=\mathop {\mathrm {Im}}\nolimits (t)$,

• $s\mathcal {R}t$ if and only if $\ker (s)=\ker (t)$,

• $s\mathcal {J}t$ if and only if $|\mathop {\mathrm {Im}}\nolimits (s)|=|\mathop {\mathrm {Im}}\nolimits (t)|$, and

• $s\mathcal {H}t$ if and only if $s=t$,

for all $s,t\in S$. If $S=\mathscr {POI}_n$, for the Green relation $\mathcal {R}$, we have, even more simply,

• $s\mathcal {R}t$ if and only if $\mathop {\mathrm {Dom}}\nolimits (s)=\mathop {\mathrm {Dom}}\nolimits (t)$,

for all $s,t\in S$. Let

$$\begin{aligned} J_k=J_k^S=\{s\in S\mid |\mathop {\mathrm {Im}}\nolimits (s)|=k\}\quad \;\text {and}\;\quad I_k=I_k^S=\{s\in S\mid |\mathop {\mathrm {Im}}\nolimits (s)|\le k\}, \end{aligned}$$

for $0\le k\le n$. If $S\in \{\mathscr {POI}_n,\mathscr {PO}_n\}$ then

$$\begin{aligned} S/\mathcal {J}=\{J_0<_\mathcal {J}J_1<_\mathcal {J}\cdots <_\mathcal {J}J_n\} \end{aligned}$$

and $\{\emptyset \}=I_0\subset I_2\subset \cdots \subset I_n=S$ are all the ideals of S. On the other hand, if $S=\mathscr {O}_n$ then

$$\begin{aligned} S/\mathcal {J}=\{J_1<_\mathcal {J}J_2<_\mathcal {J}\cdots <_\mathcal {J}J_n\} \end{aligned}$$

and $I_1\subset I_2\subset \cdots \subset I_n=S$ are all the ideals of S. See [10, 18].

Recall that a Rees congruence$\rho$ of a semigroup S is a congruence associated to an ideal I of S: $s\rho t$ if and only if $s=t$ or $s,t\in I$, for all $s,t\in S$.

Observe that Aǐzenštat [2] proved the congruences of $\mathscr {O}_n$ are exactly the identity and its n Rees congruences. See [24] for another proof. Analogously, the congruences of $\mathscr {POI}_n$ and $\mathscr {PO}_n$ are exactly their $n+1$ Rees congruences. This has been shown, for $\mathscr {POI}_n$, by Derech [6] and, independently, by Fernandes [10] and, for $\mathscr {PO}_n$, by Fernandes et al. [13].

Let S be a monoid such that $S{\setminus }\{1\}$ is an ideal of S. Let e and f be two idempotents of S such that $ef=fe=f$. Then, clearly, the mapping $\phi :S\longrightarrow S$ defined by $1\phi =e$ and $s\phi =f$, for all $s\in S{\setminus }\{1\}$, is an endomorphism (of semigroups) of S. This applies to any $S\in \{\mathscr {O}_n,\mathscr {POI}_n,\mathscr {PO}_n\}$.

Let M be a monoid, let S be a subsemigroup of M and let g be a unit of M such that $g^{-1}Sg=S$. Then, it is easy to check that the mapping $\phi ^g:S\longrightarrow S$ defined by $s\phi ^g=g^{-1}sg$, for all $s\in S$, is an automorphism of S.

Consider the following permutation of $\Omega _n$:

$$\begin{aligned} \sigma =\left( \begin{array}{lllll} 1&{}\quad 2&{}\quad \cdots &{}\quad n-1&{}\quad n\\ n&{}\quad n-1&{}\quad \cdots &{}\quad 2&{}\quad 1 \end{array}\right) . \end{aligned}$$

Let $S\in \{\mathscr {O}_n,\mathscr {POI}_n,\mathscr {PO}_n\}$. It is easy to verify that $\sigma ^{-1}S\sigma =S$. Therefore, the permutation $\sigma$ induces a non-trivial automorphism $\phi ^{\sigma }$ of S. In fact, this is the unique non-trivial automorphism of S. See [3, Corollary 5.2].

Finding the automorphisms and endomorphisms of transformation semigroups is a classical problem. They have been determined for several transformation semigroups, for instance, $\mathscr {T}_n$ [28], $\mathscr {I}_n$ [27], and the Brauer-type semigroups [25]. Furthermore, regarding semigroups of order-preserving transformations, Fernandes et al. [14] proved the following description of the endomorphisms of $\mathscr {O}_n$:

Theorem 1.1

[14, Theorem 1.1] Let $\phi : \mathscr {O}_n\rightarrow \mathscr {O}_n$ be any mapping. Then $\phi$ is an endomorphism of the semigroup $\mathscr {O}_n$ if and only if one of the following holds:

• (a) $\phi$ is an automorphism and so $\phi$ is the identity or $\phi =\phi ^{\sigma }$;

• (b) there exist idempotents $e,f\in \mathscr {O}_n$ with $e\not =f$ and $ef=fe=f$ such that $1\phi =e$ and $(\mathscr {O}_n{\setminus }\{1\})\phi =\{f\}$;

• (c) $\phi$ is a constant mapping with idempotent value.

And, as a corollary:

Theorem 1.2

[14, Theorem 1.2] The semigroup $\mathscr {O}_n$ has $2+\sum _{i=0}^{n-1}\left( {\begin{array}{c}n+i\\ 2i+1\end{array}}\right) F_{2i+2}$ endomorphisms, where $F_{2i+2}$ denotes the $(2i+2)$th Fibonacci number.

In this paper we describe the monoids of the endomorphisms of the semigroups $\mathscr {POI}_n$ and $\mathscr {PO}_n$. As an application of these descriptions, we compute the number of such endomorphisms. This paper is organized as follows. After the current section, we give a miscellaneous of auxiliary results in Sect. 2. Finally, in Sect. 3 we present and prove our main results.

2 Preliminary results

In this section we present a series of auxiliary results. We also construct a certain type of endomorphisms of $\mathscr {POI}_n$ and $\mathscr {PO}_n$.

Our first two lemmas have some general nature.

Lemma 2.1

Let S be a regular semigroup. Let I be an ideal of S and $\phi$ be an endomorphism of S such that the kernel of $\phi$ is the Rees congruence associated to I. Let $s,t\in S{\setminus }I$. Then:

• 1. $s\mathcal {L}t$ if and only if $s\phi \mathcal {L}t\phi$;

• 2. $s\mathcal {R}t$ if and only if $s\phi \mathcal {R}t\phi$.

Proof

We prove the lemma for the Green relation $\mathcal {L}$. The proof for $\mathcal {R}$ is similar.

First, notice that $I\phi \phi ^{-1}=I$ and the restriction of $\phi$ to $S{\setminus } I$ is injective.

Let $s,t\in S{\setminus } I$. If $s\mathcal {L}t$, then $s\phi \mathcal {L}t\phi$, since any homomorphism of semigroups preserve Green relations (i.e., images of related elements are related). Conversely, suppose that $s\phi \mathcal {L}t\phi$. As S is regular, then $S\phi$ is also regular, whence $s\phi$ and $t\phi$ are also $\mathcal {L}$-related in $S\phi$ and so, for some $u,v\in S$, we have $s\phi =(u\phi )(t\phi )$ and $t\phi =(v\phi )(s\phi )$. Thus, $s\phi =(ut)\phi$ and so $ut\in S{\setminus } I$, since $s\in S{\setminus } I$ and $I\phi \phi ^{-1}=I$. Moreover, as $\phi$ is injective in $S{\setminus } I$, it follows that $s=ut$. Analogously, $t=vs$ and so $s\mathcal {L}t$, as required. $\square$

Lemma 2.2

Let S be any subsemigroup of $\mathscr {PT}_n$ which contains transformations with arbitrary images of size less than n. Let $s\in S$ and $k\in \mathbb N$ be such that $1\le \mathop {\mathrm {rank}}\nolimits (s)\le k\le n-2$. Then, there exists $t\in S$ such that $\mathop {\mathrm {rank}}\nolimits (t)=k+1$ and $st\ne s$.

Proof

Let A be any subset of $\Omega _n$ such that $\mathop {\mathrm {Im}}\nolimits (s)\subset A$ and $|A|=k+2$. Let t be any element of S such that $\mathop {\mathrm {Im}}\nolimits (t)=A{\setminus }\{\min (\mathop {\mathrm {Im}}\nolimits (s))\}$ (notice that $\mathop {\mathrm {Im}}\nolimits (s)\ne \emptyset$). Then, $\mathop {\mathrm {rank}}\nolimits (t)=k+1$ and $\mathop {\mathrm {Im}}\nolimits (st)\subseteq \mathop {\mathrm {Im}}\nolimits (t)$. Since $\min (\mathop {\mathrm {Im}}\nolimits (s))\not \in \mathop {\mathrm {Im}}\nolimits (t)$, then also $\min (\mathop {\mathrm {Im}}\nolimits (s))\not \in \mathop {\mathrm {Im}}\nolimits (st)$, whence $\mathop {\mathrm {Im}}\nolimits (s)\ne \mathop {\mathrm {Im}}\nolimits (st)$, and so $s\ne st$, as required. $\square$

Observe that the previous lemma applies to any $S\in \{\mathscr {O}_n,\mathscr {POI}_n,\mathscr {PO}_n\}$.

Next, we give two particular properties of our semigroups.

Lemma 2.3

Let $k\in \{0,1,\ldots ,n-2\}$. Then, there exist idempotents $h_1,\ldots ,h_n\in J_{k+1}^{\mathscr {POI}_n}$ such that $h_ih_j\in I_k^{\mathscr {POI}_n}$, for all $1\le i<j\le n$.

Proof

We have $\left( {\begin{array}{c}n\\ k+1\end{array}}\right)$ distinct subsets of $\Omega _n$ with $k+1$ elements. As $0\le k\le n-2$, then $1\le k+1\le n-1$, and so $\left( {\begin{array}{c}n\\ k+1\end{array}}\right) \ge n$. Therefore, we may take (at least) n distinct subsets $Y_1,\ldots , Y_n$ of $\Omega _n$ with $k+1$ elements. Let $h_i$ be the partial identity on $Y_i$, for $1\le i\le n$. Then, for $1\le i<j\le n$, the transformation $h_ih_j$ is the partial identity on $Y_i\cap Y_j$ and, since $Y_i\ne Y_j$, we obtain $|Y_i\cap Y_j|<|Y_j|=k+1$, whence $h_ih_j\in I_k^{\mathscr {POI}_n}$, as required. $\square$

For $k\in \{2,3,\ldots ,n\}$, consider the following two transformations of $\mathscr {O}_n$ with rank $n-1$:

$$\begin{aligned} f_k= & {} \left( \begin{array}{lllllll} 1&{}\quad \cdots &{}\quad k-1&{}\quad k&{}\quad k+1&{}\quad \cdots &{}\quad n\\ 1&{}\quad \cdots &{}\quad k-1&{}\quad k-1&{}\quad k+1&{}\quad \cdots &{}\quad n \end{array}\right) \quad \text {and}\quad \\ g_k= & {} \left( \begin{array}{lllllll} 1&{}\quad \cdots &{}\quad k-2&{}\quad k-1&{}\quad k&{}\quad \cdots &{}\quad n\\ 1&{}\quad \cdots &{}\quad k-2&{}\quad k&{}\quad k&{}\quad \cdots &{}\quad n \end{array}\right) . \end{aligned}$$

We have:

Lemma 2.4

Each of the $n-1$$\mathcal {R}$-classes of transformations of rank $n-1$ of $\mathscr {O}_n$ has exactly two idempotents, namely $f_k$ and $g_k$, for some $k\in \{2,3,\ldots ,n\}$.

Proof

Let R be an $\mathcal {R}$-class of $\mathscr {O}_n$ contained in $J_{n-1}^{\mathscr {O}_n}$. Then all elements of R have the same kernel, which is associated to a partition of $\Omega _n$ of the form $\{\{i\}\mid i\in \{1,2,\ldots ,k-2,k+1,\ldots ,n\}\}\cup \{\{k-1,k\}\}$, for some $k\in \{2,3,\ldots ,n\}$. Clearly, $f_k$ and $g_k$ are two distinct idempotents of R. Moreover, let

$$\begin{aligned} e=\left( \begin{array}{lllllll} 1&{}\quad \cdots &{}\quad k-1&{}\quad k&{}\quad k+1&{}\quad \cdots &{}\quad n\\ i_1&{}\quad \cdots &{}\quad i_{k-1}&{}\quad i_{k-1}&{}\quad i_k&{}\quad \cdots &{}\quad i_{n-1} \end{array}\right) , \end{aligned}$$

with $1\le i_1< \cdots <i_{n-1}\le n$, be an (arbitrary) idempotent of R. Then $\mathop {\mathrm {Fix}}\nolimits (e)=\mathop {\mathrm {Im}}\nolimits (e)$ and so $|\mathop {\mathrm {Fix}}\nolimits (e)|=n-1$, whence there exists a unique $i\in \Omega _n$ such that $(i)e\ne i$. Since $((i)e)e=(i)e$, we have $((i)e,i)\in \ker (e)$, and so $\{(i)e,i\}=\{k-1,k\}$. If $i=k$ then, clearly, $e=f_k$. Otherwise, $i=k-1$ and then, clearly, $e=g_k$. This proves the lemma. $\square$

For $i\in \{1,2,\ldots ,n\}$, let

$$\begin{aligned} e_i=\left( \begin{array}{llllll} 1&{}\quad \cdots &{}\quad i-1&{}\quad i+1&{}\quad \cdots &{}\quad n\\ 1&{}\quad \cdots &{}\quad i-1&{}\quad i+1&{}\quad \cdots &{}\quad n \end{array}\right) . \end{aligned}$$

It is clear that each of the n$\mathcal {R}$-classes of transformations of rank $n-1$ of $\mathscr {POI}_n$ has exactly one idempotent (notice that $\mathscr {POI}_n$ is an inverse semigroup), namely $e_i$, for some $i\in \{1,2,\ldots ,n\}$.

Notice that $J_{n-1}^{\mathscr {PO}_n}=J_{n-1}^{\mathscr {O}_n}\cup J_{n-1}^{\mathscr {POI}_n}$ (a disjoint union). Hence, by the above observations, $J_{n-1}^{\mathscr {PO}_n}$ contains n$\mathcal {R}$-classes exactly with one idempotent and $n-1$$\mathcal {R}$-classes exactly with two idempotents. Moreover, each $\mathcal {R}$-class contained in $J_{n-1}^{\mathscr {PO}_n}$ has precisely n transformations (one for each possible image with $n-1$ elements). Additionally, it is clear that each $\mathcal {R}$-class contained in $J_1^{\mathscr {PO}_n}$ is determined by the domain of the transformations (as it happens in general in $\mathscr {POI}_n$), and so we have $2^n-1$$\mathcal {R}$-classes of transformations of rank 1 of $\mathscr {PO}_n$, each with exactly as many idempotents as elements in the corresponding domain. Such as for $J_{n-1}^{\mathscr {PO}_n}$, each $\mathcal {R}$-class contained in $J_1^{\mathscr {PO}_n}$ has precisely n transformations (one for each possible image with 1 element).

Next, we aim to construct an endomorphism of $\mathscr {PO}_n$.

Let us define a mapping $\phi _1:\mathscr {PO}_n\longrightarrow \mathscr {PO}_n$ by:

• 1. $1\phi _1=1$;

• 2. For $s\in J_{n-1}^{\mathscr {POI}_n}$, let $s\phi _1=\left( {\begin{array}{c}i\\ j\end{array}}\right)$, where $i,j\in \{1,2,\ldots ,n\}$ are the unique indices such that $e_i\mathcal {R}s\mathcal {L}e_j$;

• 3. For $s\in J_{n-1}^{\mathscr {O}_n}$, let $s\phi _1=\left( \begin{array}{ll} k-1&{}k\\ k_s&{}k_s \end{array}\right)$, where $\{k_s\}=\Omega _n{\setminus }\mathop {\mathrm {Im}}\nolimits (s)$ and $k\in \{2,3,\ldots ,n\}$ is the unique index such that $s\mathcal {R}f_k$ (and $s\mathcal {R}g_k$);

• 4. $I_{n-2}^{\mathscr {PO}_n}\phi _1=\{\emptyset \}$.

Clearly, $\phi _1$ is well defined mapping. Moreover, since $\mathscr {PO}_n$ (such as $\mathscr {POI}_n$) is an $\mathcal {H}$-trivial semigroup (and so each element of $\mathscr {PO}_n$ is perfectly defined by its $\mathcal {L}$-class and $\mathcal {R}$-class, i.e., its image and kernel), the restriction of $\phi _1$ to $\mathscr {PO}_n{\setminus } I_{n-2}^{\mathscr {PO}_n}$ is injective. Furthermore, it is a routine matter to prove the following lemma.

Lemma 2.5

The mapping $\phi _1$ is an endomorphism of $\mathscr {PO}_n$ such that $\mathscr {POI}_n\phi _1\subseteq \mathscr {POI}_n$. Consequently, the restriction of $\phi _1$ to $\mathscr {POI}_n$ may also be seen as an endomorphism of $\mathscr {POI}_n$.

All endomorphisms similar to $\phi _1$ have the following property.

Lemma 2.6

Let $S\in \{\mathscr {POI}_n,\mathscr {PO}_n\}$. Let $\phi$ be an endomorphism of S such that $1\phi =1$, $J_{n-1}\phi \subseteq J_1$ and $I_{n-2}\phi =\{\emptyset \}$. Then $\phi$ is perfectly defined by the images of the idempotents $e_1,\ldots , e_n$. Moreover, $|\mathop {\mathrm {Dom}}\nolimits (s\phi )|=1$, for all $s\in J_{n-1}^{\mathscr {POI}_n}$, and $|\mathop {\mathrm {Dom}}\nolimits (s\phi )|=2$, for all $s\in J_{n-1}^{\mathscr {O}_n}$.

Proof

We begin by observing that the kernel of $\phi$ must be the Rees congruence associated to $I_{n-2}$ and so $\phi$ is injective in $S{\setminus } I_{n-2}$. Next, as $\phi$ applies $\mathcal {R}$-related transformations of $J_{n-1}$ in $\mathcal {R}$-related transformations of $J_1$, $\phi$ injective in $J_{n-1}$ and the $\mathcal {R}$-classes contained in $J_{n-1}$ and in $J_1$ have the same number of elements, namely n, the endomorphism $\phi$ applies each $\mathcal {R}$-class of $J_{n-1}$ bijectively in a $\mathcal {R}$-class of $J_1$. It follows that, for each $\mathcal {R}$-class R of $J_{n-1}$, the number of idempotents of R and of the $\mathcal {R}$-class $R\phi$ of $J_1$ must be the same. Thus, in particular, $J_{n-1}^{\mathscr {POI}_n}\phi =J_1^{\mathscr {POI}_n}$.

For each $i\in \{1,2,\ldots ,n\}$, let $k_i\in \Omega _n$ be such that $e_i\phi =\left( {\begin{array}{c}k_i\\ k_i\end{array}}\right)$. Notice that $\left( \begin{array}{llll} 1&{}2&{}\cdots &{}n\\ k_1&{}k_2&{}\cdots &{}k_n \end{array}\right)$ is a permutation of $\Omega _n$.

Let $s\in J_{n-1}^{\mathscr {POI}_n}$. Then, there exists a unique pair $(i,j)\in \{1,2,\ldots ,n\}\times \{1,2,\ldots ,n\}$ such that $s\mathcal {R}e_i$ and $s\mathcal {L}e_j$. Then, $s\phi \mathcal {R}e_i\phi$ and $s\phi \mathcal {L}e_j\phi$, and so $s\phi =\left( {\begin{array}{c}k_i\\ k_j\end{array}}\right)$.

If $S=\mathscr {POI}_n$ then the proof is completed. Thus, from now on, we suppose that $S=\mathscr {PO}_n$.

Let $i\in \{2,3,\ldots ,n\}$. Then $f_i\mathcal {L}e_i$ and $g_i\mathcal {L}e_{i-1}$, whence $f_i\phi \mathcal {L}e_i\phi$ and $g_i\phi \mathcal {L}e_{i-1}\phi$, and so $\mathop {\mathrm {Im}}\nolimits (f_i\phi )=\{k_i\}$ and $\mathop {\mathrm {Im}}\nolimits (g_i\phi )=\{k_{i-1}\}$. Hence, $k_i\in \mathop {\mathrm {Im}}\nolimits (f_i\phi )=\mathop {\mathrm {Fix}}\nolimits (f_i\phi )\subseteq \mathop {\mathrm {Dom}}\nolimits (f_i\phi )$ and $k_{i-1}\in \mathop {\mathrm {Im}}\nolimits (g_i\phi )=\mathop {\mathrm {Fix}}\nolimits (g_i\phi )\subseteq \mathop {\mathrm {Dom}}\nolimits (g_i\phi )$. Besides, as $f_i\mathcal {R}g_i$, we have $f_i\phi \mathcal {R}g_i\phi$ and so $\mathop {\mathrm {Dom}}\nolimits (f_i\phi )=\mathop {\mathrm {Dom}}\nolimits (g_i\phi )$. Since $|\mathop {\mathrm {Dom}}\nolimits (f_i\phi )|=2$ and $k_{i-1}\ne k_i$, it follows that $\mathop {\mathrm {Dom}}\nolimits (f_i\phi )=\{k_{i-1},k_i\}$.

Now, let $s\in J_{n-1}^{\mathscr {O}_n}$. Then, there exists a unique pair $(i,j)\in \{2,3,\ldots ,n\}\times \{1,2,\ldots ,n\}$ such that $s\mathcal {R}f_i$ and $s\mathcal {L}e_j$. Thus, $s\phi \mathcal {R}f_i\phi$ and $s\phi \mathcal {L}e_j\phi$, and so $s\phi =\left( \begin{array}{ll} k_{i-1}&{}k_i\\ k_j&{}k_j \end{array}\right)$, which finishes the proof of this lemma. $\square$

Observe that we may also conclude that, within the conditions of the previous lemma, we have at most n! endomorphisms.

Now, we recall that a subsemigroup T of $\mathscr {PT}_n$ is said to be $\mathscr {S}_n$-normal if $g^{-1}Tg\subseteq T$, for all $g\in \mathscr {S}_n$. In 1975, Sullivan [29, Theorem 2] proved that $\text {Aut}(T)\simeq \mathscr {S}_n$, for any $\mathscr {S}_n$-normal subsemigroup T of $\mathscr {PT}_n$ containing a constant mapping. Moreover, we obtain an isomorphism $\Theta :\mathscr {S}_n\longrightarrow \text {Aut}(T)$ by defining $g\Theta =\theta _g$, where $\theta _g$ denotes the inner automorphism of T associated to g (i.e., $t\theta _g=g^{-1}tg$, for all $t\in T$), for all $g\in \mathscr {S}_n$.

Let $S\in \{\mathscr {POI}_n,\mathscr {PO}_n\}$. Let $I_1^1=I_1\cup \{1\}$. It is clear that $I_1^1$ is an $\mathscr {S}_n$-normal subsemigroup of $\mathscr {PT}_n$ containing a constant mapping. Therefore, by Sullivan’s Theorem, we have

$$\begin{aligned} \text {Aut}(I_1^1)=\{\theta _g\mid g\in \mathscr {S}_n\}\simeq \mathscr {S}_n, \end{aligned}$$

where $\theta _g$ denotes the inner automorphism of $I_1^1$ associated to g, for all $g\in \mathscr {S}_n$.

Let $\phi _g={\phi _1}_{\displaystyle |_S}\theta _g$ (where ${\phi _1}_{\displaystyle |_S}$ denotes the restriction of $\phi _1$ to S), considered as a mapping from S to S, for all $g\in \mathscr {S}_n$. Clearly, $\{\phi _g\mid g\in \mathscr {S}_n\}$ is a set of n! distinct endomorphisms of S. Moreover, it is easy to conclude the following result, with which we finish this section.

Lemma 2.7

Let $S\in \{\mathscr {POI}_n,\mathscr {PO}_n\}$. Let $\phi$ be an endomorphism of S such that $1\phi =1$, $J_{n-1}\phi \subseteq J_1$ and $I_{n-2}\phi =\{\emptyset \}$. Then, $\phi =\phi _g$, for some $g\in \mathscr {S}_n$.

3 Main results

Let $S\in \{\mathscr {POI}_n,\mathscr {PO}_n\}$. Let $\phi$ be an endomorphism of the semigroup S. Then, $\ker (\phi )$ is the Rees congruence of S associated to $I_k$, for some $k\in \{0,1,\ldots ,n\}$. Observe that the restriction of $\phi$ to $S{\setminus } I_k$ is an injective mapping and $|I_k\phi |=1$. Let $f\in S$ be such that $I_k\phi =\{f\}$. Clearly, f is an idempotent of S. Notice also that $\{f\}\phi ^{-1}=I_k$.

Suppose that $\phi$ is neither a constant mapping nor an automorphism. Then, since $\ker (\phi )$ is not trivial and not universal, we have $1\le k\le n-1$.

Let us admit that $k=n-1$ and take $e=1\phi$. Then e is also an idempotent, $e\ne f$ and, for $s\in I_{n-1}$, we have $ef=(1\phi )(s\phi )=(1\cdot s)\phi =s\phi =f=s\phi =(s\cdot 1)\phi =(s\phi )(1\phi )=fe$.

From now on, suppose that $1\le k\le n-2$. Since any homomorphism of semigroups preserve Green relations, there exists $\ell \in \{0,1,\ldots ,n\}$ such that $J_{k+1}\phi \subseteq J_{\ell }$. Under these conditions, we prove two lemmas.

Lemma 3.1

Under the above conditions, one has $\mathop {\mathrm {rank}}\nolimits (f)<\ell$.

Proof

First, notice that $(\cup _{i=k+1}^{n}J_i)\phi \subseteq \cup _{i=\ell }^{n}J_i$, since $J_{k+1}\phi \subseteq J_{\ell }$ and any homomorphism preserves the quasi-order $\le _\mathcal {J}$.

Next, we show that $\mathop {\mathrm {rank}}\nolimits (f)\le \ell$. Take $s\in J_k$ and $t\in J_{k+1}$. Then, $s<_\mathcal {J}t$, and so $s\phi \le _\mathcal {J}t\phi$. Since $J_k\phi =\{f\}$ and $J_{k+1}\phi \subseteq J_{\ell }$, we have $s\phi =f$ and $t\phi \in J_{\ell }$, whence $\mathop {\mathrm {rank}}\nolimits (f)\le \ell$.

Now, we prove that $\mathop {\mathrm {rank}}\nolimits (f)\le k$. By contradiction, suppose that $\mathop {\mathrm {rank}}\nolimits (f)\ge k+1$. Then, $I_k\subseteq I_{\mathop {\mathrm {rank}}\nolimits (f)-1}$, and so

$$\begin{aligned} (S{\setminus } I_k)\phi =(\cup _{i=k+1}^{n}J_i)\phi \subseteq \cup _{i=\ell }^{n}J_i \subseteq \cup _{i=\mathop {\mathrm {rank}}\nolimits (f)}^{n}J_i =S{\setminus } I_{\mathop {\mathrm {rank}}\nolimits (f)-1}\subseteq S{\setminus } I_k. \end{aligned}$$

It follows that $(S{\setminus } I_k)\phi =S{\setminus } I_k$, since the restriction of $\phi$ to $S{\setminus } I_k$ is injective. As $\mathop {\mathrm {rank}}\nolimits (f)\ge k+1$ also implies that $f\in S{\setminus } I_k$, we deduce that $I_k\cap S{\setminus } I_k=\{f\}\phi ^{-1}\cap S{\setminus } I_k\ne \emptyset$, which is a contradiction. Thus, we must have $\mathop {\mathrm {rank}}\nolimits (f)\le k$.

Finally, we prove that $\mathop {\mathrm {rank}}\nolimits (f)<\ell$. Suppose, by contradiction, that $\mathop {\mathrm {rank}}\nolimits (f)=\ell$. Take $s\in J_{k+1}$. Since $J_{k+1}\phi \subseteq J_{\ell }$, we have $s\phi \mathcal {J}f$. Moreover, as $f\in I_k$, we also have $sf,fs\in I_k$, whence $(sf)\phi =(fs)\phi =f\phi =f$. From $f=(fs)\phi =f\phi s\phi =f(s\phi )$, it follows that $\mathop {\mathrm {Im}}\nolimits (f)=\mathop {\mathrm {Im}}\nolimits (f(s\phi ))\subseteq \mathop {\mathrm {Im}}\nolimits (s\phi )$. From $f=(sf)\phi =s\phi f\phi =(s\phi )f$, it follows that $\ker (f)=\ker ((s\phi )f)\supseteq \ker (s\phi )$. Since $s\phi \mathcal {J}f$, we have $|\ker (f)|=|\mathop {\mathrm {Im}}\nolimits (f)|=|\mathop {\mathrm {Im}}\nolimits (s\phi )|=|\ker (s\phi )|$, and so $\mathop {\mathrm {Im}}\nolimits (f)=\mathop {\mathrm {Im}}\nolimits (s\phi )$ and $\ker (f)=\ker (s\phi )$, whence $f\mathcal {L}s\phi$ and $f\mathcal {R}s\phi$, i.e., $f\mathcal {H}s\phi$. Thus, $f=s\phi$, which is a contradiction (being the case that $s\in J_{k+1}$ and $\{f\}\phi ^{-1}=I_k$). Therefore, $\mathop {\mathrm {rank}}\nolimits (f)<\ell$, as required. $\square$

Lemma 3.2

Under the above conditions, $1\phi =1$, $J_{n-1}\phi \subseteq J_1$, and $I_{n-2}\phi =\{\emptyset \}$.

Proof

Since $k\in \{1,2,\ldots ,n-2\}$, by Lemma 2.3, we may take idempotents $h_1,\ldots ,h_n\in J_{k+1}^{\mathscr {POI}_n}$ such that $h_ih_j\in I_k^{\mathscr {POI}_n}$, for all $1\le i<j\le n$.

Recall that $f\in I_k$, and so $f\phi =f$. Let $i\in \{1,2,\ldots ,n\}$. Then, $f (h_i\phi )=f\phi h_i\phi =(fh_i)\phi =f$, since $fh_i\in I_k$. Hence, $\mathop {\mathrm {Im}}\nolimits (f)\subseteq \mathop {\mathrm {Im}}\nolimits (h_i\phi )$.

Next, let $1\le i<j\le n$. By the previous paragraph, we have $\mathop {\mathrm {Im}}\nolimits (f)\subseteq \mathop {\mathrm {Im}}\nolimits (h_i\phi )\cap \mathop {\mathrm {Im}}\nolimits (h_j\phi )$. Conversely, let $a\in \mathop {\mathrm {Im}}\nolimits (h_i\phi )\cap \mathop {\mathrm {Im}}\nolimits (h_j\phi )$. Since $h_i\phi$ and $h_j\phi$ are idempotents and $h_ih_j\in I_k$, we have $\mathop {\mathrm {Im}}\nolimits (h_i\phi )=\mathop {\mathrm {Fix}}\nolimits (h_i\phi )$, $\mathop {\mathrm {Im}}\nolimits (h_j\phi )=\mathop {\mathrm {Fix}}\nolimits (h_j\phi )$ and $(h_ih_j)\phi =f$, whence $af=a(h_ih_j)\phi =(a(h_i\phi ))(h_j\phi )=a(h_j\phi )=a$, and so $a\in \mathop {\mathrm {Im}}\nolimits (f)$. Then, $\mathop {\mathrm {Im}}\nolimits (h_i\phi )\cap \mathop {\mathrm {Im}}\nolimits (h_j\phi )\subseteq \mathop {\mathrm {Im}}\nolimits (f)$, and thus $\mathop {\mathrm {Im}}\nolimits (h_i\phi )\cap \mathop {\mathrm {Im}}\nolimits (h_j\phi )=\mathop {\mathrm {Im}}\nolimits (f)$.

Let $E_i=\mathop {\mathrm {Im}}\nolimits (h_i\phi ){\setminus }\mathop {\mathrm {Im}}\nolimits (f)$, for $1\le i\le n$. Clearly, $\mathop {\mathrm {Im}}\nolimits (f)\cap (\cup _{i=1}^{n}E_i)=\emptyset$ and, for $1\le i<j\le n$, the equality $\mathop {\mathrm {Im}}\nolimits (h_i\phi )\cap \mathop {\mathrm {Im}}\nolimits (h_j\phi )=\mathop {\mathrm {Im}}\nolimits (f)$ implies that $E_i\cap E_j=\emptyset$. Moreover, since $h_i\in J_{k+1}$, then $\mathop {\mathrm {rank}}\nolimits (h_i\phi )=\ell >\mathop {\mathrm {rank}}\nolimits (f)$, by Lemma 3.1, and so $|E_i|\ge 1$, for $1\le i\le n$. Thus $|E_1|=|E_2|=\cdots =|E_n|=1$ and $\cup _{i=1}^{n}E_i=\Omega _n$, from which follows that $\mathop {\mathrm {Im}}\nolimits (f)=\emptyset$.

Now, observe that $\ell =\mathop {\mathrm {rank}}\nolimits (h_1\phi )=|\mathop {\mathrm {Im}}\nolimits (h_1\phi )|=|E_1\cup \mathop {\mathrm {Im}}\nolimits (f)|=|E_1|=1$. Then, $J_{k+1}\phi \subseteq J_1$, and so we cannot have more than n elements of $J_{k+1}\phi$ in distinct $\mathcal {L}$-classes. Thus, by Lemma 2.1, we cannot have more than n elements of $J_{k+1}$ in distinct $\mathcal {L}$-classes, i.e. $\left( {\begin{array}{c}n\\ k+1\end{array}}\right) \le n$, and so $k+1\in \{0,1,n-1,n\}$. Since $1\le k\le n-2$, it follows that $k=n-2$.

It remains to show that $e=1$. Since $J_{n-1}\phi \subseteq J_1$ and $I_{n-2}\phi =\{\emptyset \}$, the reasoning of the first paragraph of the proof of Lemma 2.6 applies here and we can conclude that $J_{n-1}^{\mathscr {POI}_n}\phi =J_1^{\mathscr {POI}_n}$.

Suppose, by contradiction, that $e\ne 1$. Then, $|\mathop {\mathrm {Im}}\nolimits (e)|<n$ and so we may take $i\in \Omega _n{\setminus }\mathop {\mathrm {Im}}\nolimits (e)$. Let $h\in J_{n-1}^{\mathscr {POI}_n}$ be such that $h\phi =\left( {\begin{array}{c}i\\ i\end{array}}\right)$. Hence, $\emptyset =e\left( {\begin{array}{c}i\\ i\end{array}}\right) =(1\phi )(h\phi )=(1\cdot h)\phi =h\phi =\left( {\begin{array}{c}i\\ i\end{array}}\right) ,$ a contradiction. Thus, $1\phi =1$, as required. $\square$

Now, by Lemmas 3.2 and 2.7, we can deduce that, if $1\le k\le n-2$, then ($k=n-2$ and) $\phi =\phi _g$, for some $g\in \mathscr {S}_n$. This concludes the proof of the following description of the monoid of endomorphisms of S.

Theorem 3.3

Let $S\in \{\mathscr {POI}_n,\mathscr {PO}_n\}$. Let $\phi : S\longrightarrow S$ be any mapping. Then, $\phi$ is an endomorphism of the semigroup S if and only if one of the following holds:

• (a) $\phi$ is an automorphism and so $\phi$ is the identity or $\phi =\phi ^{\sigma }$;

• (b) there exist idempotents $e,f\in S$ with $e\not =f$ and $ef=fe=f$ such that $1\phi =e$ and $(S{\setminus }\{1\})\phi =\{f\}$;

• (c) $\phi =\phi _g$, for some $g\in \mathscr {S}_n$;

• (d) $\phi$ is a constant mapping with idempotent value.

As a corollary of the this theorem, we finish this paper by counting the number of endomorphisms of $\mathscr {POI}_n$ and of $\mathscr {PO}_n$.

For $S\in \{\mathscr {POI}_n,\mathscr {PO}_n\}$ and for each idempotent $e\in S$, let

$$\begin{aligned} E_S(e)=\{f\in S\mid f^2=f\, {\text {and}}\, fe=ef=f\}. \end{aligned}$$

Then, according to Theorem 3.3, we have $\sum _{e^2=e\in S}|E_S(e)|$ endomorphisms of S of type (b) and (d).

We start by considering $\mathscr {POI}_n$.

Theorem 3.4

The semigroup $\mathscr {POI}_n$ has $2+n!+3^n$ endomorphisms.

Proof

First, recall that the idempotents of $\mathscr {POI}_n$ are all the partial identities of $\Omega _n$, and so we precisely have $\left( {\begin{array}{c}n\\ k\end{array}}\right)$ idempotents of $\mathscr {POI}_n$ with rank k, for all $0\le k\le n$.

Let e be an idempotent of $\mathscr {POI}_n$. Then, it is easy to show that $f\in E_{\mathscr {POI}_n}(e)$ if and only if $\mathop {\mathrm {Im}}\nolimits (f)\subseteq \mathop {\mathrm {Im}}\nolimits (e)$, for any idempotent f of $\mathscr {POI}_n$. Hence, $|E_{\mathscr {POI}_n}(e)|=2^{|\mathop {\mathrm {Im}}\nolimits (e)|}$.

It follows that the number of endomorphisms of $\mathscr {POI}_n$ of type (b) and (d) is equal to

$$\begin{aligned} \sum _{e^2=e\in \mathscr {POI}_n}|E_{\mathscr {POI}_n}(e)| = \sum _{e^2=e\in \mathscr {POI}_n}2^{|\mathop {\mathrm {Im}}\nolimits (e)|} = \sum _{k=0}^{n}\left( {\begin{array}{c}n\\ k\end{array}}\right) 2^k=3^n, \end{aligned}$$

and so, since we have n! endomorphisms of type (c), as observed at the end of Sect. 2, and two automorphisms, we obtain a total of $2+n!+3^n$ endomorphisms of $\mathscr {POI}_n$, as required. $\square$

Counting the number of endomorphisms of $\mathscr {PO}_n$ is more elaborated than for $\mathscr {POI}_n$. First, we prove two lemmas.

Lemma 3.5

Let $1\le k\le n$ and let e be an idempotent of $\mathscr {PO}_n$ with rank k. Then, the set $E_{\mathscr {PO}_n}(e)$ has as many elements as the number of idempotents of $\mathscr {PO}_k$, i.e., $E_{\mathscr {PO}_n}(e)$ has $1+(\sqrt{5})^{k-1}((\frac{\sqrt{5}+1}{2})^k-(\frac{\sqrt{5}-1}{2})^k)$ elements.

Proof

Let X be any finite chain and denote by $\mathscr {PO}(X)$ the monoid of all order-preserving partial transformations on X. Observe that $\mathscr {PO}(X)$ and $\mathscr {PO}_{|X|}$ are isomorphic monoids.

Let $1\le k\le n$ and let e be an idempotent of $\mathscr {PO}_n$ with rank k. Given an idempotent $g\in \mathscr {PO}(\mathop {\mathrm {Im}}\nolimits (e))$, it is a routine matter to check that $eg\in E_{\mathscr {PO}_n}(e)$ and, moreover, that the map $\{f\in \mathscr {PO}(\mathop {\mathrm {Im}}\nolimits (e))\mid f^2=f\}\longrightarrow E_{\mathscr {PO}_n}(e)$, $g\longmapsto eg$, is a bijection. Therefore, $|E_{\mathscr {PO}_n}(e)|=|\{f\in \mathscr {PO}_k\mid f^2=f\}|$.

Now, it remains to recall that Laradji and Umar proved that the number of idempotents of $\mathscr {PO}_k$ is equal to $1+(\sqrt{5})^{k-1}((\frac{\sqrt{5}+1}{2})^k-(\frac{\sqrt{5}-1}{2})^k)$ (see [22, Theorem 3.8]).

$\square$

Lemma 3.6

The number of idempotents of $\mathscr {PO}_n$ with rank k is $\sum _{i=k}^{n}\left( {\begin{array}{c}n\\ i\end{array}}\right) \left( {\begin{array}{c}i+k-1\\ 2k-1\end{array}}\right)$, for $1\le k\le n$.

Proof

Let X be any finite chain and denote by $\mathscr {O}(X)$ the monoid of all order-preserving full transformations on X. As for order-preserving partial transformations, we have that $\mathscr {O}(X)$ and $\mathscr {O}_{|X|}$ are isomorphic monoids.

Let $1\le k\le n$. Since an idempotent fixes its image, given an idempotent e of $\mathscr {PO}_n$, it is clear that $\mathop {\mathrm {Im}}\nolimits (e)\subseteq \mathop {\mathrm {Dom}}\nolimits (e)$, and so $e\in \mathscr {O}(\mathop {\mathrm {Dom}}\nolimits (e))$. Hence, an element e of $\mathscr {PO}_n$ is an idempotent with rank k if and only if e is an idempotent of $\mathscr {O}(X)$ with rank k, for some subset X of $\Omega _n$ such that $|X|\ge k$. Therefore, the number of idempotents of $\mathscr {PO}_n$ with rank k is

$$\begin{aligned} \sum _{i=k}^{n}\left( {\begin{array}{c}n\\ i\end{array}}\right) |\{e\in J_k^{\mathscr {O}_i}\mid e^2=e\}|, \end{aligned}$$

and so, since $|\{e\in J_k^{\mathscr {O}_i}\mid e^2=e\}|=\left( {\begin{array}{c}i+k-1\\ 2k-1\end{array}}\right)$, by [23, Corollary 4.4], for $i\ge k$, the lemma is proved. $\square$

Observe that, by the previous lemma and [22, Theorem 3.8], we obtain the following equality:

$$\begin{aligned} \sum _{k=1}^{n}\sum _{i=k}^{n}\left( {\begin{array}{c}n\\ i\end{array}}\right) \left( {\begin{array}{c}i+k-1\\ 2k-1\end{array}}\right) = (\sqrt{5})^{n-1}\left( \left( \frac{\sqrt{5}+1}{2}\right) ^n-\left( \frac{\sqrt{5}-1}{2}\right) ^n\right) . \end{aligned}$$

(1)

Now, we can calculate the number of endomorphisms of $\mathscr {PO}_n$.

Theorem 3.7

The semigroup $\mathscr {PO}_n$ has

$$\begin{aligned}&3 + n! + (\sqrt{5})^{n-1}\left( \left( \frac{\sqrt{5}+1}{2}\right) ^n \!\!\! -\left( \frac{\sqrt{5}-1}{2}\right) ^n\right) \\&\quad + \sum _{k=1}^{n} (\sqrt{5})^{k-1}\left( \left( \frac{\sqrt{5}+1}{2}\right) ^k \!\!\! -\left( \frac{\sqrt{5}-1}{2}\right) ^k\right) \sum _{i=k}^{n}\left( {\begin{array}{c}n\\ i\end{array}}\right) \left( {\begin{array}{c}i+k-1\\ 2k-1\end{array}}\right) \end{aligned}$$

endomorphisms.

Proof

The number of endomorphisms of $\mathscr {PO}_n$ of type (b) and (d) is equal to

$$\begin{aligned} \sum _{e^2=e\in \mathscr {PO}_n}|E_{\mathscr {PO}_n}(e)|= & {} 1+\sum _{e^2=e\in \mathscr {PO}_n{\setminus }\{\emptyset \}}|\{f\in \mathscr {PO}_{|\mathop {\mathrm {Im}}\nolimits (e)|}\mid f^2=f\}| \\= & {} 1 + \sum _{k=1}^{n} |\{f\in \mathscr {PO}_k\mid f^2=f\}| |\{e\in J_k^{\mathscr {PO}_n}\mid e^2=e\}| \\= & {} 1 + \sum _{k=1}^{n} \left( 1+(\sqrt{5})^{k-1}\left( \left( \frac{\sqrt{5}+1}{2}\right) ^k\right. \right. \\&\left. \left. -\left( \frac{\sqrt{5}-1}{2}\right) ^k\right) \right) \sum _{i=k}^{n}\left( {\begin{array}{c}n\\ i\end{array}}\right) \left( {\begin{array}{c}i+k-1\\ 2k-1\end{array}}\right) \\= & {} 1 + \sum _{k=1}^{n}\sum _{i=k}^{n}\left( {\begin{array}{c}n\\ i\end{array}}\right) \left( {\begin{array}{c}i+k-1\\ 2k-1\end{array}}\right) + \sum _{k=1}^{n} (\sqrt{5})^{k-1}\left( \left( \frac{\sqrt{5}+1}{2}\right) ^k\right. \\&\left. -\left( \frac{\sqrt{5}-1}{2}\right) ^k\right) \sum _{i=k}^{n}\left( {\begin{array}{c}n\\ i\end{array}}\right) \left( {\begin{array}{c}i+k-1\\ 2k-1\end{array}}\right) , \end{aligned}$$

by Lemmas 3.5 and 3.6, i.e. equal to

$$\begin{aligned} 1+ & {} (\sqrt{5})^{n-1}\left( \left( \frac{\sqrt{5}+1}{2}\right) ^n-\left( \frac{\sqrt{5}-1}{2}\right) ^n\right) \\+ & {} \sum _{k=1}^{n} (\sqrt{5})^{k-1}\left( \left( \frac{\sqrt{5}+1}{2}\right) ^k-\left( \frac{\sqrt{5}-1}{2}\right) ^k\right) \sum _{i=k}^{n}\left( {\begin{array}{c}n\\ i\end{array}}\right) \left( {\begin{array}{c}i+k-1\\ 2k-1\end{array}}\right) , \end{aligned}$$

by the equality (1). Once again we have n! endomorphisms of type (c) and two automorphisms, so the result follows. $\square$