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 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 $\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 algebra that $X^{+}$ and $X^{*}$ are unique up to isomorphism.

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