Why is the free monoid free?

I have been reading up on monoids recently and came across the free monoid Σ*, which (if I understand correctly) is an initial object in the category of monoids, meaning that there is a homomorphism from the free monoid onto any other monoid.

I apologize if this is too simple, but I have two questions:

1. Is this a correct interpretation of the free monoid?
2. If so, does anyone know of a proof (or where I can find one) as to why there is a homomorphism from this monoid onto any other monoid?

Thanks!

-
Is $\Sigma^*$ the monoid whose underlying set is a single idempotent? –  Arturo Magidin Aug 19 '11 at 19:24
I confess that I'm not well-versed enough in the terminology to understand your question. My background is in computer science, where Σ* denotes the monoid of all strings drawn from an alphabet &Sigma;. –  templatetypedef Aug 19 '11 at 19:26
Note that "initial object" means that there is a unique morphism from the object to any other object in the category; that morphism need not be onto, though. For example, $\emptyset$ is the initial object in the category of sets, and the trivial group is the initial object in the category of groups. –  Arturo Magidin Aug 19 '11 at 19:26
Could you give the source where you encountered the claim that this is "an initial object in the category of monoids"? Because the initial object (initial objects, when they exist, are unique up to unique isomorphism) in the category of monoids is the one-element monoid. –  Arturo Magidin Aug 19 '11 at 19:27
From the Wikipedia page: "As the name implies, free monoids and semigroups are those objects which satisfy the usual universal property defining free objects, in the respective categories of monoids and semigroups. It follows that every monoid (or semigroup) arises as a homomorphic image of a free monoid (or semigroup)." –  templatetypedef Aug 19 '11 at 19:29
show 2 more comments

I think you are confusing the universal property of the initial object of a category and the universal property of a free object.

What follows may be a bit too abstract for your taste, so you can skim and skip to the portion below the horizontal line:

Definition. Given a category $\mathcal{C}$, an initial object in $\mathcal{C}$ is an object $s$ such that for each object $a\in \mathcal{C}$ there is exactly one arrow $s\to a$.

An initial object, if it exists, is unique up to unique isomorphism: if $s$ and $s'$ are both initial objects, then there is a unique map $f\colon s\to s'$, a unique map $g\colon s'\to s$. So $g\circ f\colon s\to s$ is the unique map from $s$ to $s$, so $g\circ f = \mathrm{id}_s$; and similarly $f\circ f = \mathrm{id}_{s'}$.

By contrast, a free object is defined in terms of sets:

Definition. Let $\mathcal{C}$ be a category in which every object is a set and every arrow is a set function. Let $\mathbf{U}\colon\mathcal{C}\to\mathcal{S}et$ be the underlying set functor that maps every object to its underlying set. If $X$ is a set, then a free $\mathcal{C}$-object on $X$ is an object $F(X)$ of $\mathcal{C}$, together with a function $i\colon X\to \mathbf{U}(F(X))$ from $X$ to the underlying set of $F(X)$, such that:

• For every object $C\in\mathcal{C}$ and every set-theoretic function $j\colon X\to \mathbf{U}(C)$, there exists a unique arrow $f\colon F(X)\to C$ in $\mathcal{C}$ such that $j=f\circ i$.

A free object on $X$, if it exists, is unique up to unique isomorphism. But the map $f$ need not be onto.

If $\mathcal{C}$ has free objects on every set, then the free object on the empty set is necessarily the initial object in $\mathcal{C}$. Thus, the trivial group is the initial object in $\mathcal{G}roup$, and the trivial monoid is the initial object in $\mathcal{M}onoid$, because the trivial group (resp. monoid) is the free group (resp. monoid) on the empty set. On the other hand, there is no free semigroup on the empty set.

The free $\mathcal{C}$-object on $X$, when it exists, can be interpreted as an initial object, but in a different category: you consider the category of all pairs $(C,j)$, where $C$ is an object of $\mathcal{C}$, $j\colon X\to C$ is a set-theoretic function, and arrows $(C,j)\to (D,k)$ are morphisms $f\colon C\to D$ from $\mathcal{C}$ such that $f\circ j = k$. Then $(F(x),i)$ is an initial object of this category.

If $\Sigma^*$ is the monoid of all strings drawn from the alphabet $\Sigma$, then it turns out that $\Sigma^*$ is the free monoid on the set $\Sigma$. The universal property it satisfies is not being "an initial object in the category of monoids", but rather that described above: given any set-theoretic function $j\colon \Sigma\to M$ into a monoid $M$, there is a unique monoid homomorphism $f\colon \Sigma^*\to M$ such that $f|_{\Sigma}=j$ (that is, $f$, restricted to the set $\Sigma$ viewed as a subset of $\Sigma^*$, is equal to $j$). But this map is not necessarily onto. It is onto if and only if $j(\Sigma)$ generates $M$ (as a monoid).

The proof that $\Sigma^*$ is indeed the free monoid on $\Sigma$ is fairly straightforward. Given $j\colon X\to M$, we define $f\colon \Sigma^*\to M$ recursively, using the definition of $\Sigma^*$:

1. Define $f$ on $\Sigma_0$ (the empty word) as mapping to the identity element of $M$.
2. Define $f$ on $\Sigma_1 = \Sigma$ to be equal to $j$.
3. Having defined $f$ on $\Sigma_i$, define $f$ on $\Sigma_{i+1}$ as follows: given $uv\in\Sigma_{i+1}$, with $u\in\Sigma_i$ and $v\in \Sigma$, define $f(uv)$ to be $f(u)j(v)$.

This defines $f$ on all of $\Sigma^*$. Using associativity, you show that this is a monoid homomorphism. And for uniqueness, you again do it by induction: any other $g$ which agrees with $f$ on $\Sigma_1$ must agree on $\Sigma_0$ (because they are module homomorphisms), and if they agree on $\Sigma_i$, then they will agree on $\Sigma_{i+1}$, since $g(uv) = g(u)j(v) = f(u)j(v)=f(uv)$.

This shows that for any monoid $M$ and any set-theoretic function $j\colon \Sigma\to M$, there is a unique monoid homomorphism $f\colon \Sigma^*\to M$ such that $f(\sigma)=j(\sigma)$ for all $\sigma\in\Sigma$, so $\Sigma^*$ is the free monoid on $\Sigma$.

Again, $f$ will be onto if and only if $\langle j(\Sigma)\rangle = M$. It is always onto $\langle j(\Sigma)\rangle$, since the image is a submonoid of $M$ that contains $\Sigma$, and every element in the image is a product of elements of $j(\Sigma)$.

-
Thank you so much for this amazing explanation. This completely clarifies things and hits right at the heart of the confusion between initial and free objects. –  templatetypedef Aug 19 '11 at 20:00
@templatetypedef: Glad to be of help; note also the issue of "onto", which is often taken to mean "surjective". Neither the maps from free nor from initial objects are surjective in general (surjective may not even make sense for initial objects in arbitrary abstract categories). –  Arturo Magidin Aug 19 '11 at 20:08