Abstract Algebra and Computation - Monoids

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.

Let's start with the algebraic view - we'll look at that, and then we'll
shift gears and see how it looks categorically. In terms of abstract
algebra, a monoid is an algebraic structure which captures the basic idea of
function composition. That should be ringing some bells - the
fundamental concept of category theory is an abstract view of function
composition!

A monoid is, like a group, a set of values with a single binary
operation. The monoid is a simpler construct though - since all it captures
is the idea of composition, it doesn't need inverses. For a monoid, we say
that it's a set of values, M, and a binary operation º, with three
properties:

1. Closure: ∀a,m∈M: aºb ∈ M
2. Identity: ∃ i∈M : ∀f∈M : iºf = fºi = f.
3. Associativity: ∀ a,b,c∈M: (aºb)ºc = aº(bºc).

That's really it. If you think of those properties in terms of functions
and function composition, they all make really good sense. They're looking
at the most canonical form of functions - so all functions are treated as
being, roughly, functions from natural numbers to natural numbers. Closure
says that if I've got two simple total functions a and b, then composing a
and b is also a simple total function. Identity says that there's a function
f(x)=x which composes properly. And associativity says shifting the order in
which I evaluate compositions doesn't change the resulting composed
function. Those are all very natural properties of function composition.

What happens if we treat a monoid like a group, and try to use it as an
action? The answer is near and dear to the hearts of computer science folks
like me: what you get is basically a finite state machine!

Take a monoid, (M,º). We can define an action of the
monoid on a set S. The action is an operation *:M×S→S - that is,
from a value in M and a value in S to a value in S. This monoid
action of M on S has two properties - which are basically just
extensions of the monoid properties through the action:

1. Identity: ∀s∈S, i*s=s.
2. Associativity: ∀a,b∈M, ∀s∈S: a*(b*s) = (aºb)*s.

What's that mean? What we've done is add function application
to the monoid. The monoidal operation is the application of the functions in
M.

So, what do we get if we have a collection of related composable
functions that can be applied to particular set of values?

An automaton - that is, a mathematical model of a computing device.

How's that an automaton?

With the monoidal operator, each member of the monoid is a
function, which maps a values to values. Monoidal composition
chains those functions together. In terms of automata, each member of the
monoid is a step in a computation. Monoidal composition is chaining
the steps of a computation in the automaton together in sequence. It's not
quite full computation yet - but it's a huge step towards it, in an
extremely simple form.

Think about it just a tad more. Remember href="http://scienceblogs.com/goodmath/2006/08/a_lambda_calculus_rerun_1.php">lambda
calculus? Lambda calculus is a tool from logic for describing
computation in terms of nothing but functions. Guess what? We've just
recreated a substantial part of lambda calculus coming at it from the
direction of abstract algebra.

I'll have more to say about that in future posts - but first I'll need
to show you what this all looks like in terms of category theory - because
the next big step is clearest in category land.