1 Introduction
Ayyer et al. [Reference Ayyer, Schilling, Steinberg and Thiéry1] developed a general theory of Markov chains realisable as random walks on
$\mathscr {R}$
-trivial monoids, providing an elegant and uniform treatment of many classical examples and their generalisations. An essential role in [Reference Ayyer, Schilling, Steinberg and Thiéry1] is played by a novel series of finite
$\mathscr {R}$
-trivial monoids, so-called free tree monoids. For a positive integer n, the free tree monoid of rank n, denoted by
$FT_{n}$
, is generated by the identity
$\varepsilon $
and a totally ordered alphabet
$\mathcal {A}_{n} =\{1<2< \cdots < n\}$
with the relations
$$ \begin{align*} i^{2}=i & \quad \text{for each } i=1,2, \ldots, n, \\ kik= ki & \quad \text{if } 1\leq i <k\leq n. \end{align*} $$
The monoid
$FT_{n}$
is called the free tree monoid because there is a bijection between the elements of
$FT_{n}$
and certain trees. In fact, it follows from [Reference Ayyer, Schilling, Steinberg and Thiéry1, Proposition 5.1] that all rewriting rules
$$ \begin{align} \{i\mathbf{a} i\to i\mathbf{a} \mid i\in \mathcal{A}_{n}, \mathbf{a}\in \{1,2,\ldots, i-1\}^{*}\} \end{align} $$
constitute a complete rewriting system of
$FT_{n}$
. Consequently, we can identify the elements of
$FT_{n}$
with the reduced words in
$\mathcal {A}_{n}^{*}$
. For any
$\mathbf {a}\in \mathcal {A}_{n}^{*}$
, let
$\overline {\mathbf {a}}$
be the unique reduced word corresponding to
$\mathbf {a}$
. Now, take a reduced word
$\overline {\mathbf {a}}$
. If
$\mathcal {A}_{n}$
(and therefore
$\overline {\mathbf {a}}$
) is empty, let
$\mathcal {T}_{\mathcal {A}_{n}}(\overline {\mathbf {a}})$
be the tree consisting of a single leaf. Otherwise, note that n is the largest letter of
$\mathcal {A}_{n}$
. If n appears in
$\overline {\mathbf {a}}$
, write
$\overline {\mathbf {a}}=\mathbf {a}_{1}n\mathbf {a}_{2}$
, where
$\mathbf {a}_{1}, \mathbf {a}_{2}\in \mathcal {A}_{n-1}^{*}$
and define
$\mathcal {T}_{\mathcal {A}_{n}}(\overline {\mathbf {a}})$
as the tree whose root has subtrees
$\mathcal {T}_{\mathcal {A}_{n-1}}(\mathbf {a}_{1})$
and
$\mathcal {T}_{\mathcal {A}_{n-1}}(\mathbf {a}_{2})$
. If n does not appear in
$\overline {\mathbf {a}}$
, then define
$\mathcal {T}_{\mathcal {A}_{n}}(\overline {\mathbf {a}})$
as the tree whose root has
$\mathcal {T}_{\mathcal {A}_{n-1}}(\overline {\mathbf {a}})$
as the single subtree. For example,
$\mathcal {T}_{\mathcal {A}_{4}}(132412)$
is given in Figure 1.
The tree
${\mathcal {T}}_{{\mathcal{A}}_{4}}(132412)$
.
Clearly, the number of leaves of the tree is the length of the word plus one. It follows from [Reference Ayyer, Schilling, Steinberg and Thiéry1, Proposition 5.5] that the map
$\mathcal {T}_{\mathcal {A}_{n}}$
is a bijection between the elements of the free tree monoid
$FT_{n}$
and certain trees. By the definition of free tree monoids,
$FT_{n}$
is a finite monoid,
$|FT_{1}|=2$
and
$|FT_{n+1}|=|FT_{n}|^{2}+|FT_{n}|$
.
Let
$\mathcal {X}$
be any countably infinite alphabet and
$\mathcal {X}^{*}$
the free monoid over
$\mathcal {X}$
. Elements of
$\mathcal {X}$
are referred to as variables and elements of
$\mathcal {X}^{*}$
are referred to as words. Let
$\mathbf {u}\in \mathcal {X}^{*}$
. The content of
$\mathbf {u}$
, denoted by
$ {\mathsf {con}}(\mathbf {u})$
, is the set of all variables occurring in
$\mathbf {u}$
. A semigroup identity is usually written as
$\mathbf {u}\approx \mathbf {v}$
, where
$\mathbf {u},\mathbf {v}\in \mathcal {X}^{*}$
. A semigroup S satisfies
$\mathbf {u}\approx \mathbf {v}$
if
$\alpha (\mathbf {u}) =\alpha (\mathbf {v})$
in S under all possible substitutions
$\alpha : \mathcal {X}^{*}\to S$
. A semigroup is finitely based if there is a finite subset of its identities from which all of its identities may be deduced. Otherwise, it is nonfinitely based. The variety defined by a given set
$\Sigma $
of identities is the class of all semigroups that satisfy all identities in
$\Sigma $
. The variety generated by S, denoted by
$\text {var}(S)$
, is the variety defined by the set of all identities that S satisfies.
Recently, Sapir and Volkov [Reference Sapir and Volkov7, Proposition 4.5] proved that the free tree monoid
$FT_{n}$
is nonfinitely based for any
$n\geq 4$
. It follows from [Reference Lee and Li5] that both
$FT_{1}$
of order
$2$
and
$FT_{2}$
of order
$6$
are finitely based. However, the finite basis property of the monoid
$FT_{3}$
of order
$42$
remains unknown.
Let
$\tau $
be any total transformation on
$\{1,2,\ldots ,n\}$
. If
$\tau (i)\geq i$
for all i, then
$\tau $
is extensive; if
$\tau (i)\leq \tau (j)$
whenever
$i<j$
, then
$\tau $
is order-preserving. The set of all total extensive transformations of the finite chain
$\{1,2,\ldots ,n\}$
forms a monoid denoted by
$E_{n}$
. The set of all order-preserving transformations in
$E_{n}$
forms a submonoid, called the Catalan monoid
$C_{n}$
, because the cardinality of
$C_{n}$
coincides with the nth Catalan number
${1}/({n+1})(^{2n}_{\: n} )$
(see [Reference Higgins3, Theorem 3.1]). The equational properties of
$E_{n}$
and
$C_{n}$
have been widely studied. The finite basis problem for Catalan monoids was completely solved and a description of identities holding in Catalan monoids was given in [Reference Volkov8].
Proposition 1.1 [Reference Volkov8, Theorem 2].
For every
$n\geq 1$
, the identity
$\mathbf {u}\approx \mathbf {v}$
holds in
$C_{n+1}$
if and only if the words
$\mathbf {u}$
and
$\mathbf {v}$
have the same set of scattered subwords of length less than or equal to n.
Recall that the word
$\mathbf {w}=x_{1}x_{2}\cdots x_{r}\in \mathcal {X}^{*}$
is a scattered subword of
$\mathbf {u}$
if
$\mathbf {u}$
can be decomposed as
$$ \begin{align*} \mathbf{u}=\mathbf{u}_{1}x_{1}\mathbf{u}_{2}x_{2}\cdots \mathbf{u}_{r}x_{r}\mathbf{u}_{r+1} \end{align*} $$
for some
$\mathbf {u}_{1}, \mathbf {u}_{2}, \ldots , \mathbf {u}_{r+1}\in \mathcal {X}^{*}$
. Further, this decomposition is called the first occurrence of the scattered subword
$\mathbf {w}$
in the word
$\mathbf {u}$
if
$x_{i}\notin \operatorname {\mathsf {con}}(\mathbf {u}_{i})$
for all
$i=1, \ldots , r$
. Define the relation
$\sim _{n}$
on
$\mathcal {X}^{*}$
by letting
$\mathbf {u}\sim _{n}\mathbf {v}$
if and only if the following conditions hold:
-
(I) the words
$\mathbf {u}$
and
$\mathbf {v}$
have the same sets of scattered subwords of length less than or equal to n; -
(II) if
$\mathbf {w}=x_{1}x_{2}\cdots x_{r}$
(
$r\leq n$
) is an arbitrary common scattered subword of
$\mathbf {u}$
and
$\mathbf {v}$
, and are the first occurrences of the scattered subword
$$ \begin{align*} \mathbf{u}&=\mathbf{u}_{1}x_{1}\mathbf{u}_{2}x_{2}\cdots \mathbf{u}_{r}x_{r}\mathbf{u}_{r+1},\\ \mathbf{v}&=\mathbf{v}_{1}x_{1}\mathbf{v}_{2}x_{2}\cdots \mathbf{v}_{r}x_{r}\mathbf{v}_{r+1}, \end{align*} $$
$\mathbf {w}$
in
$\mathbf {u}$
and
$\mathbf {v}$
, then
${\mathsf {con}}(\mathbf {u}_{i})={\mathsf {con}}(\mathbf {v}_{i})$
for
$i=1,2,\ldots , r+1$
.
In [Reference Goldberg, André, Fernandes, Gomes, Branco, Fountain and Meakin2], Goldberg studied the equational property and the finite basis problem for
$E_{n+1}$
.
Proposition 1.2 [Reference Goldberg, André, Fernandes, Gomes, Branco, Fountain and Meakin2, Proposition 2.2].
The identity
$\mathbf {u}\approx \mathbf {v}$
holds in the monoid
$E_{n+1}$
if and only if
$\mathbf {u}\sim _{n-1}\mathbf {v}$
.
A combination of [Reference Goldberg, André, Fernandes, Gomes, Branco, Fountain and Meakin2, Theorem 1.1], [Reference Lee4, Theorem 1.2] and [Reference Li and Luo6, Theorem 1] completely solved the finite basis problem for
$E_{n+1}$
.
Proposition 1.3. The monoid
$E_{n+1}$
is finitely based if and only if
$n\leq 3$
.
In this paper, we show that the identity
$\mathbf {u}\approx \mathbf {v}$
holds in the free tree monoid
$FT_{n}$
if and only if
$\mathbf {u}\sim _{n-1}\mathbf {v}$
, and so by Proposition 1.2, the monoids
$FT_{n}$
and
$E_{n+1}$
satisfy the same identities. Consequently, the finite basis problem for
$FT_{n}$
is completely solved.
Theorem 1.4. For each positive integer n, the monoids
$FT_{n}$
and
$E_{n+1}$
satisfy the same identities. Consequently,
$FT_{n}$
is finitely based if and only if
$n\leq 3$
.
2 Proof of Theorem 1.4
Given
$\mathbf {a}\in \mathcal {A}_{n}^{*}$
, the support of
$\mathbf {a}$
, denoted by
$\operatorname {\mathsf {supp}}(\mathbf {a})$
, is the set of all letters occurring in
$\mathbf {a}$
. The number of occurrences of
$i\in \mathcal {A}_{n}$
in
$\mathbf {a}$
is denoted by
$\operatorname {\mathsf {occ}}(i,\mathbf {a})$
. Let
$\mathbf {a}[1,2,\ldots , n-1]$
denote the word obtained from
$\mathbf {a}$
by retaining only the letters
$1,2,\ldots , n-1$
.
Lemma 2.1. Let
$n\geq 2$
and
$\mathbf {u},\mathbf {v}\in \mathcal {X}^{*}$
. If
$\mathbf {w}=x_{1}x_{2}\cdots x_{r}$
$(r\leq n-1)$
is an arbitrary common scattered subword of
$\mathbf {u}$
and
$\mathbf {v}$
, and
$$ \begin{align*} \mathbf{u}&=\mathbf{u}_{1}x_{1}\mathbf{u}_{2}x_{2}\cdots \mathbf{u}_{r}x_{r}\mathbf{u}_{r+1},\\ \mathbf{v}&=\mathbf{v}_{1}x_{1}\mathbf{v}_{2}x_{2}\cdots \mathbf{v}_{r}x_{r}\mathbf{v}_{r+1}, \end{align*} $$
are the first occurrences of
$\mathbf {w}$
in
$\mathbf {u}$
and
$\mathbf {v}$
, and
${\textsf{con}}(\mathbf {u}_{i})\neq {\textsf{con}}(\mathbf {v}_{i})$
for some
$i\in \{1, 2,\ldots , r+1\}$
, then
$FT_{n}$
does not satisfy the identity
$\mathbf {u}\approx \mathbf {v}$
.
Proof. Without loss of generality, assume that
$y\in \operatorname {\mathsf {con}}(\mathbf {u}_{i})\setminus \operatorname {\mathsf {con}}(\mathbf {v}_{i})$
for some
$i\in \{1,2,\ldots , r+1\}$
. Then,
$x_{1} x_{2}\cdots x_{i-1}y x_{i}\cdots x_{r}$
is a scattered subword of
$\mathbf {u}$
. Note that
$x_{j}$
may equal
$x_{k}$
for some distinct j and k, and y may equal
$x_{j}$
for some j. We partition the multiset
$\{x_{1}, x_{2}, \ldots , x_{r}, y\}$
, variables in it possibly equal, into the disjoint union of some multisets such that the same variables belong to the same multiset. Without loss of generality, assume that
$$ \begin{align*} \{x_{1}, \ldots, x_{r}, y\}=\{x_{j_{1}^{1}}= \cdots= x_{j_{1}^{k_{1}}}\} \sqcup \{x_{j_{2}^{1}}= \cdots= x_{j_{2}^{k_{2}}}\}\sqcup\cdots\sqcup \{x_{j_{\ell}^{1}}= \cdots= x_{j_{\ell}^{k_{\ell}}}= y\}, \end{align*} $$
where
$k_1, \ldots , k_{\ell -1}\geq 1$
,
$k_{\ell }\geq 0$
and
$x_{j_{1}^{1}}, x_{j_{2}^{1}}, \ldots , x_{j_{\ell -1}^{1}}, y$
are pairwise distinct and
$$ \begin{align*} j_{1}^{1}<\cdots<j_{1}^{k_{1}},\quad j_{2}^{1}<\cdots<j_{2}^{k_{2}},\quad \ldots, \quad j_{\ell}^{1}<\cdots<j_{\ell}^{k_{\ell}}. \end{align*} $$
Now, we define the substitution
$\beta : \mathcal {X}^{*} \to FT_{n}$
as follows:
$$ \begin{align*} \beta(x_{j_{1}^{1}}) & =\cdots=\beta(x_{j_{1}^{k_{1}}})= (n+1-j_{1}^{k_{1}})\cdots (n+1-j_{1}^{2})(n+1-j_{1}^{1}), \\ \beta(x_{j_{2}^{1}}) & =\cdots=\beta(x_{j_{2}^{k_{2}}})= (n+1-j_{2}^{k_{2}})\cdots (n+1-j_{2}^{2})(n+1-j_{2}^{1}), \\ &\ \vdots\\ \beta(x_{j_{\ell}^{1}}) & =\cdots=\beta(x_{j_{\ell}^{k_{\ell}}})=\beta(y)= 1(n+1-j_{\ell}^{k_{\ell}})\cdots (n+1-j_{\ell}^{2})(n+1-j_{\ell}^{1}),\\ \beta(z) & = \varepsilon \;\;\text{for any}\;\; z\in \mathcal{X}\setminus \{x_{1}, x_{2},\ldots, x_{r}, y\}. \end{align*} $$
By the definition of
$\beta $
,
$$ \begin{align*} \beta(\mathbf{u})&=\beta(\mathbf{u}_{1})\beta(x_{1})\beta(\mathbf{u}_{2})\beta(x_{2})\cdots \beta(\mathbf{u}_{r})\beta(x_{r})\beta(\mathbf{u}_{r+1}),\\ \beta(\mathbf{v})&=\beta(\mathbf{v}_{1})\beta(x_{1})\beta(\mathbf{v}_{2})\beta(x_{2})\cdots \beta(\mathbf{v}_{r})\beta(x_{r})\beta(\mathbf{v}_{r+1}), \end{align*} $$
where:
-
(a)
$\operatorname {\mathsf {occ}}(n, \beta (x_{1}))=\operatorname {\mathsf {occ}}(n-1, \beta (x_{2}))=\cdots =\operatorname {\mathsf {occ}}(n+1-r, \beta (x_{r}))=1$
; -
(b)
$n\hspace{-0.5pt}\notin\hspace{-0.5pt} \operatorname {\mathsf {supp}}(\beta (\mathbf {u}_{1})\beta (\mathbf {v}_{1})), n\hspace{-0.5pt}-\hspace{-0.5pt}1\hspace{-0.5pt}\notin\hspace{-0.5pt} \operatorname {\mathsf {supp}}(\beta (\mathbf {u}_{2})\beta (\mathbf {v}_{2})), \ldots , n\hspace{-0.5pt}+\hspace{-0.5pt}1\hspace{-0.5pt}-\hspace{-0.5pt}r\hspace{-0.5pt}\notin\hspace{-0.5pt} \operatorname {\mathsf {supp}}(\beta (\mathbf {u}_{r})\beta (\mathbf {v}_{r}))$
.
Since
$y\in \operatorname {\mathsf {con}}(\mathbf {u}_{i})\setminus \operatorname {\mathsf {con}}(\mathbf {v}_{i})$
, it follows that
$1\in \operatorname {\mathsf {supp}}(\beta (\mathbf {u}_{i}))\setminus \mathsf{supp}(\beta(\mathbf{v}_i))$
. By the definition of
$\beta $
, the reduced words
$\overline {\beta (\mathbf {u})}$
and
$\overline {\beta (\mathbf {v})}$
corresponding respectively to
$\beta (\mathbf {u})$
and
$\beta (\mathbf {v})$
can be written as
$$ \begin{align*} \overline{\beta(\mathbf{u})}&=\mathbf{a}_{1}n\mathbf{a}_{2}(n-1)\cdots \mathbf{a}_{i-1} (n-i+2) \mathbf{a}_{i} (n-i+1) \cdots \mathbf{a}_{r} (n-r+1) \mathbf{a}_{r+1},\\ \overline{\beta(\mathbf{v})}&=\mathbf{b}_{1}n\mathbf{b}_{2}(n-1)\cdots \mathbf{b}_{i-1}(n-i+2)\mathbf{b}_{i}(n-i+1)\cdots \mathbf{b}_{r}(n-r+1)\mathbf{b}_{r+1}, \end{align*} $$
where:
-
(c)
$\mathbf {a}_{1},\ldots ,\mathbf {a}_{r+1}, \mathbf {b}_{1},\ldots , \mathbf {b}_{r+1}\in \mathcal {A}_{n}^{*}$
and
$1\in \operatorname {\mathsf {supp}}(\mathbf {a}_{i})\setminus \operatorname {\mathsf {supp}}(\mathbf {b}_{i})$
; -
(d)
$n\notin \operatorname {\mathsf {supp}}(\mathbf {a}_{1}\mathbf {a}_{2}\cdots \mathbf {a}_{r+1}\mathbf {b}_{1}\mathbf {b}_{2}\cdots \mathbf {b}_{r+1}), (n-1)\notin \operatorname {\mathsf {supp}}(\mathbf {a}_{2}\cdots \mathbf {a}_{r+1}\mathbf {b}_{2}\cdots \mathbf {b}_{r+1}), \ldots , (n-r+1)\notin \operatorname {\mathsf {supp}}(\mathbf {a}_{r}\mathbf {a}_{r+1}\mathbf {b}_{r}\mathbf {b}_{r+1})$
.
Consequently,
$\overline {\beta (\mathbf {u})}\neq \overline {\beta (\mathbf {v})}$
, this implies that
$\beta (\mathbf {u})\neq \beta (\mathbf {v})$
in
$FT_{n}$
.
Lemma 2.2. Let
$\mathbf {u}, \mathbf {v}\in \mathcal {X}^{*}$
and
$\mathbf {u}\sim _{n}\mathbf {v}$
. If
$$ \begin{align} \mathbf{u}&=\mathbf{u}_{1}x\mathbf{u}_{2}, \end{align} $$
$$ \begin{align} \mathbf{v}&=\mathbf{v}_{1}x\mathbf{v}_{2} \end{align} $$
for some
$\mathbf {u}_{1}, \mathbf {u}_{2}, \mathbf {v}_{1}, \mathbf {v}_{2}\in \mathcal {X}^{*}$
such that
$x\notin {\mathsf{con}}(\mathbf {u}_{1}\mathbf {v}_{1})$
, then
$\mathbf {u}_{1}\sim _{n-1}\mathbf {v}_{1}$
and
$\mathbf {u}_{2}\sim _{n-1}\mathbf {v}_{2}$
.
Proof. We only need to prove
$\mathbf {u}_{1}\sim _{n-1}\mathbf {v}_{1}$
since the result
$\mathbf {u}_{2}\sim _{n-1}\mathbf {v}_{2}$
can be obtained similarly. Since
$\mathbf {u}\sim _{n}\mathbf {v}$
, the words
$\mathbf {u}$
and
$\mathbf {v}$
have the same sets of scattered subwords of length less than or equal to n. Assume that
$y_{1}y_{2}\cdots y_{r}$
(
$r\leq n-1$
) is any scattered subword of
$\mathbf {u}_{1}$
. Since (2.1), (2.2) are the first occurrences of the scattered subword x in
$\mathbf {u}$
and
$\mathbf {v}$
, it follows from
$y_{1}\in \operatorname {\mathsf {con}}(\mathbf {u}_{1})$
and condition (II) that
$y_{1}\in \operatorname {\mathsf {con}}(\mathbf {v}_{1})$
. Let
$$ \begin{align} \mathbf{u}&=\mathbf{u}_{3}y_{1}\mathbf{u}_{4}x\mathbf{u}_{2}, \end{align} $$
$$ \begin{align} \mathbf{v}&=\mathbf{v}_{3}y_{1}\mathbf{v}_{4}x\mathbf{v}_{2} \end{align} $$
for some
$\mathbf {u}_{3}, \mathbf {u}_{4},\mathbf {v}_{3}, \mathbf {v}_{4}\in \mathcal {X}^{*}$
such that
$y_{1}\notin \operatorname {\mathsf {con}}(\mathbf {u}_{3}\mathbf {v}_{3})$
. Since
$y_{1}y_{2}\cdots y_{r}$
is a scattered subword of
$\mathbf {u}_{1}$
, it follows that
$y_{2}\in \operatorname {\mathsf {con}}(\mathbf {u}_{4})$
. Note that as (2.3), (2.4) are the first occurrences of the scattered subword
$y_{1}x$
in
$\mathbf {u}$
and
$\mathbf {v}$
, it follows from condition (II) that
$y_{2}\in \operatorname {\mathsf {con}}(\mathbf {v}_{4})$
. Repeating this process shows that
$y_{1}y_{2}\cdots y_{r}$
$(r\leq n-1)$
is a scattered subword of
$\mathbf {v}_{1}$
. By symmetry, if
$y_{1}y_{2}\cdots y_{r}$
$(r\leq n-1)$
is a scattered subword of
$\mathbf {v}_{1}$
, then it is also a scattered subword of
$\mathbf {u}_{1}$
. Hence, the words
$\mathbf {u}_{1}$
and
$\mathbf {v}_{1}$
have the same sets of scattered subwords of length less than or equal to
$n-1$
.
If
$y_{1}y_{2}\cdots y_{r}$
(
$r\leq n-1$
) is an arbitrary common scattered subword of
$\mathbf {u}_{1}$
and
$\mathbf {v}_{1}$
, and
$$ \begin{align*} \mathbf{u}_{1}&=\mathbf{u}_{1}^{\prime}y_{1}\mathbf{u}_{2}^{\prime}y_{2}\cdots \mathbf{u}_{r}^{\prime}y_{r}\mathbf{u}_{r+1}^{\prime},\\ \mathbf{v}_{1}&=\mathbf{v}_{1}^{\prime}y_{1}\mathbf{v}_{2}^{\prime}y_{2}\cdots \mathbf{v}_{r}^{\prime}y_{r}\mathbf{v}_{r+1}^{\prime}, \end{align*} $$
are the first occurrences of the scattered subword
$y_{1}y_{2}\cdots y_{r}$
in
$\mathbf {u}_{1}$
and
$\mathbf {v}_{1}$
, then
$$ \begin{align*} \mathbf{u}&=\mathbf{u}_{1}x\mathbf{u}_{2}=\mathbf{u}_{1}^{\prime}y_{1}\mathbf{u}_{2}^{\prime}y_{2}\cdots \mathbf{u}_{r}^{\prime}y_{r}\mathbf{u}_{r+1}^{\prime}x\mathbf{u}_{2},\\ \mathbf{v}&=\mathbf{v}_{1}x\mathbf{v}_{2}=\mathbf{v}_{1}^{\prime}y_{1}\mathbf{v}_{2}^{\prime}y_{2}\cdots \mathbf{v}_{r}^{\prime}y_{r}\mathbf{v}_{r+1}^{\prime}x\mathbf{v}_{2} \end{align*} $$
are the first occurrences of the scattered subword
$y_{1}\cdots y_{r} x$
in
$\mathbf {u}$
and
$\mathbf {v}$
. Since
$\mathbf {u}\sim _{n}\mathbf {v}$
, it follows from condition (II) that
$\operatorname {\mathsf {con}}(\mathbf {u}_{i}^{\prime })=\operatorname {\mathsf {con}}(\mathbf {v}_{i}^{\prime })$
for
$i=1,2,\ldots , r+1$
.
Proof of Theorem 1.4.
Clearly,
$FT_{1}$
is isomorphic to
$E_{2}$
. Therefore, we assume that
$n\geq 2$
. Let
$\mathbf {u}, \mathbf {v}\in \mathcal {X}^{*}$
. It suffices to show that the identity
$\mathbf {u}\approx \mathbf {v}$
holds in
$FT_{n}$
if and only if
$\mathbf {u}\sim _{n-1}\mathbf {v}$
. Then, by Proposition 1.2, the monoids
$FT_{n}$
and
$E_{n+1}$
satisfy the same identities.
Assume that
$\mathbf {u}\approx \mathbf {v}$
holds in
$FT_{n}$
. Then,
$\mathbf {u}\approx \mathbf {v}$
holds in the Catalan monoid
$C_{n+1}$
since
$C_{n+1}$
is a homomorphic image of
$FT_{n}$
[Reference Sapir and Volkov7, Lemma 4.3]. It follows from Proposition 1.1 that the words
$\mathbf {u}$
and
$\mathbf {v}$
have the same sets of scattered subwords of length less than or equal to n, and so condition (I) holds. Condition (II) holds by Lemma 2.1.
Conversely, assume that
$\mathbf {u}\sim _{n-1}\mathbf {v}$
. Now, we prove that
$\mathbf {u}\approx \mathbf {v}$
holds in
$FT_{n}$
. We proceed by induction on n. If
$n=2$
, then
$\mathbf {u}\sim _{1}\mathbf {v}$
. For any substitution
$\alpha : \mathcal {X}^{*}\to FT_{2}$
, we have
$\operatorname {\mathsf {supp}}(\alpha (\mathbf {u}))=\operatorname {\mathsf {supp}}(\alpha (\mathbf {v}))$
by condition (I). If
$2\notin \operatorname {\mathsf {supp}}(\alpha (\mathbf {u}))=\operatorname {\mathsf {supp}}(\alpha (\mathbf {v}))$
, then clearly
$\alpha (\mathbf {u})=\alpha (\mathbf {v})=1$
or
$\varepsilon $
. If
$2\in \operatorname {\mathsf {supp}}(\alpha (\mathbf {u}))=\operatorname {\mathsf {supp}}(\alpha (\mathbf {v}))$
, then let
$$ \begin{align} \mathbf{u}=\mathbf{u}_{1}x\mathbf{u}_{2} \end{align} $$
for some
$x\in \mathcal {X}, \mathbf {u}_{1},\mathbf {u}_{2}\in \mathcal {X}^{*}$
such that
$2\in \operatorname {\mathsf {supp}}(\alpha (x))$
and
$2\notin \operatorname {\mathsf {supp}}(\alpha (\mathbf {u}_{1}))$
. Then,
$x\in \operatorname {\mathsf {con}}(\mathbf {v})$
by condition (I). Denote
$$ \begin{align} \mathbf{v}=\mathbf{v}_{1}x\mathbf{v}_{2}, \end{align} $$
where
$\mathbf {v}_{1},\mathbf {v}_{2}\in \mathcal {X}^{*}$
and
$x\notin \operatorname {\mathsf {con}}(\mathbf {v}_{1})$
. Since (2.5), (2.6) are the first occurrences of the scattered subword x in
$\mathbf {u}$
and
$\mathbf {v}$
, it follows from
$\mathbf {u}\sim _{1}\mathbf {v}$
and condition (II) that
$\operatorname {\mathsf {con}}(\mathbf {u}_{1})=\operatorname {\mathsf {con}}(\mathbf {v}_{1})$
and
$\operatorname {\mathsf {con}}(\mathbf {u}_{2})=\operatorname {\mathsf {con}}(\mathbf {v}_{2})$
. Hence,
$2\notin \operatorname {\mathsf {supp}}(\alpha (\mathbf {u}_{1})) =\operatorname {\mathsf {supp}}(\alpha (\mathbf {v}_{1}))$
and
$\operatorname {\mathsf {supp}}(\alpha (\mathbf {u}_{2})) =\operatorname {\mathsf {supp}}(\alpha (\mathbf {v}_{2}))$
, and so
$\alpha (\mathbf {u})=\alpha (\mathbf {v})$
by (1.1). Thus,
$\mathbf {u}\approx \mathbf {v}$
holds in
$FT_{2}$
.
Suppose that
$\mathbf {u}\approx \mathbf {v}$
holds in
$FT_{k}$
if
$\mathbf {u}\sim _{k-1}\mathbf {v}$
for
$2\leq k\leq n-1$
. We need to show
$\mathbf {u}\sim _{n-1}\mathbf {v}$
implies that
$\mathbf {u}\approx \mathbf {v}$
holds in
$FT_{n}$
. Since
$\mathbf {u}\sim _{n-1}\mathbf {v}$
, it follows from condition (I) that
$\operatorname {\mathsf {supp}}(\alpha (\mathbf {u}))=\operatorname {\mathsf {supp}}(\alpha (\mathbf {v}))$
for any substitution
$\alpha : \mathcal {X}^{*}\to FT_{n}$
. If
$n\notin \operatorname {\mathsf {supp}}(\alpha (\mathbf {u}))=\operatorname {\mathsf {supp}}(\alpha (\mathbf {v}))$
, then
$\alpha $
can be seen as a substitution
$\alpha : \mathcal {X}^{*}\to FT_{n-1}$
. Since
$\mathbf {u}\sim _{n-1}\mathbf {v}$
, it follows that
$\mathbf {u}\sim _{n-2}\mathbf {v}$
. According to the inductive hypothesis, we have
$\alpha (\mathbf {u})=\alpha (\mathbf {v})$
. If
$n\in \operatorname {\mathsf {supp}}(\alpha (\mathbf {u}))=\operatorname {\mathsf {supp}}(\alpha (\mathbf {v}))$
, then let
$$ \begin{align} \mathbf{u}=\mathbf{u}_{1}x\mathbf{u}_{2} \end{align} $$
for some
$x\in \mathcal {X}, \mathbf {u}_{1},\mathbf {u}_{2}\in \mathcal {X}^{*}$
such that
$n\in \operatorname {\mathsf {supp}}(\alpha (x))$
and
$n\notin \operatorname {\mathsf {supp}}(\alpha (\mathbf {u}_{1}))$
. Hence,
$x\in \operatorname {\mathsf {con}}(\mathbf {v})$
by condition (I). Denote
$$ \begin{align} \mathbf{v}=\mathbf{v}_{1}x\mathbf{v}_{2}, \end{align} $$
where
$\mathbf {v}_{1},\mathbf {v}_{2}\in \mathcal {X}^{*}$
and
$x\notin \operatorname {\mathsf {con}}(\mathbf {v}_{1})$
. Since (2.7), (2.8) are the first occurrences of the scattered subword x in
$\mathbf {u}$
and
$\mathbf {v}$
, it follows from
$\mathbf {u}\sim _{n-1}\mathbf {v}$
and condition (II) that
$\operatorname {\mathsf {con}}(\mathbf {u}_{1})=\operatorname {\mathsf {con}}(\mathbf {v}_{1})$
and
$\operatorname {\mathsf {con}}(\mathbf {u}_{2})=\operatorname {\mathsf {con}}(\mathbf {v}_{2})$
. For
$$ \begin{align*} \alpha(\mathbf{u})&=\alpha(\mathbf{u}_{1})\alpha(x)\alpha(\mathbf{u}_{2}),\\ \alpha(\mathbf{v})&=\alpha(\mathbf{v}_{1})\alpha(x)\alpha(\mathbf{v}_{2}), \end{align*} $$
we have
$n\in \operatorname {\mathsf {supp}}(\alpha (x))$
,
$n\notin \operatorname {\mathsf {supp}}(\alpha (\mathbf {u}_{1})\alpha (\mathbf {v}_{1}))$
, and all n in
$\alpha (\mathbf {u}_{2}), \alpha (\mathbf {v}_{2})$
can be eliminated by the rewriting rules in (1.1). Hence, there is a substitution
$\beta : \mathcal {X}^{*}\to FT_{n-1}$
given by
$$ \begin{align*} \mathbf{a} &\mapsto \begin{cases} \alpha(\mathbf{a}) & \text{if}\ n\notin\operatorname{\mathsf{supp}}(\alpha(\mathbf{a})),\\ \alpha(\mathbf{a})[1,2,\ldots,n-1] & \text{if}\ n\in\operatorname{\mathsf{supp}}(\alpha(\mathbf{a})), \end{cases} \end{align*} $$
such that
$$ \begin{align*} \alpha(\mathbf{u})&=\alpha(\mathbf{u}_{1})\alpha(x)\alpha(\mathbf{u}_{2})=\beta(\mathbf{u}_{1})\alpha(x)\beta(\mathbf{u}_{2}),\\ \alpha(\mathbf{v})&=\alpha(\mathbf{v}_{1})\alpha(x)\alpha(\mathbf{v}_{2})=\beta(\mathbf{v}_{1})\alpha(x)\beta(\mathbf{v}_{2}). \end{align*} $$
By Lemma 2.2,
$\mathbf {u}_{1}\sim _{n-2}\mathbf {v}_{1}$
and
$\mathbf {u}_{2}\sim _{n-2}\mathbf {v}_{2}$
. According to the inductive hypothesis,
$\beta (\mathbf {u}_{1})=\beta (\mathbf {v}_{1})$
and
$\beta (\mathbf {u}_{2})=\beta (\mathbf {v}_{2})$
, and so
$\alpha (\mathbf {u})=\alpha (\mathbf {v})$
. That is,
$\mathbf {u}\approx \mathbf {v}$
holds in
$FT_{n}$
.
Corollary 2.3. We have
$\mathrm {var}(C_{2})=\mathrm {var}(FT_{1})=\mathrm {var}(E_{2})$
, and
$\mathrm {var}(C_{n+1})$
is a proper subvariety of
$\mathrm {var}(FT_{n})= \mathrm {var}(E_{n+1})$
for any
$n\geq 2$
.
Proof. Clearly,
$C_{2}, FT_{1}$
and
$E_{2}$
are isomorphic to each other. For
$n\geq 2$
, it follows from Theorem 1.4 and [Reference Sapir and Volkov7, Lemma 4.3] that
$\mathrm {var}(C_{n+1})\subseteq \mathrm {var}(FT_{n})=\mathrm {var}(E_{n+1})$
. Next, we prove that
$\mathrm {var}(C_{n+1})$
is a proper subvariety of
$\mathrm {var}(FT_{n})$
. Consider the identity
$(xy)^{n}\approx (yx)^{n}$
. It is routine to check that
$(xy)^{n}$
and
$(yx)^{n}$
have the same set of scattered subwords of length less than or equal to n, and it follows from Proposition 1.1 that
$C_{n+1}$
satisfies
$(xy)^{n}\approx (yx)^{n}$
. However,
$$ \begin{align*} (xy)^{n}=x\cdot y(xy)^{n-1} \quad \mbox{and} \quad (yx)^{n}=y\cdot x \cdot (yx)^{n-1} \end{align*} $$
are the first occurrences of the common scattered subword x in
$(xy)^{n}$
and
$(yx)^{n}$
. Clearly,
$(xy)^{n}\approx (yx)^{n}$
does not satisfy condition (II). Therefore,
$FT_{n}$
does not satisfy
$(xy)^{n}\approx (yx)^{n}$
.
