free semigroup

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

$$X^n=\{x_1{x}_2\mathrm{\dots }{x}_n\mid x_j\in X\text{ for all }j\in \{1,\mathrm{\dots },n\}\}$$

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

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

where $\epsilon \notin X$.Note that the set $X$ is not necessarily an alphabet,that is, it may be infinite; for example, we may choose $X=ℝ$.

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\{\epsilon \right\}.$$

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

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

$$vw=v_1{v}_2\mathrm{\dots }{v}_n{w}_1{w}_2\mathrm{\dots }{w}_m,$$

where $v=v_1{v}_2\mathrm{\dots }{v}_n$ and $w=w_1{w}_2\mathrm{\dots }{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 itwe 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 $\mathrm{\Phi }:X\to S$ (resp. $\mathrm{\Phi }:X\to M$),a semigroup homomorphism $\overline{\mathrm{\Phi }}:X^{+}\to S$(resp. a monoid homomorphism $\overline{\mathrm{\Phi }}:X^{*}\to M$)exists such that the following diagram commutes:

(resp.

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