Since I mentioned the idea of monoids as a formal models of computations, John Armstrong made the natural leap ahead, to the connection between monoids and monads – which are a common feature in programming language semantics, and a prominent language feature in Haskell, one of my favorite programming languages.
While doing some reading on rings, I came across some interesting stuff about
Monoids and syntax. That’s right up my alley, so I decided to write a post about that.
When I first talked about rings, I said that a ring is an algebraic
abstraction that, in a very loose way, describes the basic nature of integers. A ring is a full abelian group with respect to addition – because the integers
are an abelian group with respect to addition. Rings add multiplication with an
identity – because integers have multiplication with identity. Ring multiplication doesn’t include an inverse – because there is no multiplicative inverse in
the integers.
But a ring isn’t just the set of integers with addition and multiplication. It’s an abstraction, and there are lots of thing that fit that abstraction beyond the basic realization of the ring of integers. So what are the elements of those
things? They can be pretty much anything – there are rings of topological spaces,
rings of letters, rings of polynomials. But can we use the abstraction of
the ring to create an abstraction of an object that resembles an integer, rather than an abstraction that resembles the set of all integers?
By now, we’ve seen the simple algebraic monoid, which is essentially an
abstract construction of a category. We’ve also seen the more complicated, but interesting monoidal category – which is, sort of, a meta-category – a category built using categories. The monoidal category is a fairly complicated object – but it’s useful.
What does a algebraic monoid look like in category theory? The categorical monoid is a complex object – a monoid built from monoids. If we render the algebraic monoid in terms of a basic category, what do we get? A monoid is, basically, a category with one object. That’s it: every algebraic monoid is a single object category.
But we can do something more interesting than that. We know what a monoidal category looks like. What if we take a monoidal category, and express the fundamental concept of a monoid in it?
In the last post on groups and related stuff, I talked about the algebraic construction of monoids. A monoid is, basically, the algebraic construction of a category – it’s based on the same ideas, and has the same properties; just the presentation of it is different.
But you can also see a monoid in categorical terms. It’s what we computer scientists would call a bootstrapped definition: we’re relying on the fact that we have all of the constructs of category theory, and then using category theory to rebuild its own basic concepts.
In the last couple of posts, I showed how we can start looking at group
theory from a categorical perspective. The categorical approach gives us a
different view of symmetry that we get from the traditional algebraic
approach: in category theory, we see symmetry from the viewpoint of
groupoids – where a group, the exemplar of symmetry, is seen as an
expression of the symmetries of a simpler structure.
We can see similar things as we climb up the stack of abstract algebraic
constructions. If we start looking for the next step up in algebraic
constructions, the rings, we can see a very different view of
what a ring is.
Before we can understand the categorical construction of rings, we need
to take a look at some simpler constructions. Rings are expressed in
categories via monoids. Monoids are wonderful things in their own right, not
just as a stepping stone to rings in abstract algebra.
What makes them so interesting? Well, first, they’re a solid bridge
between the categorical and algebraic views of things. We saw how the
category theoretic construction of groupoids put group theory on a nice
footing in category theory. Monoids can do the same in the other direction:
they’re in some sense the abstract algebraic equivalent of categories.
Beyond that, monoids actually have down-to-earth practical applications –
you can use monoids to describe computation, and in fact, many of the
fundamental automatons that we use in computer science are, semantically,
monoids.