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:
- Closure: ∀a,m∈M: aºb ∈ M
- Identity: ∃ i∈M : ∀f∈M : iºf = fºi = f.
- 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:
- Identity: ∀s∈S, i*s=s.
- 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 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.
Physical Science
Technology
Comments
A small typo Mark or at least I think so. Your monoid properties should read:
∀ a,b∈M
Posted by: Thony C. | February 11, 2008 2:27 AM
A monoid isn't just the "equivalent" of a category, a monoid is a category. It's exactly what you get when you ask for a category with a single object, just like a group is exactly a groupoid with a single object!
Posted by: John Armstrong | February 11, 2008 9:36 AM
May I add that an ordered Abelian monoid is an ordered monoid groupoid?
Are you going to connect this with the standard and new-style formalisms (n-Categories and the like) connecting semigroups, automata and languages?
I like groups, semigroups, groupoids, and monoids. I like the ways that you present them in a multi-level format, painlessly introductory to new students, tie-the-pieces together for intermediate students who know some theory but are unclear on The Big Picture, and cutting edge theory and publications and conjectures for the advanced students. You're a good teacher, to keep the slow, median, and fast students all alert and entertained in the same blogular virtual classroom, Mark!
But, as this Saint Valentine's Day, today, is also the 22nd wedding anniversary of my Physics Professor wife and my absurdly lucky self: no group, groupie, or groupoid sex, please; just monoid monogamy.
Posted by: Jonathan Vos Post | February 14, 2008 4:22 AM