# characterization of free submonoids

Let $A$ be an arbitrary set, let $A^{\ast}$ be the free monoid on $A$, and let $e$ be the identity element (empty word) of $A^{\ast}$. Let $M$ be a submonoid of $A^{\ast}$ and let $\mathrm{mgs}(M)$ be its minimal generating set.

We recall the universal property of free monoids: for every mapping $f:A\to M$ with $M$ a monoid, there exists a unique morphism $\phi:A^{\ast}\to M$ such that $\phi(a)=f(a)$ for every $a\in A$.

###### Theorem 1

The following are equivalent.

1. 1.

$M$ is a free submonoid of $A^{\ast}$.

2. 2.

Any equation

 $x_{1}\cdots x_{n}=y_{1}\cdots y_{m}\;,\;x_{1},\ldots,x_{n},y_{1},\ldots,y_{m}% \in\mathrm{mgs}(M)$ (1)

has only the trivial solutions $n=m,x_{1}=y_{1},\ldots,x_{n}=y_{n}$.

3. 3.

For every $w\in A^{\ast}$, if $p,q\in M$ exist such that $pw,wq\in M$, then $w\in M$.

From point 3 of Theorem 1 follows

###### Corollary 1

An intersection of free submonoids of $A^{\ast}$ is a free submonoid of $A^{\ast}$.

As a consequence of Theorem 1, there is no Nielsen-Schreier theorem for monoids. In fact, consider $A=\{a,b\}$ and $Y=\{a,ab,ba\}\subseteq A^{\ast}$: then $\mathrm{mgs}(Y^{\ast})=Y$, but $x_{1}x_{2}=y_{1}y_{2}$ has a nontrivial solution over $Y$, namely, $(ab)a=a(ba)$.

We now prove Theorem 1.

Point 2 implies point 1. Let $f:\mathrm{mgs}(M)\to B$ be a bijection. By the universal property of free monoids, there exists a unique morphism $\phi:B^{\ast}\to M$ that extends $f^{-1}$; such a morphism is clearly surjective. Moreover, any equation $\phi(b_{1}\cdots b_{n})=\phi(b^{\prime}_{1}\cdots b^{\prime}_{m})$ translates into an equation of the form (1), which by hypothesis has only trivial solutions: therefore $n=m$, $b_{i}=b^{\prime}_{i}$ for all $i$, and $\phi$ is injective.

Point 3 implies point 2. Suppose the existence of $p,q\in M$ such that $pw,wq\in M$ implies $w\in A^{\ast}$ is actually in $M$. Consider an equation of the form (1) which is a counterexample to the thesis, and such that the length of the compared words is minimal: we may suppose $x_{1}$ is a prefix of $y_{1}$, so that $y_{1}=x_{1}w$ for some $w\in A^{\ast}$. Put $p=x_{1},q=y_{2}\cdots y_{m}$: then $pw=y_{1}$ and $wq=x_{2}\cdots x_{n}$ belong to $M$ by construction. By hypothesis, this implies $w\in M$: then $y_{1}\in\mathrm{mgs}(M)$ equals a product $x_{1}w$ with $x_{1},w\in M$—which, by definition of $\mathrm{mgs}(M)$, is only possible if $w=e$. Then $x_{1}=y_{1}$ and $x_{2}\cdots x_{n}=y_{2}\cdots y_{m}$: since we had chosen a counterexample of minimal length, $n=m,x_{2}=y_{2},\ldots,x_{n}=y_{n}$. Then the original equation has only trivial solutions, and is not a counterexample after all.

Point 1 implies point 3. Let $\phi:B^{\ast}\to M$ be an isomorphism of monoids. Then clearly $\mathrm{mgs}(M)\subseteq\phi(B)$; since removing $m=\phi(b)$ from $\mathrm{mgs}(M)$ removes $\phi(b^{\ast})$ from $M$, the equality holds. Let $w\in A^{\ast}$ and let $p,q\in M$ satisfy $pw,wq\in M$: put $x=\phi^{-1}(p)$, $y=\phi^{-1}(q)$, $r=\phi^{-1}(pw)$, $s=\phi^{-1}(wq)$. Then $\phi(xs)=\phi(ry)=pwq\in M$, so $xs=ry$: this is an equality over $B^{\ast}$, and is satisfied only by $r=xu$, $s=uy$ for some $u$. Then $w=\phi(u)\in M$.

## References

• 1 M. Lothaire. Combinatorics on words. Cambridge University Press 1997.
Title characterization of free submonoids CharacterizationOfFreeSubmonoids 2013-03-22 18:21:32 2013-03-22 18:21:32 Ziosilvio (18733) Ziosilvio (18733) 7 Ziosilvio (18733) Theorem msc 20M05 msc 20M10 intersection of free submonoids is free