Generated Submonoid is Set of Words of Generator

Theorem

Let $\struct {M, \circ}$ be a monoid whose identity is $e_M$.

Let $S \subseteq M$.

Let $\gen S$ be the submonoid of $\struct {M, \circ}$ generated by $S$.

Then:

$\gen S = \set {\ds \sum_{i \mathop = 1}^r n_i \cdot s_i : r \in \N, n_i \in \N, s_i \in S}$

where:

$n_i \cdot s_i$ denotes the power of $s_i$:
$n \cdot a = \begin {cases} e_M & : n = 0 \\ \paren {\paren {n - 1} \cdot a} \circ a & : n > 0 \end {cases}$
$\ds \sum_{i \mathop = 1}^r n_i \cdot s_i := \paren {n_1 \cdot s_1} \circ \paren {n_2 \cdot s_2} \circ \cdots \circ \paren {n_r \cdot s_r}$

That is, $\gen S$ is the set of words of $S$.