symmetric alphabet. Let be a bijection; is naturally extended to a bijection essentially by taking the disjoint union of (as a set) with its inverse, or in piecewise notation: Now construct as the free semigroup on in the usual way with the binary (semigroup) operation on being concatenation: for some letters The bijection on is then extended as a bijection defined as the string reversal of the elements of that consist of more than one letter: This map is an involution on the semigroup . Thus, the semigroup with the map is a semigroup with involution, called a free semigroup with involution on X. (The irrelevance of the concrete identity of and of the bijection in this choice of terminology is explained below in terms of the universal property of the construction.) Note that unlike in Example 6, the involution of every letter is a distinct element in an alphabet with involution, and consequently the same observation extends to a free semigroup with involution. If in the above construction instead of we use the free monoid , which is just the free semigroup extended with the empty word (which is the identity element of the monoid ), and suitably extend the involution with , we obtain a free monoid with involution. The construction above is actually the only way to extend a given map from to , to an involution on (and likewise on ). The qualifier "free" for these constructions is justified in the usual sense that they are universal constructions. In the case of the free semigroup with involution, given an arbitrary semigroup with involution and a map , then a semigroup homomorphism exists such that , where is the inclusion map and composition of functions is taken in diagram order. The construction of as a semigroup with involution is unique up to isomorphism. An analogous argument holds for the free monoid with involution in terms of monoid homomorphisms and the uniqueness up to isomorphism of the construction of as a monoid with involution. The construction of a free group is not very far off from that of a free monoid with involution. The additional ingredient needed is to define a notion of reduced word and a rewriting rule for producing such words simply by deleting any adjacent pairs of letter of the form or . It can be shown than the order of rewriting (deleting) such pairs