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

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$ .