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.

## Archive for the 'Abstract Algebra' category

## Monoids and Computation: Syntactic Monoids

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.

## Ideals - Abstract Integers

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?

## Full Circle: the Categorical Monoid

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?

## This is getting fun! On to Monoidal Categories.

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.

## 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.