On the diameter of semigroups of transformations and partitions (Q6586625)

Let \(S\) be a semigroup and \(I\) be a right ideal of \(S\). A subset \(V\) of \(I\) is called a generating set for \(I\) if \(I=VS^{1}\), where \(S^{1}\) denotes the monoid obtained from \(S\) by adjoining an identity if necessary. When considering \(S\) being generated by a set as a right ideal, it is written \(S^{r}\) rather than \(S\). Thus, \(S^{r}\) is generated by \(V\subseteq S\) means \(S=VS^{1}\). If \(S=VS^{1}\) for a finite \(V\subseteq S\), then \(S^{r}\) is called finitely generated. Let \(\rho\) be an equivalence relation on \(S\). If \((a,b)\in\rho\) implies \((as,bs) \in \rho\) for all \(s\in S\), then \(\rho\) is called a right congruence. For a subset \(U\) of \(S\times S\), the smallest right congruence is called the right congruence generated by \(U\) and denoted by \(\langle U\rangle\). If \(\rho =\langle U \rangle\) for a finite \(U\subseteq S\times S\), then \(\rho\) is called finitely generated (as a right congruence). For \(U\subseteq S\times S\), if \(\rho = \langle U\rangle\), then for any \(a,b\in S\), it is known that \((a,b)\in\rho\) if and only if either \(a=b\) or there exists a sequence \N\[\Na\equiv u_{1}s_{1}\rightarrow v_{1}s_{1}\equiv u_{2}s_{2}\rightarrow \cdots \rightarrow v_{n-1}s_{n-1}\equiv u_{n}s_{n} \rightarrow v_{n}s_{n}\equiv b\N\]\Nfor some \(n\in \mathbb{N}\), where \((u_{i},v_{i})\in U\) or \((v_{i},u_{i})\in U\) and \(s_{i}\in S^{1}\) for each \(1\leq i\leq n\). This sequence is referred to as a \(U\)-sequence from \(a\) to \(b\) of length \(n\). The universal relation \(S\times S\) is also a right congruence on \(S\) which is called the universal right congruence and denoted by \(\omega_{S}^{r}\). For a subset \(U\) of \(S\times S\), let \(\omega_{S}^{r} =\langle U\rangle\). For any \(a\in S\), let \(d_{U}^{r}(a,a)=0\) and for any \(a,b\in S\) with \(a\neq b\), let \(d_{U}^{r}(a,b)\) denote the least positive integer \(n\) such that there is a \(U\)-sequence from \(a\) to \(b\) of length \(n\). Then the right \(U\)-diameter of \(S\) is defined by \N\[\ND_{r}(U,S)=\sup\{ d_{U}^{r}(a,b) : a,b\in S\},\N\]\Nand moreover, if \(\omega_{S}^{r}\) is finitely generated, the right diameter of \(S\) is defined by \N\[\ND_{r}(S)=\min \{ D_{r}(U,S) : \omega_{S}^{r} =\langle U\rangle \mbox{ where } U \mbox{ is finite}\,\}.\N\]\N\(S^{l}\), \(\omega_{S}^{l}\) (the universal left congruence on \(S\)) and \(D_{r}(S)\) (the left diameter of \(S\)) are defined similarly.\N\NThe purpose of this paper is to investigate, for various infinite semigroups of transformations and partitions, whether each such semigroup has a finitely generated universal right (left) congruence and determine its right (left) diameter if it has a finitely generated universal right (left) congruence. Before presenting some of the main results, it is better to introduce some of which semigroups of transformations and partitions are studied in the paper.\N\NFor an infinite set \(X\), let\N\begin{itemize}\N\item \(\mathcal{B}_{X}\) be the monoid of all binary relations on \(X\) (under composition),\N\item \(\mathcal{PT}_{X}\) be the partial transformation monoid on \(X\),\N\item \(\mathcal{I}_{X}\) be the symmetric inverse monoid on \(X\),\N\item \(\mathcal{T}_{X}\) be the full transformation monoid on \(X\),\N\item \(\mathcal{S}_{X}\) be the symmetric group on \(X\),\N\item \(\mathcal{F}_{X}\) be the submonoid of \(\mathcal{T}_{X}\) consisting of all finite-to-one transformations on \(X\), that is \N\[\N\mathcal{F}_{X}=\{\alpha\in\mathcal{T}_{X} :\lvert x\alpha^{-1}\rvert <\infty \mbox{ for all }x\in X \},\N\]\N\item \(\mathcal{I}nj_{X}\) be the submonoid of \(\mathcal{T}_{X}\) consisting of all injective transformations on \(X\),\N\item \(\mathcal{BL}_{X,q}\) be the Baer-Levi semigroup of type \(q\) on \(X\), that is \N\[\N\mathcal{BL}_{X,q}=\{ \alpha \in \mathcal{I}nj_{X} : \lvert X\setminus \mbox{im}\alpha \rvert =q \},\N\]\N\item \(\mathcal{BL}_{X}\) be the Baer-Levi semigroup of on \(X\): \(\mathcal{BL}_{X,q}\) for \(q=\lvert X\rvert\),\N\item \(\mathcal{S}urj_{X}\) be the submonoid of \(\mathcal{T}_{X}\) consisting of all surjective transformations on \(X\).\N\end{itemize}\NMoreover, \(\mathcal{P}_{X}\) and \(\mathcal{PB}_{X}\) denote the partition monoid and the partial Brauer monoid on \(X\), respectively.\N\NMost of the main results of the paper are summarised in the following table:\N\[\N\begin{array}{c|c|c|c|c|c|c|} \mbox{Semigroup } S & S^{r}\mbox{ f.g.?} & \omega_{S}^{r}\mbox{ f.g.?} & D_{r}(S) & S^{l}\mbox{ f.g.?} & \omega_{S}^{l}\mbox{ f.g.?} & D_{l}(S) \\\N\hline \mathcal{B}_{X}& \mbox{Yes} & \mbox{Yes} & 1 & \mbox{Yes} & \mbox{Yes} & 1 \\\N\hline \mathcal{PT}_{X}&\mbox{Yes} & \mbox{Yes} & 1 & \mbox{Yes} & \mbox{Yes} & 1 \\\N\hline \mathcal{I}_{X}& \mbox{Yes} & \mbox{Yes} & 2 & \mbox{Yes} & \mbox{Yes} & 2 \\\N\hline \mathcal{T}_{X}& \mbox{Yes} & \mbox{Yes} & 1 & \mbox{Yes} & \mbox{Yes} & 1 \\\N\hline \mathcal{S}_{X}& \mbox{Yes} & \mbox{No} &\mbox{n.a.}& \mbox{Yes} & \mbox{No} & \mbox{n.a.} \\\N\hline \mathcal{F}_{X}& \mbox{Yes} & \mbox{Yes} & 1 & \mbox{Yes} & \mbox{No} & \mbox{n.a.}\\\N\hline \mathcal{I}nj_{X}& \mbox{Yes} & \mbox{Yes} & 4 & \mbox{Yes} & \mbox{No} & \mbox{n.a.} \\\N\hline \mathcal{BL}_{X,q}& \mbox{Yes} & \mbox{No} & \mbox{n.a.} & \mbox{No} & \mbox{No} & \mbox{n.a.} \\\N\hline \mathcal{BL}_{X}& \mbox{Yes} & \mbox{Yes} & 3 & \mbox{No} & \mbox{No} & \mbox{n.a.} \\\N\hline \mathcal{BL}_{X}^{1}& \mbox{Yes} & \mbox{Yes} & 3 & \mbox{Yes} & \mbox{No} & \mbox{n.a.} \\\N\hline \mathcal{S}_{X}\cup\mathcal{BL}_{X}& \mbox{Yes} & \mbox{Yes} & 4 & \mbox{Yes} & \mbox{No} & \mbox{n.a.} \\\N\hline \mathcal{S}urj_{X}& \mbox{Yes} & \mbox{No} & \mbox{n.a.} & \mbox{Yes} & \mbox{Yes} & 4 \\\N\hline \mathcal{T}_{X}\setminus \mathcal{I}nj_{X}& \mbox{No} & \mbox{No} & \mbox{n.a.} & \mbox{Yes} & \mbox{Yes} & 2 \\\N\hline \mathcal{T}_{X}\setminus \mathcal{S}urj_{X}& \mbox{Yes} & \mbox{Yes} & 2 & \mbox{No} & \mbox{No} & \mbox{n.a.} \\\N\hline \mathcal{P}_{X}& \mbox{Yes} & \mbox{Yes} & 1 & \mbox{Yes} & \mbox{Yes} & 1 \\\N\hline \mathcal{PB}_{X}& \mbox{Yes} & \mbox{Yes} & 1 & \mbox{Yes} & \mbox{Yes} & 1\\\N\hline \end{array} \N\]\NMoreover, some more certain transformation semigroups including the dual Baer-Levi semigroups are defined and investigated.