# free semigroup

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

 $X^{n}=\left\{x_{1}x_{2}\ldots x_{n}\mid x_{j}\in X\hbox{ for all }j\in\left\{1% ,\ldots,n\right\}\right\}$

for all $n\in\mathbb{N}\setminus\left\{0\right\}$, and

 $X^{0}=\left\{\varepsilon\right\},$

where $\varepsilon\notin X$. Note that the set $X$ is not necessarily an alphabet, that is, it may be infinite; for example, we may choose $X=\mathbb{R}$.

We define the sets $X^{+}$ and $X^{*}$ as

 $X^{+}=\bigcup_{n\in\mathbb{N}\setminus\left\{0\right\}}X^{n}$

and

 $X^{*}=\bigcup_{n\in\mathbb{N}}X^{n}=X^{+}\cup\left\{\varepsilon\right\}.$

The elements of $X^{*}$ are called words on $X$, and $\varepsilon$ is called the empty word on $X$.

We define the juxtaposition of two words $v,w\in X^{*}$ as

 $vw=v_{1}v_{2}\ldots v_{n}w_{1}w_{2}\ldots w_{m},$

where $v=v_{1}v_{2}\ldots v_{n}$ and $w=w_{1}w_{2}\ldots w_{m}$, with $v_{i},w_{j}\in X$ 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 semigroup 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 universal mapping problem: given a semigroup $S$ (resp. a monoid $M$) and a map $\Phi\colon X\to S$ (resp. $\Phi\colon X\to M$), a semigroup homomorphism $\overline{\Phi}\colon X^{+}\to S$ (resp. a monoid homomorphism $\overline{\Phi}\colon X^{*}\to M$) exists such that the following diagram commutes:

 $\xymatrix{&X\ar[r]^{\iota}\ar[d]_{\Phi}&X^{+}\ar[dl]^{\overline{\Phi}}\\ &S&}$

(resp.

 $\xymatrix{&X\ar[r]^{\iota}\ar[d]_{\Phi}&X^{*}\ar[dl]^{\overline{\Phi}}\\ &M&}$

), where $\iota\colon X\to X^{+}$ (resp. $\iota\colon X\to X^{*}$) is the inclusion map. It is well known from universal algebra that $X^{+}$ and $X^{*}$ are unique up to isomorphism.

## 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