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.

3.
For every $w\in {A}^{\ast}$, if $p,q\in M$ exist such that $pw,wq\in M$, then $w\in M$.
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 NielsenSchreier 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$.
References
 1 M. Lothaire. Combinatorics on words. Cambridge University Press 1997.
Title  characterization of free submonoids 

Canonical name  CharacterizationOfFreeSubmonoids 
Date of creation  20130322 18:21:32 
Last modified on  20130322 18:21:32 
Owner  Ziosilvio (18733) 
Last modified by  Ziosilvio (18733) 
Numerical id  7 
Author  Ziosilvio (18733) 
Entry type  Theorem 
Classification  msc 20M05 
Classification  msc 20M10 
Defines  intersection of free submonoids is free 