On relative ranks of finite transformation semigroups with restricted range
UDC 512.5 We determine the relative rank of the semigroup ${\scr T }(X,Y)$ of all transformations on a finite chain $X$ with restricted range $Y\subseteq X$ modulo the set ${\scr OP }(X,Y)$ of all orientation-preserving transformations in ${\scr T }(X,Y).$ Moreover, we state the relative rank of the...
Gespeichert in:
| Datum: | 2021 |
|---|---|
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Englisch |
| Veröffentlicht: |
Institute of Mathematics, NAS of Ukraine
2021
|
| Online Zugang: | https://umj.imath.kiev.ua/index.php/umj/article/view/288 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Ukrains’kyi Matematychnyi Zhurnal |
| Завантажити файл: |  |
Institution
Ukrains’kyi Matematychnyi Zhurnal| _version_ | 1860506998244638720 |
|---|---|
| author | Dimitrova, I. Koppitz, J. I. Dimitrova, I. Koppitz, J. |
| author_facet | Dimitrova, I. Koppitz, J. I. Dimitrova, I. Koppitz, J. |
| author_sort | Dimitrova, I. |
| baseUrl_str | https://umj.imath.kiev.ua/index.php/umj/oai |
| collection | OJS |
| datestamp_date | 2025-03-31T08:48:07Z |
| description | UDC 512.5
We determine the relative rank of the semigroup ${\scr T }(X,Y)$ of all transformations on a finite chain $X$ with restricted range $Y\subseteq X$ modulo the set ${\scr OP }(X,Y)$ of all orientation-preserving transformations in ${\scr T }(X,Y).$ Moreover, we state the relative rank of the semigroup ${\scr OP }(X,Y)$ modulo the set ${\scr O}(X,Y)$ of all order-preserving transformations in ${\scr OP}(X,Y).$ In both cases we characterize the minimal relative generating sets.
  |
