= Free monoid
{title2=$\Sigma^*$}
{wiki}
The <free monoid> $\Sigma^*$ on an <alphabet> $\Sigma$ consists of all finite <words over an alphabet>, including the <empty word> $\varepsilon$, with <concatenation> as its <binary operation>. Distinct <strings> represent distinct elements: there are no imposed equalities between different sequences of letters. The <empty word> is its <identity element>, and <concatenation> has the <associative property>.<Group Theory (v4.01) by James S. Milne>[§2: free monoids]{ref}
For $\Sigma=\{a,b\}$, the elements begin $\varepsilon,a,b,aa,ab,ba,bb,\ldots$. Both $(ab)a$ and $a(ba)$ give the same <word> $aba$, but $ab\ne ba$, so this <monoid> is not <commutative>. The <length of a word over an alphabet> obeys $\ell(uv)=\ell(u)+\ell(v)$; it is a <monoid homomorphism> to the nonnegative <integers> with <addition>. A nonempty <word> has no <inverse element>, since joining it to any other <word> cannot decrease its length to zero.
The defining benefit of being free is that letters can stand for arbitrary elements of another <monoid>. Choose a value $h(a)$ for each letter $a\in\Sigma$; then $h(a_1\cdots a_n)=h(a_1)\ast\cdots\ast h(a_n)$, with $h(\varepsilon)=e$, is the unique <monoid homomorphism> extending those choices. <Associativity> and the <identity element> make this evaluation consistent for every finite <word>. For example, interpreting the letters as <self-maps> evaluates a <word> as a composed transformation; interpreting them as nonnegative counts evaluates it by <addition>.
Back to article page
