Prove that the free monoid is unique (up to isomorphism)

Question

For example, if $M^*$ and $N^*$ are two free monoids on a set $U$, I know that I can have two monoid homomorphisms between them (eg. $\varphi: M^* \to N^*, \varPsi: N^* \to M^*$), but the farthest I have been able to get with that is showing that the identities are bijective i.e. $\varphi(\varPsi(e_N)) = e_N$ and vice-versa, but I am not sure how to demonstrate full bijectivity for an isomorphism.

Answer 1

First, note that a free monoid on $U$ consists not just of a monoid $M^*$ but also a function $m : U \to M^*$ (and similarly there is a function $n : U \to N^*$).

Consider the composites. Note that $\phi \circ \psi : N^* \to N^*$ is a monoid momomorphism. Furthermore, consider the fact that $\phi \circ \psi \circ n = \phi \circ m = n = 1_{N^*} \circ m$, where $1_{N^*} : N^* \to N^*$ is the identity monoid homomorphism. Therefore, we see that $\phi \circ \psi = 1_{N^*}$.

A symmetric argument shows that $\phi \circ \psi = 1_{M^*}$. Therefore, $\phi$ and $\psi$ are inverse isomorphisms.

Answer 2

The argument is the same for all free objects: free groups. free monoids, free semigroups, etc.

A monoid $\mathfrak{M}$ is "free on $U$" if and only if it satisfies two properties:

1. There is a set-theoretic map $i\colon U\to \mathfrak{M}$; and
2. For every monoid $M$ and every set theoretic map $f\colon U\to M$, there exists a unique monoid morphism $\phi\colon \mathfrak{M}\to M$ such that $f=\phi\circ i$.

(My functions appear to the left of their arguments and I compose right-to-left).

So suppose that $M$ and $N$ are both free on $U$, with $i\colon U\to M$ and $j\colon U\to N$ the functions from the definition.

The morphism $j\colon U\to N$ induces a unique monoid morphism $\psi\colon M\to N$ such that $j=\psi\circ i$. The morphism $i\colon U\to M$ induces a unique monoid morphism $\phi\colon N\to M$ such that $i=\phi\circ j$.

Now, we note that $i = \phi\circ j = \phi\circ(\psi\circ i) = (\phi\circ\psi)\circ i$. So $\phi\circ\psi\colon M\to M$ is a monoid morphism such that $i = (\phi\circ\psi)\circ i$. The uniqueness clause of the definition tells us that the only morphism with this property is $\mathrm{id}_M\colon M\to M$. Thus, $\phi\circ\psi = \mathrm{id}_M$.

The symmetric argument shows that $\psi\circ\phi = \mathrm{id}_N$. Thus, $\phi$ and $\psi$ are inverses of each other, so they are isomorphisms (being invertible).

Note that we did not use the fact that we had monoids; the exact same argument works if you replace "monoid" with "group", "semigroup", "ring", "$R$-module", "lattice", etc. throughout.