| doi_str_mv | 10.37863/umzh.v73i5.288 |
| first_indexed | 2026-03-24T02:02:19Z |
| format | Article |
| fulltext |
DOI: 10.37863/umzh.v73i5.288
UDC 512.5
I. Dimitrova (South-West University “Neofit Rilski”, Blagoevgrad, Bulgaria),
J. Koppitz (Institute of Mathematics and Informatics Bulgarian Academy of Sciences, Sofia, Bulgaria)
ON RELATIVE RANKS OF FINITE TRANSFORMATION SEMIGROUPS
WITH RESTRICTED RANGE
ПРО ВIДНОСНI РАНГИ НАПIВГРУП ФIНIТНИХ ПЕРЕТВОРЕНЬ
З ОБМЕЖЕНОЮ ОБЛАСТЮ ЗНАЧЕНЬ
We determine the relative rank of the semigroup \scrT (X,Y ) of all transformations on a finite chain X with restricted range
Y \subseteq X modulo the set \scrO \scrP (X,Y ) of all orientation-preserving transformations in \scrT (X,Y ). Moreover, we state the
relative rank of the semigroup \scrO \scrP (X,Y ) modulo the set \scrO (X,Y ) of all order-preserving transformations in \scrO \scrP (X,Y ).
In both cases we characterize the minimal relative generating sets.
Визначено вiдносний ранг напiвгрупи \scrT (X,Y ) усiх перетворень на скiнченному ланцюгу X з обмеженою областю
значень Y \subseteq X за модулем множини \scrO \scrP (X,Y ) усiх перетворень у \scrT (X,Y ), що зберiгають орiєнтацiю. Крiм того,
встановлено вiдносний ранг напiвгрупи \scrO \scrP (X,Y ) за модулем множини \scrO (X,Y ) усiх перетворень в \scrO \scrP (X,Y ),
що зберiгають порядок. В обох випадках охарактеризовано вiдповiднi мiнiмальнi породжуючi множини.
1. Introduction and preliminaries. Let S be a semigroup. The rank of S (denoted by \mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}S ) is
defined to be the minimal number of elements of a generating set of S. The ranks of various known
semigroups have been calculated [7, 8, 10, 11]. For a set A \subseteq S, the relative rank of S modulo A,
denoted by \mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}(S : A), is the minimal cardinality of a set B \subseteq S such that A \cup B generates S.
It follows immediately from the definition that \mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}(S : \varnothing ) = \mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}S, \mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}(S : S) = 0, \mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}(S :
A) = \mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}(S : \langle A\rangle ) and \mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}(S : A) = 0 if and only if A is a generating set for S. The relative
rank of a semigroup modulo a suitable set was first introduced by Ruškuc in [14] in order to describe
the generating sets of semigroups with infinite rank. In [12], Howie, Ruškuc, and Higgins considered
the relative ranks of the monoid \scrT (X) of all full transformations on X, where X is an infinite
set, modulo some distinguished subsets of \scrT (X). They showed that \mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}(\scrT (X) : \scrS (X)) = 2,
\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}(\scrT (X) : \scrE (X)) = 2 and \mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}(\scrT (X) : J) = 0, where \scrS (X) is the symmetric group on X,
\scrE (X) is the set of all idempotent transformations on X and J is the top \scrJ -class of \scrT (X), i.e.,
J = \{ \alpha \in \scrT (X) : | X\alpha | = | X| \} . But also if the rank is finite, the relative rank gives information
about the generating sets. In the present paper, we will determine the relative rank for a particular
semigroup of transformations on a finite set.
Let X be a finite chain, say X = \{ 1 < 2 < . . . < n\} for a natural number n. A transformation
\alpha \in \scrT (X) is called order-preserving if x \leq y implies x\alpha \leq y\alpha for all x, y \in X. We denote by
\scrO (X) the submonoid of \scrT (X) of all order-preserving full transformations on X. The relative rank
of \scrT (X) modulo \scrO (X) was considered by Higgins, Mitchell, and Ruškuc in [9]. They showed
that \mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}(\scrT (X) : \scrO (X)) = 1, when X is an arbitrary countable chain or an arbitrary well-ordered
set, while \mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}(\scrT (\BbbR ) : \scrO (\BbbR )) is uncountable, by considering the usual order of the set \BbbR of real
numbers. In [2], Dimitrova, Fernandes, and Koppitz studied the relative rank of the semigroup
\scrO (X) modulo J = \{ \alpha \in \scrO (X) : | X\alpha | = | X| \} for an infinite countable chain X. We say that
a transformation \alpha \in \scrT (X) is orientation-preserving if there are subsets X1, X2 \subseteq X with \varnothing \not =
c\bigcirc I. DIMITROVA, J. KOPPITZ, 2021
ISSN 1027-3190. Укр. мат. журн., 2021, т. 73, № 5 617
618 I. DIMITROVA, J. KOPPITZ
\not = X1 < X2 (i.e., x1 < x2 for x1 \in X1 and x2 \in X2), X = X1\cup X2, and x\alpha \leq y\alpha , whenever either
(x, y) \in X2
1 \cup X2
2 with x \leq y or (x, y) \in X2 \times X1. Note that X2 = \varnothing provides \alpha \in \scrO (X). We
denote by \scrO \scrP (X) the submonoid of \scrT (X) of all orientation-preserving full transformations on X.
An equivalent notion of an orientation-preserving transformation was first introduced by McAlister
in [13] and, independently, by Catarino and Higgins in [1]. It is clear that \scrO (X) is a submonoid
of \scrO \scrP (X), i.e., \scrO (X) \subset \scrO \scrP (X) \subset \scrT (X). It is interesting to note that the relative rank of \scrT (X)
modulo \scrO \scrP (X) as well as the relative rank of \scrO \scrP (X) modulo \scrO (X) is one (see [1, 12]), but the
situation will change if one considers transformations with restricted range.
Let Y = \{ a1 < a2 < . . . < am\} be a nonempty subset of X, for a natural number m \leq n,
and denote by \scrT (X,Y ) the subsemigroup \{ \alpha \in \scrT (X) : X\alpha \subseteq Y \} of \scrT (X) of all transformations
with range (image) restricted to Y. The set \scrT (X,Y ) coincides with \scrT (X), whenever Y = X (i.e.,
m = n). In 1975, Symons [15] introduced and studied the semigroup \scrT (X,Y ), which is called
semigroup of transformations with restricted range. Recently, the rank of \scrT (X,Y ) was computed
by Fernandes and Sanwong in [6]. They proved that the rank of \scrT (X,Y ) is the Sterling number
S(n,m) of second kind with | X| = n and | Y | = m. The rank of the order-preserving counterpart
\scrO (X,Y ) of \scrT (X,Y ) was studied in [4] by Fernandes, Honyam, Quinteiro, and Singha. The authors
found that \mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}\scrO (X,Y ) =
\biggl(
n - 1
m - 1
\biggr)
+
\bigm| \bigm| Y \#
\bigm| \bigm| , where Y \# denotes the set of all y \in Y with one of
the following properties: (i) y has no successor in X; (ii) y is no successor of any element in X;
(iii) both the successor of Y and the element whose successor is y belong to Y. Moreover, the
regularity and the rank of the semigroup \scrO \scrP (X,Y ) were studied by the same authors in [5]. They
showed that \mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}\scrO \scrP (X,Y ) =
\biggl(
n
m
\biggr)
. In [16], Tinpun and Koppitz studied the relative rank of
\scrT (X,Y ) modulo \scrO (X,Y ) and proved that \mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}(\scrT (X,Y ) : \scrO (X,Y )) = S(n,m) -
\biggl(
n - 1
m - 1
\biggr)
+ a,
where a \in \{ 0, 1\} depending on the set Y. In this paper, we determine the relative rank of \scrO \scrP (X,Y )
modulo \scrO (X,Y ) as well as the relative rank of \scrT (X,Y ) modulo \scrO \scrP (X,Y ).
Let \alpha \in \scrT (X,Y ). The kernel of \alpha is the equivalence relation \mathrm{k}\mathrm{e}\mathrm{r}\alpha with (x, y) \in \mathrm{k}\mathrm{e}\mathrm{r}\alpha if x\alpha =
= y\alpha . It corresponds uniquely to a partition on X. This justifies to regard \mathrm{k}\mathrm{e}\mathrm{r}\alpha as a partition on X.
We will call a block of this partition as \mathrm{k}\mathrm{e}\mathrm{r}\alpha -class. In particular, the sets x\alpha - 1 = \{ y \in X : y\alpha = x\} ,
for x \in X\alpha , are the \mathrm{k}\mathrm{e}\mathrm{r}\alpha -classes. We say that a partition P is a subpartition of a partition Q of X
if for all p \in P there is q \in Q with p \subseteq q. A set T \subseteq X with
\bigm| \bigm| T \cap x\alpha - 1
\bigm| \bigm| = 1, for all x \in X\alpha , is
called a transversal of \mathrm{k}\mathrm{e}\mathrm{r}\alpha . Let A \subseteq X. Then \alpha | A : A \rightarrow Y denotes the restriction of \alpha to A and
A will be called convex if x < y < z with x, z \in A implies y \in A.
Let l \in \{ 1, . . . ,m\} . We denote by \scrP l the set of all partitions \{ A1, . . . , Al\} of X such that A2 <
< A3 < . . . < Al are convex sets (if l > 1) and A1 is the union of two convex sets with 1, n \in A1.
Further, let \scrQ l be the set of all partitions \{ A1, . . . , Al\} of X such that A1 < A2 < . . . < Al are
convex and let \scrR l be the set of all partitions of X, which not belong to \scrQ l \cup \scrP l. We observe that
\mathrm{k}\mathrm{e}\mathrm{r}\beta \in \scrQ l \cup \scrP l, whenever \beta \in \scrO \scrP (X,Y ) with | X\beta | = l. In particular, \mathrm{k}\mathrm{e}\mathrm{r}\beta \in \scrQ l, whenever
\beta \in \scrO (X,Y ).
Let us consider the case l = m > 1. For P \in \scrP m with the blocks A1, A2 < . . . < Am, let \alpha P
be the transformation on X defined by
ISSN 1027-3190. Укр. мат. журн., 2021, т. 73, № 5
ON RELATIVE RANKS OF FINITE TRANSFORMATION SEMIGROUPS WITH RESTRICTED RANGE 619
x\alpha P := ai, whenever x \in Ai for 1 \leq i \leq m,
in the case 1 /\in Y or n /\in Y and
x\alpha P :=
\left\{ ai+1, if x \in Ai for 1 \leq i < m,
a1, if x \in Am,
in the case 1, n \in Y. Clearly, \mathrm{k}\mathrm{e}\mathrm{r}\alpha P = P. For X1 = \{ 1, . . . ,\mathrm{m}\mathrm{a}\mathrm{x}Am\} , X2 = \{ \mathrm{m}\mathrm{a}\mathrm{x}Am+1, . . . , n\}
in the case 1 /\in Y or n /\in Y and X1 = \{ 1, . . . ,\mathrm{m}\mathrm{a}\mathrm{x}Am - 1\} , X2 = \{ \mathrm{m}\mathrm{a}\mathrm{x}Am - 1 + 1, . . . , n\} in the
case 1, n \in Y, where \mathrm{m}\mathrm{a}\mathrm{x}Am (\mathrm{m}\mathrm{a}\mathrm{x}Am - 1) denotes the greatest element in the set Am (Am - 1,
respectively), we can easy verify that \alpha P is orientation-preserving.
Further, let \eta \in \scrT (X,Y ) be defined by
x\eta :=
\left\{
ai+1, if ai \leq x < ai+1, 1 \leq i < m,
a1, if x = am,
a\Gamma , otherwise,
with \Gamma :=
\left\{ 1, if 1 /\in Y,
2, otherwise,
in the case 1 /\in Y or n /\in Y and
x\eta :=
\left\{ ai+1, if ai \leq x < ai+1, 1 \leq i < m,
a1 = 1, if x = am = n,
in the case that 1, n \in Y. Notice that P0 := \mathrm{k}\mathrm{e}\mathrm{r} \eta \in \scrP m if 1 /\in Y or n /\in Y and \mathrm{k}\mathrm{e}\mathrm{r} \eta \in \scrQ m
if 1, n \in Y. In fact, \eta \in \scrO \scrP (X,Y ) with X1 = \{ 1, 2, . . . , am - 1\} and X2 = \{ am, am + 1, . . . , n\} .
Moreover, \eta | Y is a permutation on Y, namely
\eta | Y =
\Biggl(
a1 . . . am - 1 am
a2 . . . am a1
\Biggr)
.
We will denote by \scrS (Y ) the set of all permutations on Y. Note that \beta \in \scrO (X,Y ) implies that either
\beta | Y is the identity mapping on Y or \beta | Y /\in \scrS (Y ).
2. The relative rank of \bfscrO \bfscrP (\bfitX ,\bfitY ) modulo \bfscrO (\bfitX ,\bfitY ). In this section, we determine the
relative rank of \scrO \scrP (X,Y ) modulo \scrO (X,Y ). A part of these results were presented at the 47 th
spring conference of the Union of Bulgarian mathematicians in March 2018 and are published in the
proceedings of this conference [3].
If m = 1, then \scrO \scrP (X,Y ) is the set of all constant mappings and coincides with \scrO (X,Y ), i.e.,
\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}(\scrO \scrP (X,Y ) : \scrO (X,Y )) = 0. So, we admit that m > 1.
First, we will show that
\scrA := \{ \alpha P : P \in \scrP m\} \cup \{ \eta \}
is a relative generating set of \scrO \scrP (X,Y ) modulo \scrO (X,Y ). Notice that \eta = \alpha P0 if 1 /\in Y or n /\in Y.
Lemma 1. For each \alpha \in \scrO \scrP (X,Y ) with \mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}\alpha = m, there is \widehat \alpha \in \{ \alpha P : P \in \scrP m\} \cup \scrO (X,Y )
with \mathrm{k}\mathrm{e}\mathrm{r}\alpha = \mathrm{k}\mathrm{e}\mathrm{r} \widehat \alpha .
ISSN 1027-3190. Укр. мат. журн., 2021, т. 73, № 5
620 I. DIMITROVA, J. KOPPITZ
Proof. Let \alpha \in \scrO \scrP (X,Y ) and let X1, X2 \subseteq X as in the definition of an orientation-preserving
transformation. If X2 = \varnothing , then \alpha \in \scrO (X,Y ). Suppose now that X2 \not = \varnothing and let X1\alpha =
= \{ x1 < . . . < xr\} and X2\alpha = \{ y1 < . . . < ys\} for suitable natural numbers r and s. We observe
that X1\alpha and X2\alpha have at most one joint element (only x1 = ys could be possible). If x1 \not = ys,
then
\mathrm{k}\mathrm{e}\mathrm{r}\alpha =
\bigl\{
x1\alpha
- 1 < . . . < xr\alpha
- 1 < y1\alpha
- 1 < . . . < ys\alpha
- 1
\bigr\}
= \mathrm{k}\mathrm{e}\mathrm{r} \widehat \alpha
with
\widehat \alpha =
\Biggl(
x1\alpha
- 1 . . . xr\alpha
- 1 y1\alpha
- 1 . . . ys\alpha
- 1
a1 . . . ar ar+1 . . . ar+s
\Biggr)
\in \scrO (X,Y ).
If x1 = ys, then 1, n \in x1\alpha
- 1 = ys\alpha
- 1 and \mathrm{k}\mathrm{e}\mathrm{r}\alpha = \mathrm{k}\mathrm{e}\mathrm{r}\alpha P with
P =
\bigl\{
x1\alpha
- 1, x2\alpha
- 1 < . . . < xr\alpha
- 1 < y1\alpha
- 1 < . . . < ys - 1\alpha
- 1
\bigr\}
\in \scrP m.
Lemma 1 is proved.
Proposition 1. \scrO \scrP (X,Y ) = \langle \scrO (X,Y ),\scrA \rangle .
Proof. Let \beta \in \scrO \scrP (X,Y ) with \mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}\beta = m. Then there is \theta \in \{ \alpha P : P \in \scrP m\} \cup \scrO (X,Y )
with \mathrm{k}\mathrm{e}\mathrm{r}\beta = \mathrm{k}\mathrm{e}\mathrm{r} \theta by Lemma 1. In particular, there is r \in \{ 0, . . . ,m - 1\} with a1\theta
- 1 = ar+1\beta
- 1.
Then it is easy to verify that \beta = \theta \eta r, where \eta 0 = \eta m.
Admit now that i = \mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}\beta < m. Suppose that \mathrm{k}\mathrm{e}\mathrm{r}\beta \in \scrP i, say \mathrm{k}\mathrm{e}\mathrm{r}\beta = \{ A1, A2 < . . . < Ai\}
with 1, n \in A1. Then there is a subpartition P \prime \in \scrP m of \mathrm{k}\mathrm{e}\mathrm{r}\beta . We put \theta = \alpha P \prime , a = \mathrm{m}\mathrm{i}\mathrm{n}X\beta ,
and let T be a transversal of \mathrm{k}\mathrm{e}\mathrm{r} \theta . In particular, we have Y = \{ x(\theta | T )\eta k : x \in T\} for all k \in
\in \{ 1, . . . ,m\} . Since both mappings \theta | T : T \rightarrow Y and \eta | Y : Y \rightarrow Y are bijections, there is k \in
\in \{ 1, . . . ,m\} with a1((\theta | T )\eta k) - 1\beta = a and a1((\theta | T )\eta k+1) - 1\beta \not = a. Moreover, since (\theta | T )\eta k is
a bijection from T to Y and both transformations \theta \eta k and \beta are orientation-preserving, it is easy
to verify that f\ast =
\bigl(
(\theta | T )\eta k
\bigr) - 1
\beta can be extended to an orientation-preserving transformation f
defined by
xf =
\left\{
a1f
\ast , if x < a1,
aif
\ast , if ai \leq x < ai+1, 1 \leq i < m,
amf\ast , if am \leq x,
i.e., f and f\ast coincide on Y. Moreover, a1f = a1f
\ast = a1
\bigl(
(\theta | T )\eta k
\bigr) - 1
\beta = a. In order to show
that f is order-preserving, it left to verify that nf \not = a. Assume that nf = a, where n \geq am.
Then nf = amf\ast = amf, i.e., (n, am) \in \mathrm{k}\mathrm{e}\mathrm{r} f and n\eta = am\eta = a1. So, there is x\ast \in T
such that x\ast
\bigl(
(\theta | T )\eta k
\bigr)
= am, i.e., x\ast = am
\bigl(
(\theta | T )\eta k
\bigr) - 1
. Now, we have a = nf = amf\ast =
= am
\bigl(
(\theta | T )\eta k
\bigr) - 1
\beta = am(\eta k| Y ) - 1(\theta | T ) - 1\beta = a1(\eta | Y ) - 1(\eta k| Y ) - 1(\theta | T ) - 1\beta = a1((\theta | T )\eta k+1) - 1\beta \not =
\not = a, a contradiction.
Finally, we will verify that \beta = \theta \eta kf \in \langle \scrO (X,Y ),\scrA \rangle . For this let x \in X. Then there is \widetilde x \in T
such that (x, \widetilde x) \in \mathrm{k}\mathrm{e}\mathrm{r}\beta . So, we have x\theta \eta kf = x\theta \eta kf\ast = \widetilde x\theta \eta k\bigl( (\theta | T )\eta k\bigr) - 1
\beta = \widetilde x\beta = x\beta .
Suppose now that \mathrm{k}\mathrm{e}\mathrm{r}\beta /\in \scrP i and, thus, \mathrm{k}\mathrm{e}\mathrm{r}\beta \in \scrQ i. Let X\beta = \{ b1, . . . , bi\} such that
b1\beta
- 1 < . . . < bi\beta
- 1. Then we define a transformation \varphi by x\varphi = aj for all x \in bj - 1\beta
- 1
and 2 \leq j \leq i+ 1. Clearly, \varphi \in \scrO (X,Y ). Further, we define a transformation \nu \in \scrT (X,Y ) by
x\nu =
\left\{ bj - 1, if aj \leq x < aj+1, 2 \leq j \leq i,
bi, otherwise.
ISSN 1027-3190. Укр. мат. журн., 2021, т. 73, № 5
ON RELATIVE RANKS OF FINITE TRANSFORMATION SEMIGROUPS WITH RESTRICTED RANGE 621
Since \beta is orientation-preserving, there is k \in \{ 1, . . . , i\} such that k = i or b1 < . . . < bk - 1 <
< bk < . . . < bi. Then X1 = \{ a1, . . . , ak+1 - 1\} and X2 = \{ ak+1, . . . , n\} gives a partition of X
providing that \nu is orientation-preserving. Clearly, \mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k} \nu = i and 1\nu = n\nu = bi. Thus, it is easy
to verify that \mathrm{k}\mathrm{e}\mathrm{r} \nu \in \scrP i. Hence, \nu \in \langle \scrO (X,Y ),\scrA \rangle by the previous case and it remains to show
that \beta = \varphi \nu \in \langle \scrO (X,Y ),\scrA \rangle . For this let x \in X. Then x \in bj\beta
- 1 for some j \in \{ 1, . . . , i\} , i.e.,
x\varphi \nu = aj+1\nu = bj = x\beta .
Proposition 1 is proved.
The previous proposition shows that \scrA is a relative generating set for \scrO \scrP (X,Y ) modulo
\scrO (X,Y ). It remains to show that \scrA is of minimal size.
Lemma 2. Let B \subseteq \scrO \scrP (X,Y ) be a relative generating set of \scrO \scrP (X,Y ) modulo \scrO (X,Y ).
Then \scrP m \subseteq \{ \mathrm{k}\mathrm{e}\mathrm{r}\alpha : \alpha \in B\} .
Proof. Let P \in \scrP m. Since \alpha P \in \scrO \scrP (X,Y ) = \langle \scrO (X,Y ), B\rangle , there are \theta 1 \in \scrO (X,Y ) \cup B
and \theta 2 \in \scrO \scrP (X,Y ) with \alpha P = \theta 1\theta 2. Because of \mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}\alpha P = m, we obtain \mathrm{k}\mathrm{e}\mathrm{r}\alpha P = \mathrm{k}\mathrm{e}\mathrm{r} \theta 1. Since
1\alpha P = n\alpha P , we conclude that \theta 1 /\in \scrO (X,Y ), i.e., \theta 1 \in B with \mathrm{k}\mathrm{e}\mathrm{r} \theta 1 = \mathrm{k}\mathrm{e}\mathrm{r}\alpha P = P.
Lemma 2 is proved.
In order to find a formula for the number of elements in \scrP m, we have to compute the number of
possible partitions of X into m+ 1 convex sets. This number is
\biggl(
n - 1
m
\biggr)
.
Remark 1. | \scrP m| =
\biggl(
n - 1
m
\biggr)
.
Now, we are able to state the main result of the section. The relative rank of \scrO \scrP (X,Y ) modulo
\scrO (X,Y ) depends of the fact whether both 1 and n belong to Y or not.
Theorem 1. For each 1 < m < n \in \BbbN ,
1) \mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}(\scrO \scrP (X,Y ) : \scrO (X,Y )) =
\biggl(
n - 1
m
\biggr)
if 1 /\in Y or n /\in Y ;
2) \mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}(\scrO \scrP (X,Y ) : \scrO (X,Y )) = 1 +
\biggl(
n - 1
m
\biggr)
if \{ 1, n\} \subseteq Y.
Proof. 1. Note that \mathrm{k}\mathrm{e}\mathrm{r} \eta \in \scrP m and \eta = \alpha P0 . Hence, the set \scrA = \{ \alpha P : P \in \scrP m\} is a
generating set of \scrO \scrP (X,Y ) modulo \scrO (X,Y ) by Proposition 1, i.e., the relative rank of \scrO \scrP (X,Y )
modulo \scrO (X,Y ) is bounded by the cardinality of \scrP m, which is
\biggl(
n - 1
m
\biggr)
by Remark 1. But this
number cannot be reduced by Lemma 2.
2. Let B \subseteq \scrO \scrP (X,Y ) be a relative generating set of \scrO \scrP (X,Y ) modulo \scrO (X,Y ). By
Lemma 2, we know that \scrP m \subseteq \{ \mathrm{k}\mathrm{e}\mathrm{r}\alpha : \alpha \in B\} . Assume that the equality holds. Note that
\mathrm{k}\mathrm{e}\mathrm{r} \eta \in \scrQ m and \eta is not order-preserving. Hence, there are \theta 1, . . . , \theta l \in \scrO (X,Y ) \cup B for a sui-
table natural number l, such that \eta = \theta 1 . . . \theta l. From \mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k} \eta = m, we obtain \mathrm{k}\mathrm{e}\mathrm{r} \theta 1 = \mathrm{k}\mathrm{e}\mathrm{r} \eta and
\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k} \theta i = m for i \in \{ 1, . . . , l\} and, thus, \{ 1, n\} \subseteq Y implies (1, n) /\in \mathrm{k}\mathrm{e}\mathrm{r} \theta i for i \in \{ 2, . . . , l\} .
This implies \theta 2, . . . , \theta l \in \scrO (X,Y ). Since \mathrm{k}\mathrm{e}\mathrm{r} \theta 1 = \mathrm{k}\mathrm{e}\mathrm{r} \eta /\in \scrP m, we get \theta 1 \in \scrO (X,Y ), and, con-
sequently, \eta = \theta 1\theta 2 . . . \theta l \in \scrO (X,Y ), a contradiction. So, we have verified that | \scrP m| < | B| , i.e.,
the relative rank of \scrO \scrP (X,Y ) modulo \scrO (X,Y ) is greater than
\biggl(
n - 1
m
\biggr)
. But it is bounded by
1 +
\biggl(
n - 1
m
\biggr)
due to Proposition 1. This proves the assertion.
Theorem 1 is proved.
ISSN 1027-3190. Укр. мат. журн., 2021, т. 73, № 5
622 I. DIMITROVA, J. KOPPITZ
We finish this section with the characterization of the minimal relative generating sets of
\scrO \scrP (X,Y ) modulo \scrO (X,Y ). We will recognize that among them there are sets with size greater
than \mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}
\bigl(
\scrO \scrP (X,Y ) : \scrO (X,Y )
\bigr)
.
Theorem 2. Let B \subseteq \scrO \scrP (X,Y ). Then B is a minimal relative generating set of \scrO \scrP (X,Y )
modulo \scrO (X,Y ) if and only if for the set \widetilde B = \{ \beta \in B : \mathrm{k}\mathrm{e}\mathrm{r}\beta \in \scrQ m\} \subseteq B the following three
statements are satisfied:
(i) \scrP m \subseteq
\bigl\{
\mathrm{k}\mathrm{e}\mathrm{r}\beta : \beta \in B \setminus \widetilde B\bigr\} ,
(ii) | B \setminus \widetilde B| = | \scrP m| ,
(iii) \eta | Y \in \langle \beta | Y : \beta \in B\rangle but \eta | Y /\in
\bigl\langle
\beta | Y : \beta \in B \setminus \{ \gamma \}
\bigr\rangle
for any \gamma \in \widetilde B.
Proof. Suppose that the conditions (i) – (iii) are satisfied for \widetilde B = \{ \beta \in B : \mathrm{k}\mathrm{e}\mathrm{r}\beta \in \scrQ m\} . We
will show that \scrA \subseteq \langle \scrO (X,Y ), B\rangle . Let \alpha \in \scrA \setminus \{ \eta \} . Then there is a partition P = \{ A1, A2 < . . .
. . . < Am\} \in \scrP m such that
\alpha = \alpha P =
\Biggl(
A1 A2 . . . Am
a1 a2 . . . am
\Biggr)
, if 1 /\in Y or n /\in Y,
or
\alpha = \alpha P =
\Biggl(
A1 A2 . . . Am - 1 Am
a2 a3 . . . am a1
\Biggr)
, if 1, n \in Y.
Notice that in the latter case a1 = 1 and am = n.
Further, from (i) it follows that there is \beta \in B with \mathrm{k}\mathrm{e}\mathrm{r}\beta = \mathrm{k}\mathrm{e}\mathrm{r}\alpha P , i.e., \beta = \alpha P or
\beta =
\Biggl(
A1 A2 . . . Am - i+1 Am - i+2 . . . Am
ai ai+1 . . . am a1 . . . ai - 1
\Biggr)
for some i \in \{ 3, . . . ,m\} . It is easy to verify that \alpha P = \beta k \in \langle B\rangle for a suitable natural number k.
Hence, \{ \alpha P : P \in \scrP m\} \subseteq \langle \scrO (X,Y ), B\rangle . Further, \mathrm{k}\mathrm{e}\mathrm{r} \eta \in \scrP m, whenever 1 /\in Y or n /\in Y, and
\mathrm{k}\mathrm{e}\mathrm{r} \eta \in \scrQ m otherwise. Thus, there is \delta \in \langle \scrO (X,Y ), B\rangle with \mathrm{k}\mathrm{e}\mathrm{r} \delta = \mathrm{k}\mathrm{e}\mathrm{r} \eta . Then we obtain as
above that \eta = \delta l \in \langle \scrO (X,Y ), B\rangle for a suitable natural number l. Consequently, \langle \scrO (X,Y ),\scrA \rangle \subseteq
\subseteq \langle \scrO (X,Y ), B\rangle . By Proposition 1, we obtain \scrO \scrP (X,Y ) = \langle \scrO (X,Y ), B\rangle . The generating set B
is minimal by properties (i) and (ii) together with Lemma 2 and by the property (iii) of \widetilde B.
Conversely, let B be a minimal relative generating set of \scrO \scrP (X,Y ) modulo \scrO (X,Y ). By
Lemma 2, there is a set B \subseteq B such that \scrP m = \{ \mathrm{k}\mathrm{e}\mathrm{r}\beta : \beta \in B\} and
\bigm| \bigm| B\bigm| \bigm| = | \scrP m| . Since
\scrO \scrP (X,Y ) = \langle \scrO (X,Y ), B\rangle , there are \beta 1, . . . , \beta k \in \scrO (X,Y ) \cup B such that \eta = \beta 1 . . . \beta k. Without
loss of generality, we can assume that there is not \gamma \in
\bigl\{
\beta i : 1 \leq i \leq k, \mathrm{k}\mathrm{e}\mathrm{r}\beta i \in \scrQ m
\bigr\}
=: \widehat B such
that \eta is a product of transformations in B \cup ( \widehat B \setminus \{ \gamma \} ). In the first part of the proof, we have shown
that B \cup \widehat B is a relative generating set of \scrO \scrP (X,Y ) modulo \scrO (X,Y ). Because of the minimality
of B, we obtain B = B \cup \widehat B, where
\bigl\{
\mathrm{k}\mathrm{e}\mathrm{r}\beta : \beta \in B \setminus \widehat B\bigr\} \supseteq \scrP m, | B \setminus \widehat B| = | B| = | \scrP m| and
\eta | Y \in \langle \beta | Y : \beta \in B\rangle but \eta | Y /\in
\bigl\langle
\beta | Y : \beta \in B \setminus \{ \gamma \}
\bigr\rangle
for any \gamma \in \widehat B.
Theorem 2 is proved.
In particular, for the relative generating sets of minimal size we have the following remark.
Remark 2. B \subseteq \scrO \scrP (X,Y ) is a relative generating set of \scrO \scrP (X,Y ) modulo \scrO (X,Y ) of
minimal size if and only if | \widetilde B| = 1 if 1, n \in Y and \widetilde B = \varnothing , otherwise.
ISSN 1027-3190. Укр. мат. журн., 2021, т. 73, № 5
ON RELATIVE RANKS OF FINITE TRANSFORMATION SEMIGROUPS WITH RESTRICTED RANGE 623
3. The relative rank of \bfscrT (\bfitX ,\bfitY ) modulo \bfscrO \bfscrP (\bfitX ,\bfitY ). In this section, we determine
the relative rank of \scrT (X,Y ) modulo \scrO \scrP (X,Y ) and characterize all minimal relative genera-
ting sets of \scrT (X,Y ) modulo \scrO \scrP (X,Y ). Since \scrO (X,Y ) \leq \scrO \scrP (X,Y ), we see immediately that
\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}(\scrT (X,Y ) : \scrO \scrP (X,Y )) \leq S(n,m) -
\biggl(
n - 1
m - 1
\biggr)
+ 1. First, we state a sufficient condition for a
set B \subseteq \scrT (X,Y ) to be a relative generating set of \scrT (X,Y ) modulo \scrO \scrP (X,Y ).
Lemma 3. Let B \subseteq \scrT (X,Y ). If \scrR m \subseteq \{ \mathrm{k}\mathrm{e}\mathrm{r}\beta : \beta \in B\} and \scrS (Y ) \subseteq
\bigl\langle
\{ \beta | Y : \beta \in B\} , \eta | Y
\bigr\rangle
,
then \langle \scrO \scrP (X,Y ), B\rangle = \scrT (X,Y ).
Proof. Let \gamma \in \scrT (X,Y ) with \mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k} \gamma = k \leq m. We will consider two cases.
Case 1. Suppose that \mathrm{k}\mathrm{e}\mathrm{r} \gamma \in \scrR k. Then \mathrm{k}\mathrm{e}\mathrm{r} \gamma contains a non-convex set which cannot be
decomposed into two convex sets, which contain 1 and n, respectively. Since k \leq m, we can divide
the partition \mathrm{k}\mathrm{e}\mathrm{r} \gamma into a partition P \in \scrR m such that P contains a non-convex set which cannot
be decomposed into two convex sets, which contain 1 and n, respectively (if k = m, then we put
P = \mathrm{k}\mathrm{e}\mathrm{r} \gamma ). Since \scrR m \subseteq \{ \mathrm{k}\mathrm{e}\mathrm{r}\beta : \beta \in B\} , there is \lambda \in B with \mathrm{k}\mathrm{e}\mathrm{r}\lambda = P. It is clear that X\lambda = Y.
Further, let X\gamma = \{ y1 < y2 < . . . < yk\} and define the sets
Ai =
\bigl\{
x \in Y : x\lambda - 1 \subseteq yi\gamma
- 1
\bigr\}
for i = 1, . . . , k. It is clear that \{ A1, A2, . . . , Ak\} is a partition of Y. Moreover, let \{ C1 < C2 < . . .
. . . < Ck\} \in \scrQ k be a partition of X such that | Ci \cap Y | = | Ai| for all i = 1, . . . , k. Let Ai = \{ ai1 <
< ai2 < . . . < aiti\} and Ci\cap Y = \{ ci1 < ci2 < . . . < citi\} with ti \in \{ 1, . . . ,m\} for i \in \{ 1, . . . , k\} .
We define a bijection
\sigma :
k\bigcup
i=1
Ai = Y - \rightarrow
k\bigcup
i=1
(Ci \cap Y ) = Y
on Y with ail\sigma = cil for l = 1, . . . , ti and i = 1, . . . , k. Since \sigma \in \scrS (Y ) and \scrS (Y ) \subseteq
\bigl\langle
\{ \beta | Y :
\beta \in B\} , \eta | Y
\bigr\rangle
, there is \mu \in \langle B, \eta \rangle with \mu | Y = \sigma .
Finally, we define a transformation \nu \in \scrO (X,Y ) \subseteq \scrO \scrP (X,Y ) with \mathrm{k}\mathrm{e}\mathrm{r} \nu = \{ C1 < C2 < . . .
. . . < Ck\} and x\nu = yi for all x \in Ci and i = 1, . . . , k.
Therefore, we have \lambda , \mu , \nu \in \langle \scrO \scrP (X,Y ), B\rangle and it remains to show that \gamma = \lambda \mu \nu , i.e., \gamma \in
\in \langle \scrO \scrP (X,Y ), B\rangle . Let x \in X. Then x\gamma = yi for some i \in \{ 1, . . . , k\} and we get
x\gamma = yi \Rightarrow x\lambda = z \in Ai \Rightarrow z\mu = u \in Ci \cap Y \Rightarrow u\nu = yi.
Hence, x\gamma = yi = x(\lambda \mu \nu ) and we conclude \gamma = \lambda \mu \nu .
Case 2. Suppose that \mathrm{k}\mathrm{e}\mathrm{r} \gamma /\in \scrR k, i.e., \mathrm{k}\mathrm{e}\mathrm{r} \gamma \in \scrQ k \cup \scrP k and there is \rho 1 \in \scrO \scrP (X,Y ) with
\mathrm{k}\mathrm{e}\mathrm{r} \rho 1 = \mathrm{k}\mathrm{e}\mathrm{r} \gamma . Further, there is a partition P = \{ Dy : y \in X\rho 1\} \in \scrR k such that y \in Dy for all
y \in X\rho 1. Then we define a transformation \rho 2 : X \rightarrow X\gamma with \mathrm{k}\mathrm{e}\mathrm{r} \rho 2 = P and \{ x\rho 2\} = y\rho - 1
1 \gamma
for all x \in Dy and y \in X\rho 1. Since \mathrm{k}\mathrm{e}\mathrm{r} \rho 1 = \mathrm{k}\mathrm{e}\mathrm{r} \gamma , the transformation \rho 2 is well defined and
we have \gamma = \rho 1\rho 2. Moreover, \rho 2 \in \langle \scrO \scrP (X,Y ), B\rangle by Case 1 (since \mathrm{k}\mathrm{e}\mathrm{r} \rho 2 \in \scrR k ) and thus
\gamma = \rho 1\rho 2 \in \langle \scrO \scrP (X,Y ), B\rangle .
Lemma 3 is proved.
Lemma 4. \langle \eta | Y \rangle =
\bigl\langle \bigl\{
\beta | Y : \beta \in \scrO \scrP (X,Y )
\bigr\} \bigr\rangle
\cap \scrS (Y ).
Proof. The inclusion \langle \eta | Y \rangle \subseteq
\bigl\langle \bigl\{
\beta | Y : \beta \in \scrO \scrP (X,Y )
\bigr\} \bigr\rangle
\cap \scrS (Y ) is obviously. Let now \beta \in
\in \scrO \scrP (X,Y ) with \beta | Y \in \scrS (Y ). Then there is k \in \{ 1, . . . ,m\} such that
ISSN 1027-3190. Укр. мат. журн., 2021, т. 73, № 5
624 I. DIMITROVA, J. KOPPITZ
\beta =
\Biggl(
A1 . . . Am - k+1 Am - k . . . Am
ak . . . am a1 . . . ak - 1
\Biggr)
with \{ A1, A2 < . . . < Am\} \in \scrP m \cup \scrQ m and ai \in Ai for i \in \{ 1, . . . ,m\} since Y is a transversal of
\mathrm{k}\mathrm{e}\mathrm{r}\beta . Thus,
\beta | Y =
\Biggl(
a1 . . . am - k+1 am - k . . . am
ak . . . am a1 . . . ak - 1
\Biggr)
= (\eta | Y )m - k+1 \in \langle \eta | Y \rangle .
This shows that
\bigl\langle \bigl\{
\beta | Y : \beta \in \scrO \scrP (X,Y )
\bigr\} \bigr\rangle
\cap \scrS (Y ) \subseteq
\bigl\{
(\eta | Y )p : p \in \BbbN
\bigr\}
= \langle \eta | Y \rangle .
Lemma 4 is proved.
The following lemmas give us necessary conditions for a set B \subseteq \scrT (X,Y ) to be a relative
generating set of \scrT (X,Y ) modulo \scrO \scrP (X,Y ).
Lemma 5. Let B \subseteq \scrT (X,Y ) \setminus \scrO \scrP (X,Y ) with \langle \scrO \scrP (X,Y ), B\rangle = \scrT (X,Y ). Then \scrS (Y ) \subseteq
\subseteq \langle \{ \beta | Y : \beta \in B\} , \eta | Y \rangle .
Proof. Let \sigma \in \scrS (Y ). We extend \sigma to a transformation \gamma : X \rightarrow Y, i.e., \gamma | Y = \sigma . Hence,
there are \gamma 1, . . . , \gamma k \in \scrO \scrP (X,Y ) \cup B (for a suitable natural number k) such that \gamma = \gamma 1 . . . \gamma k.
Since the image of any transformation in \scrT (X,Y ) belongs to Y, we have \sigma = \gamma | Y = \gamma 1| Y . . . \gamma k| Y .
Moreover, from \sigma \in \scrS (Y ), we conclude \gamma i| Y \in \scrS (Y ) for 1 \leq i \leq k. Let \gamma i \in \scrO \scrP (X,Y ) for some
i \in \{ 1, . . . , k\} . Then by Lemma 4
\gamma i| Y =
\Biggl(
a1 . . . at at+1 . . . am
am - t+1 . . . am a1 . . . am - t
\Biggr)
\in \langle \eta | Y \rangle
for a suitable natural number t. This shows \sigma \in
\bigl\langle
\{ \beta | Y : \beta \in B\} , \eta | Y
\bigr\rangle
.
Lemma 5 is proved.
Lemma 6. Let B \subseteq \scrT (X,Y ) \setminus \scrO \scrP (X,Y ) with \langle \scrO \scrP (X,Y ), B\rangle = \scrT (X,Y ). Then \scrR m \subseteq
\subseteq \{ \mathrm{k}\mathrm{e}\mathrm{r}\beta : \beta \in B\} .
Proof. Assume that there is P \in \scrR m with P \not \in \{ \mathrm{k}\mathrm{e}\mathrm{r}\beta : \beta \in B\} . Let \gamma \in \scrT (X,Y ) with
\mathrm{k}\mathrm{e}\mathrm{r} \gamma = P. Then there are \theta 1 \in \scrO \scrP (X,Y ) \cup B and \theta 2 \in \scrT (X,Y ) such that \gamma = \theta 1\theta 2. Since
\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k} \gamma = m, we obtain \mathrm{k}\mathrm{e}\mathrm{r} \gamma = \mathrm{k}\mathrm{e}\mathrm{r} \theta 1 = P. Thus, \theta 1 \not \in B, i.e., \theta 1 \in \scrO \scrP (X,Y ) and \mathrm{k}\mathrm{e}\mathrm{r} \theta 1 \in
\in \scrQ m \cup \scrP m, contradicts \mathrm{k}\mathrm{e}\mathrm{r} \theta 1 = P \in \scrR m.
Lemma 6 is proved.
Lemma 6 shows that \mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}(\scrT (X,Y ) : \scrO \scrP (X,Y )) \geq | \scrR m| . We will verify the equality.
Lemma 7. | \scrR m| = S(m,n) -
\biggl(
n
m
\biggr)
.
Proof. The cardinality of the set \scrD m := \scrR m \cup \scrP m was determined in [16]. The authors show
that | \scrD m| = S(m,n) -
\biggl(
n - 1
m - 1
\biggr)
. Because of \scrR m \cap \scrP m = \varnothing , we obtain \scrR m = \scrD m \setminus \scrP m. Since
| \scrP m| =
\biggl(
n - 1
m
\biggr)
(see Remark 1) it follows
| \scrR m| = | \scrD m| - | \scrP m| = S(m,n) -
\Biggl(
n - 1
m - 1
\Biggr)
-
\Biggl(
n - 1
m
\Biggr)
= S(m,n) -
\Biggl(
n
m
\Biggr)
.
Lemma 7 is proved.
Finally, we can state the relative rank of \scrT (X,Y ) modulo \scrO \scrP (X,Y ).
ISSN 1027-3190. Укр. мат. журн., 2021, т. 73, № 5
ON RELATIVE RANKS OF FINITE TRANSFORMATION SEMIGROUPS WITH RESTRICTED RANGE 625
Theorem 3. \mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}(\scrT (X,Y ) : \scrO \scrP (X,Y )) = S(m,n) -
\biggl(
n
m
\biggr)
.
Proof. If m = 1 then \scrT (X,Y ) = \scrO \scrP (X,Y ), i.e., \mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}(\scrT (X,Y ) : \scrO \scrP (X,Y )) = 0. On the
other hand, we have S(1, n) = n =
\biggl(
n
1
\biggr)
. Suppose now that n \geq 2. By Lemmas 6 and 7, we obtain
\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}(\scrT (X,Y ) : \scrO \scrP (X,Y )) \geq | \scrR m| = S(m,n) -
\biggl(
n
m
\biggr)
. In order to prove the equality, we have to
find a relative generating set B of \scrT (X,Y ) modulo \scrO \scrP (X,Y ) with | B| = | \scrR m| . We observe that
for each P \in \scrR m, there is \beta P \in \scrT (X,Y ) with \mathrm{k}\mathrm{e}\mathrm{r}\beta P = P, which will be fixed. Let \scrB := \{ \beta P :
P \in \scrR m\} . If m = 2 then \scrR m = \varnothing and \scrS (Y ) = \{ \eta | Y , (\eta | Y )2\} = \langle \eta | Y \rangle , obviously. If m \geq 3
then without loss of generality, we can assume that there is P \prime \in \scrR m such that Y is a transversal of
\mathrm{k}\mathrm{e}\mathrm{r}\beta P \prime and \beta P \prime | Y =
\biggl(
a1 a2 a3 . . . am
a2 a1 a3 . . . am
\biggr)
. It is known that \scrS (Y ) = \langle \beta P \prime | Y , \eta | Y \rangle . Hence,
\scrB is a relative generating set of \scrT (X,Y ) modulo \scrO \scrP (X,Y ) by Lemma 3. Since | \scrB | = | \scrR m| , we
obtain the required result.
Theorem 3 is proved.
Now we will characterize the minimal relative generating sets of \scrT (X,Y ) modulo \scrO \scrP (X,Y ).
The minimal relative generating sets do not coincide with the relative generating sets of size
\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}(\scrT (X,Y ) : \scrO \scrP (X,Y )).
Theorem 4. Let B \subseteq \scrT (X,Y ). Then B is a minimal relative generating set of \scrT (X,Y ) modulo
\scrO \scrP (X,Y ) if and only if there is a set \widetilde B \subseteq B such that the following three statements are satisfied:
(i) \scrR m \subseteq
\bigl\{
\mathrm{k}\mathrm{e}\mathrm{r}\beta : \beta \in B \setminus \widetilde B\bigr\} ,
(ii)
\bigm| \bigm| B \setminus \widetilde B\bigm| \bigm| = | \scrR m| ,
(iii) \scrS (Y ) \subseteq
\bigl\langle
\{ \beta | Y : \beta \in B\} , \eta | Y
\bigr\rangle
but \scrS (Y ) \nsubseteq
\bigl\langle
\{ \beta | Y : \beta \in B \setminus \{ \gamma \} \} , \eta | Y
\bigr\rangle
for any \gamma \in B
with \mathrm{k}\mathrm{e}\mathrm{r} \gamma \in \{ \mathrm{k}\mathrm{e}\mathrm{r}\beta : \beta \in \widetilde B\} .
Proof. Suppose that the conditions (i) – (iii) are satisfied. Then by Lemma 3 we have
\langle \scrO \scrP (X,Y ), B\rangle = \scrT (X,Y ). It remains to show that B is minimal. Assume that there is \gamma \in B
such that \langle \scrO \scrP (X,Y ), B \setminus \{ \gamma \} \rangle = \scrT (X,Y ). Note that \alpha \beta | Y = \alpha | Y \beta | Y for all \alpha , \beta \in \scrT (X,Y ).
Hence, we can conclude that
\scrS (Y ) \subseteq
\bigl\langle \bigl\{
\beta | Y : \beta \in \scrT (X,Y )
\bigr\} \bigr\rangle
\subseteq
\subseteq
\bigl\langle \bigl\{
\beta | Y : \beta \in \scrO \scrP (X,Y ) \cup (B \setminus \{ \gamma \} )
\bigr\} \bigr\rangle
=
\bigl\langle \bigl\{
\beta | Y : \beta \in B \setminus \{ \gamma \}
\bigr\}
, \eta | Y
\bigr\rangle
by Lemma 4. Hence, \mathrm{k}\mathrm{e}\mathrm{r} \gamma /\in \{ \mathrm{k}\mathrm{e}\mathrm{r}\beta : \beta \in \widetilde B\} by (iii). This implies that \gamma \in B \setminus \widetilde B and | (B \setminus \widetilde B) \setminus
\{ \gamma \} | < | \scrR m| by (ii), i.e., \scrR m \nsubseteqq \{ \mathrm{k}\mathrm{e}\mathrm{r}\beta : \beta \in (B \setminus \widetilde B) \setminus \{ \gamma \} \} . Since \mathrm{k}\mathrm{e}\mathrm{r} \gamma /\in \{ \mathrm{k}\mathrm{e}\mathrm{r}\beta : \beta \in \widetilde B\} , we
have \scrR m \nsubseteqq \{ \mathrm{k}\mathrm{e}\mathrm{r}\beta : \beta \in (B \setminus \{ \gamma \} )\} and, by Lemma 6, we obtain that \langle \scrO \scrP (X,Y ), B \setminus \{ \gamma \} \rangle \not =
\not = \scrT (X,Y ), a contradiction. This shows that B is a minimal relative generating set of \scrT (X,Y )
modulo \scrO \scrP (X,Y ).
Conversely, let B be a minimal relative generating set of \scrT (X,Y ) modulo \scrO \scrP (X,Y ). We have
\scrR m \subseteq \{ \mathrm{k}\mathrm{e}\mathrm{r}\beta : \beta \in B\} and \scrS (Y ) \subseteq \langle \{ \beta | Y : \beta \in B\} , \eta | Y \rangle by Lemmas 5 and 6, respectively. Then
there exists a set \widetilde B \subseteq B with | B \setminus \widetilde B| = | \scrR m| and \scrR m \subseteq \{ \mathrm{k}\mathrm{e}\mathrm{r}\beta : \beta \in (B \setminus \widetilde B)\} . For the set \widetilde B, the
conditions (i) and (ii) are satisfied. Assume now that there is \gamma \in B with \mathrm{k}\mathrm{e}\mathrm{r} \gamma \in \{ \mathrm{k}\mathrm{e}\mathrm{r}\beta : \beta \in \widetilde B\}
such that \scrS (Y ) \subseteq \langle \{ \beta | Y : \beta \in B \setminus \{ \gamma \} \} , \eta | Y \rangle . Then because of \scrR m \subseteq \{ \mathrm{k}\mathrm{e}\mathrm{r}\beta : \beta \in (B \setminus \{ \gamma \} )\} , the
set B\setminus \{ \gamma ) is a relative generating set of \scrT (X,Y ) modulo \scrO \scrP (X,Y ) by Lemma 3. This contradicts
the minimality of B. Consequently, (iii) is satisfied.
Theorem 4 is proved.
ISSN 1027-3190. Укр. мат. журн., 2021, т. 73, № 5
626 I. DIMITROVA, J. KOPPITZ
In particular, for the relative generating sets of minimal size we have the following remark.
Remark 3. B \subseteq \scrT (X,Y ) is a relative generating set of \scrT (X,Y ) modulo \scrO \scrP (X,Y ) of minimal
size if and only if \widetilde B = \varnothing .
References
1. P. M. Catarino, P. M. Higgins, The monoid of orientation-preserving mappings on a chain, Semigroup Forum, 58,
190 – 206 (1999).
2. I. Dimitrova, V. H. Fernandes, J. Koppitz, A note on generators of the endomorphism semigroup of an infinite
countable chain, J. Algebra and Appl., 16, № 2, Article 1750031 (2017).
3. I. Dimitrova, J. Koppitz, K. Tinpun, On the relative rank of the semigroup of orientation-preserving transformations
with restricted range, Proc. 47th Spring Conf. Union Bulg. Math., 109 – 114 (2018).
4. V. H. Fernandes, P. Honyam, T. M. Quinteiro, B. Singha, On semigroups of endomorphisms of a chain with restricted
range, Semigroup Forum, 89, 77 – 104 (2014).
5. V. H. Fernandes, P. Honyam, T. M. Quinteiro, B. Singha, On semigroups of orientation-preserving transformations
with restricted range, Commun. Algebra, 44, 253 – 264 (2016).
6. V. H. Fernandes, J. Sanwong, On the rank of semigroups of transformations on a finite set with restricted range,
Algebra Colloq., 21, 497 – 510 (2014).
7. G. M. S. Gomes, J. M. Howie, On the rank of certain semigroups of order-preserving transformations, Semigroup
Forum, 51, 275 – 282 (1992).
8. G. M. S. Gomes, J. M. Howie, On the ranks of certain finite semigroups of transformations, Math. Proc. Cambridge
Phil. Soc., 101, 395 – 403 (1987).
9. P. M. Higgins, J. D. Mitchell, N. Ruškuc, Generating the full transformation semigroup using order preserving
mappings, Glasgow Math. J., 45, 557 – 566 (2003).
10. J. M. Howie, Fundamentals of semigroup theory, Oxford Univ. Press, Oxford (1995).
11. J. M. Howie, R. B. McFadden, Idempotent rank in finite full transformation semigroups, Proc. Roy. Soc. Edinburgh A,
114, 161 – 167 (1990).
12. J. M. Howie, N. Ruškuc, P. M. Higgins, On relative ranks of full transformation semigroups, Commun. Algebra, 26,
733 – 748 (1998).
13. D. McAlister, Semigroups generated by a group and an idempotent, Commun. Algebra, 26, 515 – 547 (1998).
14. N. Ruškuc, On the rank of completely 0-simple semigroups, Math. Proc. Cambridge Phil. Soc., 116, 325 – 338 (1994).
15. J. S. V. Symons, Some results concerning a transformation semigroup, J. Austr. Math. Soc., 19, 413 – 425 (1975).
16. K. Tinpun, J. Koppitz, Relative rank of the finite full transformation semigroup with restricted range, Acta Math.
Univ. Comenian., 85, № 2, 347 – 356 (2016).
Received 04.09.18
ISSN 1027-3190. Укр. мат. журн., 2021, т. 73, № 5
|
| id | umjimathkievua-article-288 |
| institution | Ukrains’kyi Matematychnyi Zhurnal |
| keywords_txt_mv | keywords |
| language | English |
| last_indexed | 2026-03-24T02:02:19Z |
| publishDate | 2021 |
| publisher | Institute of Mathematics, NAS of Ukraine |
| record_format | ojs |
| resource_txt_mv | umjimathkievua/72/3e44aa291fd6cc3dc5d73d3ecec52472.pdf |
| spelling | umjimathkievua-article-2882025-03-31T08:48:07Z On relative ranks of finite transformation semigroups with restricted range Dimitrova, I. Koppitz, J. I. Dimitrova, I. Koppitz, J. transformation semigroups with restricted range, orderpreserving transformations, orientation-preserving transformations, relative rank, relative generating sets transformation semigroups with restricted range, orderpreserving transformations, orientation-preserving transformations, relative rank, relative generating sets UDC 512.5 We determine the relative rank of the semigroup ${\scr T }(X,Y)$ of all transformations on a finite chain $X$ with restricted range $Y\subseteq X$ modulo the set ${\scr OP }(X,Y)$ of all orientation-preserving transformations in ${\scr T }(X,Y).$ Moreover, we state the relative rank of the semigroup ${\scr OP }(X,Y)$ modulo the set ${\scr O}(X,Y)$ of all order-preserving transformations in ${\scr OP}(X,Y).$ In both cases we characterize the minimal relative generating sets. &nbsp; UDC 512.5 Про вiдноснi ранги напiвгруп фiнiтних перетворень з обмеженою областю значень Визначено відносний ранг напівгрупи ${\scr T }(X, Y)$ усіх перетворень на скінченному ланцюгу $X$ з обмеженою областю значень $Y \subseteq X$ за модулем множини ${\scr OP }(X, Y )$ усіх перетворень у ${\scr T } (X, Y),$ що зберігають орієнтацію. Крім того, встановлено відносний ранг напівгрупи ${\scr OP }(X, Y) $ за модулем множини ${\scr O}(X, Y)$ усіх перетворень в ${\scr OP }(X, Y),$ що зберігають порядок. В обох випадках охарактеризовано відповідні мінімальні породжуючі множини. Institute of Mathematics, NAS of Ukraine 2021-05-24 Article Article application/pdf https://umj.imath.kiev.ua/index.php/umj/article/view/288 10.37863/umzh.v73i5.288 Ukrains’kyi Matematychnyi Zhurnal; Vol. 73 No. 5 (2021); 617 - 626 Український математичний журнал; Том 73 № 5 (2021); 617 - 626 1027-3190 en https://umj.imath.kiev.ua/index.php/umj/article/view/288/9014 Copyright (c) 2021 Ilinka Dimitrova, Joerg Koppitz |
| spellingShingle | Dimitrova, I. Koppitz, J. I. Dimitrova, I. Koppitz, J. On relative ranks of finite transformation semigroups with restricted range |
| title | On relative ranks of finite transformation semigroups with restricted range |
| title_full | On relative ranks of finite transformation semigroups with restricted range |
| title_fullStr | On relative ranks of finite transformation semigroups with restricted range |
| title_full_unstemmed | On relative ranks of finite transformation semigroups with restricted range |
| title_short | On relative ranks of finite transformation semigroups with restricted range |
| title_sort | on relative ranks of finite transformation semigroups with restricted range |
| topic_facet | transformation semigroups with restricted range orderpreserving transformations orientation-preserving transformations relative rank relative generating sets transformation semigroups with restricted range orderpreserving transformations orientation-preserving transformations relative rank relative generating sets |
| url | https://umj.imath.kiev.ua/index.php/umj/article/view/288 |
| work_keys_str_mv | AT dimitrovai onrelativeranksoffinitetransformationsemigroupswithrestrictedrange AT koppitzj onrelativeranksoffinitetransformationsemigroupswithrestrictedrange AT i onrelativeranksoffinitetransformationsemigroupswithrestrictedrange AT dimitrovai onrelativeranksoffinitetransformationsemigroupswithrestrictedrange AT koppitzj onrelativeranksoffinitetransformationsemigroupswithrestrictedrange |