PlanetMath: free semigroup with involution

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (210)
Orphanage
Unclass'd (1)
Unproven (472)
Corrections (37)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

free semigroup with involution

(Example)

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 the free semigroup on . We can extend the map $^\ddagger$ to an involution $^\ddagger:Y^+\rightarrow Y^+$ on in the following way: given $w\in Y^+$ , we have for some letters $w_i\in Y$ ; then we define

$\displaystyle 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

. 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

, in the sense that it solves the following universal problem: given a semigroup with involution

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:

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

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 instead of , where $Y^*=Y^+\cup\{\varepsilon\}$ and $\varepsilon$ is the empty word (i.e. the identity of the monoid ), we obtain a monoid with involution $(X\amalg X^\ddagger)^*$ that is the free monoid with involution on .