The Unapologetic Mathematician

Mathematics for the interested outsider

Free Monoid Objects

When we have an algebraic concept described as a set with extra structure, the morphisms between such structured sets are usually structure-preserving functions between the underlying sets. This gives us a “forgetful” functor which returns the underlying sets and functions. Then as we saw, we often have a left adjoint to this forgetful functor giving the “free” structure generated by a set.

But now that we’re talking about monoid objects we’re trying not to think about sets. A monoid object in \mathcal{C} is a monoidal functor from \mathrm{Th}(\mathbf{Mon}) to \mathcal{C}, and a “homomorphism” of such monoid objects is a monoidal natural transformation. But the object part of such a functor is specified by one object of \mathcal{C} — the image of M\in\mathrm{Th}(\mathbf{Mon}) — which we can reasonably call the “underlying object” of the monoid object. Similarly, a natural transformation will be specified by a morphism between the underlying objects (subject to naturality conditions, of course). That is, we have a “forgetful functor” from monoid objects in \mathcal{C} to \mathcal{C} itself. And a reasonable notion of a “free” monoid object will be a left adjoint to this functor.

Now, if the monoidal category \mathcal{C} has coproducts indexed by the natural numbers, and if the functors C\otimes\underline{\hphantom{X}} and \underline{\hphantom{X}}\otimes C preserve these coproducts for all objects C\in\mathcal{C}, then the forgetful functor above will have a left adjoint. To say that the monoidal structure preserves these coproducts is to say that the following “distributive laws” hold:

\coprod\limits_n(A\otimes B_n)\cong A\otimes\biggl(\coprod\limits_nB_n\biggr)
\coprod\limits_n(A_n\otimes B)\cong\biggl(\coprod\limits_nA_n\biggr)\otimes B

For any object C\in\mathcal{C} we can define the “free monoid object on C” to be \coprod\limits_nC^{\otimes n}, equipped with certain multiplication and unit morphisms. For the unit, we will use the inclusion morphism C^{\otimes0}\rightarrow\coprod\limits_nC^{\otimes n} that comes for free with the coproduct. The multiplication will take a bit more work.

Given any natural numbers m and n, the object C^{\otimes m}\otimes C^{\otimes n} is canonically isomorphic to C^{\otimes m+n}, which then includes into \coprod\limits_kC^{\otimes k} using the coproduct morphisms. But this object also includes into \coprod\limits_{i,j}(C^{\otimes i}\otimes C^{\otimes j}), which is isomorphic to \biggl(\coprod\limits_iC^{\otimes i}\biggr)\otimes\biggl(\coprod\limits_jC^{\otimes j}\biggr). Thus by the universal property of coproducts there is a unique morphism \mu:\biggl(\coprod\limits_iC^{\otimes i}\biggr)\otimes\biggl(\coprod\limits_jC^{\otimes j}\biggr)\rightarrow\biggl(\coprod\limits_kC^{\otimes k}\biggr). This is our multiplication.

Proving that these two morphisms satisfy the associativity and identity relations is straightforward, though somewhat tedious. Thus we have a monoid object in \mathcal{C}. The inclusion C=C^{\otimes1}\rightarrow\coprod\limits_nC^{\otimes n} defines a universal arrow from C to the forgetful functor, and so we have an adjunction.

So what does this look like in \mathbf{Set}? The free monoid object on a set S will consist of the coproduct (disjoint union) of the sets of ordered n-tuples of elements of S. The unit will be the unique {0}-tuple (), and I’ll leave it to you to verify that the multiplication defined above becomes concatenation in this context. And thus we recover the usual notion of a free monoid.

One thing I slightly glossed over is showing that \mathbf{Set} satisfies the hypotheses of our construction. It works here for the same reason it will work in many other contexts: \mathbf{Set} is a closed category. Given any closed category with countable coproducts, the functor C\otimes\underline{\hphantom{X}} has a right adjoint by definition. And thus it preserves all colimits which might exist. In particular, it preserves the countable coproducts, which is what the construction requires. The other functor preserves these coproducts as well because the category is symmetric — tensoring by C on the left and tensoring by C on the right are naturally isomorphic. Thus we have free monoid objects in any closed category with countable coproducts.

About these ads

August 2, 2007 - Posted by | Category theory

2 Comments »

  1. [...] Free Monoid Objects [...]

    Pingback by Free Algebras « The Unapologetic Mathematician | August 3, 2007 | Reply

  2. [...] is exactly the free algebra on a vector space, and it’s just like we built the free ring on an abelian group. If [...]

    Pingback by Tensor and Symmetric Algebras « The Unapologetic Mathematician | October 26, 2009 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 388 other followers

%d bloggers like this: