Free Commutative Monoid on One Element is Isomorphic to Positive Integers under Addition

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $X = \left\{{x}\right\}$ be a singleton.

Let $M$ be the free commutative monoid on $X$.


Then $M$ is isomorphic to the additive monoid of natural numbers.


Proof

By definition, the free commutative monoid $M$ on $\left\{{x}\right\}$ is:

$M = \left\{{e, x, x^2, x^3, \ldots}\right\}$

where $e$ denotes the null sequence of elements of $X$.

Let $\phi$ denote the mapping from $M$ to $\N$ as:

$\forall a \in M: \phi \left({a}\right) = \begin{cases} 0 & : a = e \\ n & : a = x^n \end{cases}$


By definition of $\phi$:

$\phi$ is injective: $\phi \left({a}\right) = \phi \left({b}\right) \implies a = b$
$\phi$ is surjective: $\forall a \in \N: \exists b \in M: \phi \left({b}\right) = a$
$\phi$ is a monoid homomorphism: $\phi \left({a b}\right) = \phi \left({a + b}\right) = \phi \left({a}\right) + \phi \left({b}\right)$

Hence the result, by definition of isomorphism.

$\blacksquare$


Sources