Software! Math! Data! The blog of R. Sean Bowman
The blog of R. Sean Bowman
October 03 2015

At the risk of alienating those of you who are more interested in software than abstract mathematics, I’d like to write about some basic category theory. The idea is to work my way up to defining a monad, because that seems to be a requisite exercise for any programming language blogger. Here, I’d like to talk about something a bit simpler: monoids.

Category theory is a strange beast. There are many mathematicians who consider it a language to talk about concepts that might appear different at first, but have an underlying general structure. Some of these people consider category theory as a “language” to talk about math, and not much more. Others consider category theory to be worthy of study per se. Clearly modern logic and parts of computers science rest on deep results from category theory. I prefer not to take sides: my work never used category theory much, but on the other hand I find it very interesting.

For the sake of time and my sanity and the fact that there are hundreds of "basic category theory" posts out there, I’m going to assume you know the fundamentals: what a category is, morphism, functors, and natural transformations. As usual, Wikipedia has great articles on categories and category theory, so you can look to those if you need a refresher.

Monoids

On to the real stuff: recall (maybe) that a monoid is like a group without inverses. That is, it’s a set together with an associative binary operation (usually written like multiplication) and an identity element. An example is the natural numbers with addition. The operation (addition) is clearly associative, there’s an identity element (0), but there are no inverses because negative numbers aren’t included in the set.

Monoidal categories

Now it turns out that the idea of a monoid has a categorical definition, and this concept is useful in lots of places. So how might we translate the idea of a monoid into a categorical setting? First, we need a special kind of category in order to be able to “multiply” and have an “identity.” This is called a monoidal category, appropriately. It’s pretty simple, really; it’s just a category \(C\) together with

  • a bifunctor \(\otimes\colon C\times C\rightarrow C\) which is associative up to a natural isomorphism, and
  • an object \(I\) of \(C\) which is a left and right identity for \(\otimes\), again up to a natural isomorphsm.

Here “up to a natural isomorphism” means that we can consider, in the first case, \((M\otimes M)\otimes M\) to be the same object as \(M\otimes (M\otimes M)\), where \(M\) is some object of \(C\). In the second case, \(I\otimes M\) and \(M\otimes I\) can both be considered equivalent to \(M\).

Examples of such categories abound, and in fact monoidal categories with extra structure (strict, symmetric, braided, etc.) are quite important in fields like string theory and topological quantum field theory. Khovanov homology, among many other fascinating theories, rests on top of these types of categorical structures.

Monoids in categories.

We’re finally ready to define a monoid in a monoidal category \(C\). A monoid \(M\) in \(C\) is an object together with a morphism \(\mu\colon M\otimes M\rightarrow M\) (which acts like multiplication) and \(\eta\colon I\rightarrow M\) (which acts like the unit element).

We also need some conditions saying the categorical equivalent of "multiplication is associative" and "\(\eta\) is really a unit in some sense." Here is a condition saying that \(\mu\) is associative:

\[ \begin{xy} \xymatrix{ M^3\ar[r]^{1\otimes\mu}\ar[d]_{\mu\otimes 1}& M^2\ar[d]^{\mu}\\ M^2\ar[r]_{\mu} & M } \end{xy} \]

Here we’ve abbreviated \(M\otimes M\) to \(M^2\), and similarly for \(M^3\). Here’s another condition that says that \(\eta\) acts like an identity:

\[ \begin{xy} \xymatrix{ I\otimes M\ar[r]^{\eta\otimes 1}\ar[dr] & M\otimes M\ar[d]^{\mu} & M\otimes I\ar[l]_{1\otimes\eta}\ar[dl]\\ & M & } \end{xy} \]

You can also have a look at these diagrams at Wikipedia. The maps \(\mu\otimes 1\) and so forth are just this: if we have the object \(M\otimes M\otimes M\), we can act by \(\mu\) on the first two copies and carry the third copy right through. This gives us \(M\otimes M\). Similarly, \(1\otimes\mu\) acts on the right two copies of \(M\), again giving \(M\). Keep in mind that although the codomain of both maps is \(M\otimes M\), there’s no reason to believe that the maps are equal. (It would be quite boring, in fact, if they were…)

How does this generalize the idea of a monoid? Well, the category of sets is a monoidal category if you consider \(\otimes\) to just be the regular Cartesian product. A monoid in this category is just a monoid in the usual algebraic sense we talked about above. Let see why. Let \(a, b\), and \(c\) be elements of \(M\). (Normally we can’t exactly talk about “elements of an object in a category,” but since we’re dealing with the category of sets here, I think it’s okay.) The first diagram says that \(a(bc) = (ab)c\), associativity. The second diagram says that that there is an element \(e\) (the one picked out by \(\eta\)) so that \(ea = ae\) for any \(a\) in the monoid. So the monoid has an identity element.

Cool! When the category \(C\) has more structure, we get monoids with that extra structure. For example, a monoid in the category of topological spaces is a topological monoid. And so on.

Of course, Wikipedia has some great info about this, but one of the best references for this kind of stuff is Categories for the Working Mathematician by one of my mathematical heroes, Saunders MacLane. This book is not for the faint of heart, as it lives up to its title. However, MacLane pretty much invented category theory, popularizing the name “monad” (even though he did not come up with the idea). This book is quite authoritative.

Approx. 959 words, plus code