The Unapologetic Mathematician

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 $\mathbf{FinSet}$ 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 $\{a,b,c\}$ to the set $\{1,2,3\}$, 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 $\{a,b,c\}$ is the same as the number of elements in $\{1,2,3\}$,” which really means, “there is a bijection between $\{a,b,c\}$ and $\{1,2,3\}$.”

This is an example of decategorification: we take some category — here it’s $\mathbf{FinSet}$ — and break it down to the set of isomorphism classes of its objects — here it’s the set $\mathbb{N}$ 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: $M=\{\mathrm{sheep\ in\ the\ morning}\}$, $S=\{\mathrm{stones\ in\ the\ bag}\}$, and $E=\{\mathrm{sheep\ in\ the\ evening}\}$. When the shepherd puts a stone in the bag for each sheep leaving in the morning he’s setting up an explicit bijection from $M$ to $S$. Then when he takes a stone out for each returning sheep he’s setting up an explicit bijection from $S$ to $E$. We can compose these two bijections to get a bijection from $M$ to $E$. That is, the sets $M$ and $E$ are now known to be in the same isomorphism class in $\mathbf{FinSet}$, and isomorphism classes are determined by cardinalities, so $M$ and $E$ 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: $\mathbb{N}$ 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 $\mathbf{FinSet}$.

We can see that $|A|\leq|B|$ if and only if there is a monomorphism (one-to-one function) from $A$ to $B$.

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

The initial and terminal objects of $\mathbf{FinSet}$ are the set $\varnothing$ 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 $1$. The empty set, of course, becomes the cardinal ${}0$.

We know that $n\cdot1=n$ for all numbers $n$. In $\mathbf{FinSet}$ this says that $A\times*\cong A$ for all finite sets $A$. We can verify this identity using the universal property of the product: $A$ has the identity function to $A$ and the (unique) function to the terminal object $*$. Given any other set $X$ with a function $f:X\rightarrow A$ and the unique function $X\rightarrow*$, we can just use $f$ as the unique function required by the product. Thus $A$ satisfies the universal property of $A\times*$, and so must be in that isomorphism class. We can dualize this argument to show that $A\coprod\varnothing\cong A$. 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: $(a+b)+c=a+(b+c)$ and $(a\cdot b)\cdot c=a\cdot(b\cdot c)$.
• Addition and multiplication are commutative: $a+b=b+a$ and $a\cdot b=b\cdot a$.
• Multiplication distributes over addition: $a\cdot(b+c)=a\cdot b+a\cdot c$.
• Addition and multiplication preserve order: if $a\leq b$ then $a+c\leq b+c$ and $a\cdot c\leq b\cdot c$.

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!

June 27, 2007 - Posted by | Category theory

1. Meaning, I really need to get about categorifying supersymmetric quantum mechanics. Comment by Blake Stacey | June 28, 2007 | Reply

2. Meaning, I really need to get about categorifying supersymmetric quantum mechanics.

It might sound funny now, but isn’t Gukov attempting to do some toy models of this? Comment by Ben Webster | June 28, 2007 | Reply

3. […] But this all then raises a natural question: we’re looking at microstates (statistical mechanics) and declare examples of them to be “the same” if their macrostates are the same. But we don’t like “the same” — we like “isomorphic. So, is the passage from statistical mechanics to thermodymanics a decategorification? […]

Pingback by First Day in Faro: Random Thoughts « The Unapologetic Mathematician | July 11, 2007 | Reply

4. Over at the Carnival they’re claiming you did a post on “categorization”. Grr. Comment by John Baez | July 18, 2007 | Reply

5. Yes, despite my telling them the right term, it being in the post title, in the URL, and so on…

Honestly, the Carnival has been getting pretty disappointing of late. In the last two weeks I think there’s been one other serious mathematics post other than mine. Then there’s a bunch of little toys and games and math-ed things. They’re useful and all, but I think the mathematicians have generally abandoned it, especially as Alon has less and less to do with the blogosphere. Comment by John Armstrong | July 18, 2007 | Reply

6. Categories and Surreals: Disordered Thoughts

I’ve been going through André Joyal’s category-theoretic construction of the surreal numbers, futzing around to see how restricting the construction to yield only the real numbers affects things. (See my earlier remarks on this and/or Mar…

Trackback by Science After Sunclipse | August 1, 2007 | Reply

7. […] Armstrong wrote a nice little introduction to category theory a few weeks ago, showing how numbers, addition, and subtraction are really just the […]

Pingback by Unmotivated « Rolfe Schmidt | August 15, 2007 | Reply

8. […] if I recall), let’s just consider which representations are isomorphic. That is, let’s decategorify this […]

Pingback by Representations of a Polynomial Algebra « The Unapologetic Mathematician | October 30, 2008 | Reply

9. […] Instead, I’ve been sucked into the vortex of math blogs and in particular this useful post on categorification, from which I learned quite a bit.  I haven’t got much to say about the gist of the post, […]

Pingback by Reading Hume’s Principle Eliminatively? « if-then knots | December 10, 2008 | Reply

10. […] and Philosophy An aspiring philosopher of mathematics got hold of my post on categorification, and it’s leading to (what I find to be) an interesting discussion of how Hume’s […]

Pingback by Math and Philosophy « The Unapologetic Mathematician | December 10, 2008 | Reply

11. “Equations between functions become natural isomorphisms between categories.”

Presumably you mean “natural isomorphisms between functors”? Comment by Tom | December 16, 2008 | Reply

12. You know, you’re right. I’m surprised nobody caught that earlier. Thanks. Comment by John Armstrong | December 16, 2008 | Reply

13. […] me as being worth mentioning, though. John Armstrong at The Unapologetic Mathematician writes about categorification: the process of recasting a mathematical abstraction into the language of category theory, as a […]

Pingback by Carnival of Mathematics « Learning Computation | April 30, 2010 | Reply