free semigroup


Let X be a set. We define the power of X in a language-theoretical manner as

Xn={x1x2xnxjX for all j{1,,n}}

for all n{0}, and

X0={ε},

where εX. Note that the set X is not necessarily an alphabet, that is, it may be infiniteMathworldPlanetmath; for example, we may choose X=.

We define the sets X+ and X* as

X+=n{0}Xn

and

X*=nXn=X+{ε}.

The elements of X* are called words on X, and ε is called the empty wordPlanetmathPlanetmathPlanetmath on X.

We define the juxtaposition of two words v,wX* as

vw=v1v2vnw1w2wm,

where v=v1v2vn and w=w1w2wm, with vi,wjX for each i and j. It is easy to see that the juxtaposition is associative, so if we equip X+ and X* with it we obtain respectively a semigroupPlanetmathPlanetmath and a monoid. Moreover, X+ is the free semigroup on X and X* is the free monoid on X, in the sense that they solve the following universalPlanetmathPlanetmathPlanetmath mapping problem: given a semigroup S (resp. a monoid M) and a map Φ:XS (resp. Φ:XM), a semigroup homomorphism Φ¯:X+S (resp. a monoid homomorphism Φ¯:X*M) exists such that the following diagram commutes:

\xymatrix&X\ar[r]ι\ar[d]Φ&X+\ar[dl]Φ¯&S&

(resp.

\xymatrix&X\ar[r]ι\ar[d]Φ&X*\ar[dl]Φ¯&M&

), where ι:XX+ (resp. ι:XX*) is the inclusion mapMathworldPlanetmath. It is well known from universal algebraMathworldPlanetmathPlanetmath that X+ and X* are unique up to isomorphismMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath.

References

  • 1 J.M. Howie, Fundamentals of Semigroup Theory, Oxford University Press, Oxford, 1991.
Title free semigroup
Canonical name FreeSemigroup
Date of creation 2013-03-22 16:11:41
Last modified on 2013-03-22 16:11:41
Owner yark (2760)
Last modified by yark (2760)
Numerical id 15
Author yark (2760)
Entry type Definition
Classification msc 20M10
Classification msc 20M05
Related topic Word
Defines word
Defines empty word
Defines free semigroup
Defines free monoid