Category Theory, An Introduction


Much of mathematics involves pattern recognition, followed by generalization, then the swift application of the general to a problem that has not been seen before.  Let me couch this in terms of computer programming, since I have been a professional programmer for 25 years.

You write a ream of software to accomplish a certain task, and you feel like you've been here before.  No, you didn't write this exact code before, line for line, but you wrote something very similar last year.  You go back through your archives and dig out your old code.  It does almost exactly what you want, with a few minor changes.  You decide to write one program that handles both tasks.  You'll need a couple parameters to accommodate the variations between tasks, but there is so much commonality; a dual-use program is the only way to go.

You explain to your boss that you "Want to do it right."  You want to build a flexible program that will handle both tasks.  There will be less code over all, and fewer bugs, and if a bug is found, you can fix it once, not twice.  But it will take a little longer to get the job done, because you're building a useful infrastructure, instead of solving today's problem as quickly as possible.  You'll also need to run regression tests on the first task, to make sure the new program is handling it properly.  That'll be another week, if nothing goes wrong.

Your boss pulls out his gant chart and frowns.  "I like your idea, but we can't slip schedule.  I suggest you work weekends to make these changes.  No - you won't be getting any additional compensation, but maybe I can sign you up for the Jelly of the Month club this Christmas.  You know, that's the gift that keeps on giving the whole year through."

Just before Christmas you are asked to do a third task that is similar to the first two.  This was unexpected; right out of the blue.  But you recognize it for what it is.  You call up your 35,000 line program, tweak it just a bit, and invoke it with the appropriate parameters.  Voila, the task is complete, ahead of schedule, and with a couple features that your boss didn't expect.  Now he's smiling, and you might even get a bonus this year, if your job hasn't been outsourced to India.

What does all this have to do with category theory?

Let me illustrate with rings.  In 300 BC, Euclid knew that every integer factors uniquely into primes.  But after a while, all right, after two millennia, people developed related structures, like the gaussian integers.  They have primes too, i.e. numbers with no smaller factors.  Is every composite a unique product of primes?  It is, and the proof is very similar to its integer counterpart.  Perhaps there is a generalization here.

There is.  Rings of this form are now called euclidean domains.

If a new ring pops up, a ring we've never seen before, and if we can prove it has the properties of a euclidean domain, we get unique factorization for free.  We don't have to investigate prime and composite elements from scratch; we already know that every element factors into a unique set of primes.  It's already done.

However, there are other rings that are not euclidean, yet they exhibit unique factorization as well.  Perhaps there is a broader generalization here.  Unique factorization, be it euclidean or not, has some wonderful properties, like greatest common divisor and least common multiple.  We should be able to take advantage of this.

Thus another generalization was born, the unique factorization domain, also called a ufd.  If you can prove that R is a ufd, by any method, euclidean or otherwise, then any two elements have a greatest common divisor and a least common multiple.  You get that for free.

Groups, fields, topological spaces, vector spaces, noetherian modules, and on and on.  These are all generalizations that encompass a wide range of problems in math.  Prove a theorem about groups, and it can be applied in many different situations, like calling up a program with different parameters.

Category theory is the greatest generalization of them all.  It is so general, it is sometimes called generalized abstract nonsense.  And sometimes it seems that way; too abstract to have any utility at all.  But this isn't quite true.  Category theory can help in certain situations.

Check out this free category theory software package.