Categorification

Categorification is a big, scary word that refers to a much simpler basic idea than you’d expect, and it’s also huge business right now. There’s a lot of this going on at The n-Category Café, for instance. Both knot Floer homology and Khovanov homology are examples of categorifications that seem to be popular with the crew at the Secret Blogging Seminar. John Baez has a bunch of papers circling around “higher-dimensional algebra”, which is again about categorification.

So what is categorification? Well, as I said the core idea’s not really that hard to grasp, but it’s even easier to understand by first considering the reverse process: decategorification. And decategorification is best first approached through an example.

Since this post will be going to this fortnight’s Carnival, I’ll be saying a fair amount that I’ve said before and linking back to definitions most regular readers should know offhand. It might seem slower, but I’ll be back up to the regular rhetorical pace tomorrow. Or you could take it as a bit of review, just to make sure you’re on top of things. Because of this, the post is going to get long, so I’ll put it behind a jump.

Let’s consider the category of finite sets and functions between them. We’ve identified various kinds of functions that are of special interest to us: one-to-one functions (“injections” or “monomorphisms”), onto functions (“surjections” or “epimorphisms”), and functions which are both (“bijections” or “isomorphisms”). Right now we’re particularly interested in isomorphisms in this category — bijections of finite sets. More to the point, we’re interested in getting rid of them. “Isomorphic” means “essentially the same”, so why bother with a bunch of different copies of what are essentially the same set over and over again? We can set up a bijection from the set to the set , so let’s just say they’re the same thing.

“What? Madness!”, you say, and it’s easy to say that when you’re holding the category in your hands. The dirty little secret is that we do this all the time without saying so explicitly, and we teach all our children to do the same thing. The term we tell them is “counting”, and the more technical term is cardinality. We can set up a bijection between two finite sets exactly when they have the same number of elements. Identifying such sets amounts to forgetting everything about them except how many elements they have. The tautology “3=3” expands to, “the number of elements in is the same as the number of elements in ,” which really means, “there is a bijection between and .”

This is an example of decategorification: we take some category — here it’s — and break it down to the set of isomorphism classes of its objects — here it’s the set of natural numbers. This loses a lot of information. In particular, we only say that two objects are isomorphic instead of how they are isomorphic. Categorification is the (somewhat loosely-defined) reverse process of trying to replace equations by explicit isomorphisms.

There’s a story (fable?) I remember from when I was first learning about the abstract notion of “number”. A shepherd lets his flock out from the pen to graze during the day, but he wants to make sure that they all come back at night. To handle this, as they leave the pen in the morning he picks up a little stone as each sheep leaves the pen and puts it in a bag. In the evening, each time a sheep enters the pen he takes a stone out of the bag. If the bag is empty when the sheep are all in, he’s got the same number in the pen as he did in the morning.

What’s “really” going on here? There are three sets we’re looking at: , , and . When the shepherd puts a stone in the bag for each sheep leaving in the morning he’s setting up an explicit bijection from to . Then when he takes a stone out for each returning sheep he’s setting up an explicit bijection from to . We can compose these two bijections to get a bijection from to . That is, the sets and are now known to be in the same isomorphism class in , and isomorphism classes are determined by cardinalities, so and have the same cardinality — the same number of elements.

Now, this would be just a curiosity if that’s all there was to it, but it goes deeper still. Remember that the natural numbers aren’t just a set. There’s a lot of extra structure there: is a commutative ordered rig. We have an addition and a multiplication of natural numbers, which satisfy a number of algebraic properties. We have a concept of which numbers are bigger than other numbers, which plays nicely with the addition and the multiplication. All of this structure lifts up to .

We can see that if and only if there is a monomorphism (one-to-one function) from to .

The category of finite sets has finite products and coproducts. The product is the regular Cartesian product of and — the set of pairs with and . The coproduct is the disjoint union of and — the set containing all elements in both sets, but counting a copy of an element in as different from a copy of “the same” element in . If we write for the cardinality of , we can verify that , and that . That is, coproducts categorify the addition of cardinal numbers, while products categorify their multiplication.

The initial and terminal objects of are the set with no elements and a set with a single element, respectively. Note that even though the terminal object is only specified up to isomorphism, we’re just going to identify any sets that are isomorphic when we decategorify so they all become the cardinal . The empty set, of course, becomes the cardinal .

We know that for all numbers . In this says that for all finite sets . We can verify this identity using the universal property of the product: has the identity function to and the (unique) function to the terminal object . Given any other set with a function and the unique function , we can just use as the unique function required by the product. Thus satisfies the universal property of , and so must be in that isomorphism class. We can dualize this argument to show that . This shows that we can categorify the additive and multiplicative identities.

The same sorts of arguments can be used to verify all the other basic properties of the natural numbers:

• Addition and multiplication are associative: and .
• Addition and multiplication are commutative: and .
• Multiplication distributes over addition: .
• Addition and multiplication preserve order: if then and .

Try to at least write down the categorified statements of each of these properties. If you’re up for it, prove them using similar techniques to those used to prove the identity properties above. If you’re really up for a challenge, show that all the isomorphisms you’re writing down are natural.

In studying algebraic gadgets as sets with extra structure — and especially in using them to attack other problems — we write down a lot of equations when “really” we just have equivalences. Categorification seeks to replace these equations by isomorphisms. Sets become categories. Functions between sets become functors between categories. Equations between functions become natural isomorphisms between functors. Extra structures on sets become extra structures on categories.

Of course it immediately gets more complicated than that. Down in set-land equations are equations are equations, but in category-land we can run into trouble. We have to pick the natural isomorphisms to categorify our equations “coherently” so that as we string them together we don’t end up in any contradictions. And then immediately we’ll want to take whatever we get and categorify that, which will lead to even more convoluted constructions in general…

However, there is hope, and that hope is why we categorify in the first place. There is usually some way of looking at a structure that makes it perfectly clear how to categorify it, and there’s in a sense in which this perspective is the way the structure “should” be viewed. As Urs Schreiber said, “One knows one is getting to the heart of the matter when the definitions in terms of which one conceives the objects under consideration categorify effortlessly.” I rephrase this as, “when you really understand a mathematical concept, its categorification should be readily apparent”, which then becomes the directive:

If you want to understand something, try to categorify it!