Back to the index. Or to the chambers

This article has 15 links. View as Cloud or List.

Mapping Inclusion Mapping Algebraic System General Associativity Group Homomorphism Commutative Diagram Infinite Obvious Associative Function Semigroup Concatenation Monoid Universal Property Alphabet

Loading ...

Planetmath Browser (2008—2009)

BSD licence | A django site

All articles taken from PlanetMath.org snapshot under CC-BY-SA licence.

→ The original article on PlanetMath.org

Other Formats: LaTeX

New! You can click on formulas to copy the LaTeX source to your clipboard. | Math Videos

Free Semigroup

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

$\begin{displaymath} X^n=\left\{ x_1x_2\ldots x_n\mid x_j\in X \hbox{ for all }j\in\left\{ 1,\ldots,n \right\} \right\} \end{displaymath}$

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

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

where $\varepsilon\notin X$ . Note that the set

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

We define the sets and as

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

and

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

The elements of

are called words on

, and $\varepsilon$ is called the empty word on

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

$\begin{displaymath} vw=v_1v_2\ldots v_n w_1w_2\ldots w_m, \end{displaymath}$

where $v=v_1v_2\ldots v_n$ and $w=w_1w_2\ldots w_m$ , with $v_i,w_j\in X$ for each

and

. It is easy to see that the juxtaposition is associative, so if we equip

and

with it we obtain respectively a semigroup and a monoid. Moreover,

is the free semigroup on

and

is the free monoid on

, in the sense that they solve the following universal mapping problem: given a semigroup

(resp. a monoid

) 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:

$\begin{displaymath}\begin{xy} *!C\xybox{ \xymatrix{ & X \ar[r]^{\iota} \ar[d]_{\Phi} & X^+ \ar[dl]^{\overline{\Phi}} \\ & S & } } \end{xy}\end{displaymath}$

(resp.

$\begin{displaymath}\begin{xy} *!C\xybox{ \xymatrix{ & X \ar[r]^{\iota} \ar[d]_{\Phi} & X^* \ar[dl]^{\overline{\Phi}} \\ & M & } } \end{xy}\end{displaymath}$

), where $\iota\colon X\to X^+$ (resp. $\iota\colon X\to X^*$ ) is the inclusion map. It is well known from universal algebra that

and

are unique up to isomorphism.

Bibliography

1: J.M. Howie, Fundamentals of Semigroup Theory, Oxford University Press, Oxford, 1991.

1	Commutative Diagram
1	Algebraic System
1	Obvious
1	Function
1	Inclusion Mapping
1	Mapping
1	Infinite
1	Group Homomorphism
1	Associative
1	General Associativity
1	Semigroup
2	Concatenation
2	Alphabet
2	Monoid
3	Universal Property