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 $\varphi :A^{\ast }\to M$such that $\varphi (a)=f(a)$ for every $a\in A$.

Theorem 1

The following are equivalent.

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

2. Any equation

   $$x_1\mathrm{\cdots }{x}_n=y_1\mathrm{\cdots }{y}_m,x_1,\mathrm{\dots },x_n,y_1,\mathrm{\dots },y_m\in \mathrm{mgs}(M)$$(1)

   has only the trivial solutions $n=m,x_1=y_1,\mathrm{\dots },x_n=y_n$.

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^{\mathrm{\ast }}$is a free submonoid of $A^{\mathrm{\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 $\varphi :B^{\ast }\to M$ that extends $f^{-1}$;such a morphism is clearly surjective.Moreover, any equation $\varphi (b_1\mathrm{\cdots }{b}_n)=\varphi (b_1^{\prime }\mathrm{\cdots }{b}_m^{\prime })$translates into an equation of the form (1),which by hypothesis has only trivial solutions:therefore $n=m$, $b_i=b_i^{\prime }$ for all $i$, and $\varphi$ 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\mathrm{\cdots }{y}_m$:then $pw=y_1$ and $wq=x_2\mathrm{\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\mathrm{\cdots }{x}_n=y_2\mathrm{\cdots }{y}_m$:since we had chosen a counterexample of minimal length,$n=m,x_2=y_2,\mathrm{\dots },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 $\varphi :B^{\ast }\to M$ be an isomorphism of monoids.Then clearly $\mathrm{mgs}(M)\subseteq \varphi (B)$;since removing $m=\varphi (b)$ from $\mathrm{mgs}(M)$ removes $\varphi (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={\varphi }^{-1}(p)$, $y={\varphi }^{-1}(q)$,$r={\varphi }^{-1}(pw)$, $s={\varphi }^{-1}(wq)$.Then $\varphi (xs)=\varphi (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=\varphi (u)\in M$.