Free monoid

Remarks

Concatenation is associative and $\varepsilon$ is a two-sided identity, so $A^*$ is a monoid. Universal property: for every monoid $M$ and every map $f \colon A \to M$, there is exactly one monoid homomorphism $\bar f \colon A^* \to M$ with $\bar f(a) = f(a)$ for $a \in A$, namely $\bar f(a_1 \cdots a_n) = f(a_1) \cdots f(a_n)$. A monoid is called free if it is isomorphic to some $A^*$. The free semigroup $A^+$ is $A^*$ without the empty word.

Example: for $A = \set{a}$, the map $a^n \mapsto n$ is an isomorphism from $A^*$ onto the monoid $(\N, +)$ with $0 \in \N$.

Non-example: the monoid $(\Z, +)$ is not free. In a free monoid, $uv = \varepsilon$ forces $u = v = \varepsilon$, because lengths add; but in $\Z$, $1 + (-1) = 0$ with $1 \ne 0$.