202410171810

Tags : Monoid Theory

Free Monoid

---

Given a set $S$, a free monoid generated by $S$ is the set of elements that can be constructed by taking arbitrary finite sequences of terms in $S$. In some sense the free monoid on $S$ is the set of words over the alphabet $S$.

The identity element of the free monoid is generally considered to be the empty string $ϵ$ and the monoid operator is concatenation.

Universal Property of Free Structures

In the category of monoids, let $U$ be a faithful functor (forgetful functor) to the category of sets, and let $X$ be a set.

A free monoid on $X$ is an object $A$ in the category of monoids along with the inclusion map $i:X\to U(A)$ such that for any object $B$ in the category of monoids and $f:A\to B$, there exists a unique $g:X\to U(B)$ such that the following triangle commutes.

\usepackage{tikz-cd} 
\begin{document} 
\begin{tikzcd} 
A \arrow[dashed]{d}{f} & X \arrow{r}{i} \arrow{dr}[swap]{!g} & U(A) \arrow[dashed]{d}{U(f)} \\ B & & U(B) 
\end{tikzcd} 
\end{document}

---

References

Monoids Quotients of Syntactic Monoid of a language