User:Jshflynn/Length is Epimorphism

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\Sigma$ be an alphabet.


Let $\Sigma^{*}$ be the Kleene star of $\Sigma$ and $\circ$ denote concatenation.


Then the length function is an epimorphism from $(\Sigma^{*}, \circ)$ to $(\mathbb{N}_0, +)$.


Proof

The morphism property follows immediately from Length of Concatenation as:


$\operatorname{len}(x \circ y) = \operatorname{len}(x) + \operatorname{len}(y)$.


Hence it remains to be shown that length is a surjective function.


As a special case $0$ has a pre-image as:


$\operatorname{len}(\lambda \circ \lambda) = \operatorname{len}(\lambda) + \operatorname{len}(\lambda) = 0 + 0 = 0$


Now let $n \in \mathbb{N}$ and let $x \in \Sigma^{n}$


As:


$\operatorname{len}(x) = n$


We have that $\forall n \in \mathbb{N}_0: \exists x \in \Sigma^{*}: \operatorname{len}(x)=n$


Hence the result.


$\blacksquare$