# free semigroup with involution

Let $X,X^{\ddagger}$ be two disjoint sets in bijective correspondence given by the map ${}^{\ddagger}:X\rightarrow X^{\ddagger}$. Denote by $Y=X\amalg X^{\ddagger}$ (here we use $\amalg$ instead of $\cup$ to remind that the union is actually a disjoint union) and by $Y^{+}$ the free semigroup on $Y$. We can extend the map ${}^{\ddagger}$ to an involution ${}^{\ddagger}:Y^{+}\rightarrow Y^{+}$ on $Y^{+}$ in the following way: given $w\in Y^{+}$, we have $w=w_{1}w_{2}...w_{k}$ for some letters $w_{i}\in Y$; then we define

 $w^{\ddagger}=w_{k}^{\ddagger}w_{k-1}^{\ddagger}...w_{2}^{\ddagger}w_{1}^{% \ddagger}.$

It is easily verified that this is the unique way to extend ${}^{\ddagger}$ to an involution on $Y$. Thus, the semigroup $(X\amalg X^{\ddagger})^{+}$ with the involution $\ddagger$ is a semigroup with involution. Moreover, it is the free semigroup with involution on $X$, in the sense that it solves the following universal problem: given a semigroup with involution $S$ and a map $\Phi:X\rightarrow S$, a semigroup homomorphism $\overline{\Phi}:(X\amalg X^{\ddagger})^{+}\rightarrow S$ exists such that the following diagram commutes:

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

where $\iota:X\rightarrow(X\amalg X^{\ddagger})^{+}$ is the inclusion map. It is well known from universal algebra that $(X\amalg X^{\ddagger})^{+}$ is unique up to isomorphisms.

If we use $Y^{*}$ instead of $Y^{+}$, where $Y^{*}=Y^{+}\cup\{\varepsilon\}$ and $\varepsilon$ is the empty word (i.e. the identity of the monoid $Y^{*}$), we obtain a monoid with involution $(X\amalg X^{\ddagger})^{*}$ that is the free monoid with involution on $X$.

Title free semigroup with involution FreeSemigroupWithInvolution 2013-03-22 16:11:30 2013-03-22 16:11:30 Mazzu (14365) Mazzu (14365) 8 Mazzu (14365) Example msc 20M10 free semigroup with involution free monoid with involution