characterization of free submonoids

Let A be an arbitrary set, let A be the free monoid on A, and let e be the identity elementMathworldPlanetmath (empty wordPlanetmathPlanetmath) of A. Let M be a submonoid of A and let mgs(M) be its minimalPlanetmathPlanetmath generating setPlanetmathPlanetmath.

We recall the universal propertyMathworldPlanetmath of free monoids: for every mapping f:AM with M a monoid, there exists a unique morphismMathworldPlanetmathPlanetmath ϕ:AM such that ϕ(a)=f(a) for every aA.

Theorem 1

The following are equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath.

  1. 1.

    M is a free submonoid of A.

  2. 2.

    Any equation

    x1xn=y1ym,x1,,xn,y1,,ymmgs(M) (1)

    has only the trivial solutions n=m,x1=y1,,xn=yn.

  3. 3.

    For every wA, if p,qM exist such that pw,wqM, then wM.

From point 3 of Theorem 1 follows

Corollary 1

An intersectionMathworldPlanetmathPlanetmath of free submonoids of A is a free submonoid of A.

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}A: then mgs(Y)=Y, but x1x2=y1y2 has a nontrivial solution over Y, namely, (ab)a=a(ba).

We now prove Theorem 1.

Point 2 implies point 1. Let f:mgs(M)B be a bijection. By the universal property of free monoids, there exists a unique morphism ϕ:BM that extends f-1; such a morphism is clearly surjectivePlanetmathPlanetmath. Moreover, any equation ϕ(b1bn)=ϕ(b1bm) translatesMathworldPlanetmath into an equation of the form (1), which by hypothesisMathworldPlanetmath has only trivial solutions: therefore n=m, bi=bi for all i, and ϕ is injectivePlanetmathPlanetmath.

Point 3 implies point 2. Suppose the existence of p,qM such that pw,wqM implies wA 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 x1 is a prefix of y1, so that y1=x1w for some wA. Put p=x1,q=y2ym: then pw=y1 and wq=x2xn belong to M by construction. By hypothesis, this implies wM: then y1mgs(M) equals a productMathworldPlanetmathPlanetmathPlanetmath x1w with x1,wM—which, by definition of mgs(M), is only possible if w=e. Then x1=y1 and x2xn=y2ym: since we had chosen a counterexample of minimal length, n=m,x2=y2,,xn=yn. Then the original equation has only trivial solutions, and is not a counterexample after all.

Point 1 implies point 3. Let ϕ:BM be an isomorphismMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath of monoids. Then clearly mgs(M)ϕ(B); since removing m=ϕ(b) from mgs(M) removes ϕ(b) from M, the equality holds. Let wA and let p,qM satisfy pw,wqM: put x=ϕ-1(p), y=ϕ-1(q), r=ϕ-1(pw), s=ϕ-1(wq). Then ϕ(xs)=ϕ(ry)=pwqM, so xs=ry: this is an equality over B, and is satisfied only by r=xu, s=uy for some u. Then w=ϕ(u)M.


  • 1 M. Lothaire. Combinatorics on words. Cambridge University Press 1997.
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