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$.

Title	characterization of free submonoids
Canonical name	CharacterizationOfFreeSubmonoids
Date of creation	2013-03-22 18:21:32
Last modified on	2013-03-22 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