A Small Exercise in Categorification

sdenton4

To celebrate the fact that I’ve finally got latex working on the blog, I’m going to bore you with a post about combinatorics and categories…

As good a picture as any for a post about categorification, right?

After some nice student questions in the Foundations course the other day, David and I were playing around with the number of surjections that exist between finite sets. And somehow this led down the road of writing the number of maps between two finite sets as a sum over the number of pre-image sets. There’s a very nice formula for this, actually. The number of surjections {rm Sur}^n_k from set of n things to a set of k things is given by k!S(n,k), where S(n,k) is the Sterling number of the second kind, which counts the ways of partioning an n-element set into k subsets. (And it’s pretty easy to backwards reason why the number of surjections is this number!) The number of injections {rm Inj}^n_k is the falling factorial, (k)_n=k(k-1)cdots (k-n).

The total number of maps mathbb{Z}_n rightarrow mathbb{Z}_k is well-known (and easy to see) to be n^k. Let’s write |{rm Hom}(n,k)|=n^k, with an eye towards the categorification. But we would like to split these up by number of image elements. To get the total number of maps this way, we can imagine an intermediate i-element set where i is the size of the image of a given map. Then we map onto this i-element set with a surjection, and then to the k-element set with an injection. We thus decompose our arbitary map into a composition of an injection and a surjection. Then it’s tempting to write:
|{rm Hom}(n,k)| = sum_i |{rm Sur}^n_i||{rm Inj}^i_k|,
which even seems to fit the Einstein notation for summation nicely! Unfortunately it’s not quite right: we could, for example, throw in an permutation (ie, an automorphism) of the i-element set to obtain a different realization of the same map; thus, we’re over-counting.  So in fact, we have to divide by i!, or, if you prefer, |{rm Aut}(i)|. So our formula is then:
|{rm Hom}(n,k)| = sum_i frac{|{rm Sur}^n_i||{rm Inj}^i_k|}{|{rm Aut}(i)|} = sum_i S(n,i) (i)_k.
This last equality is actually the form that you’ll find in lots of combinatorics texts, like Stanley’s Enumerative Combinatorics, Volume 1. It’s part of a section called ‘The Twelvefold Way,’ about counting different kinds of functions.

By thinking of all the steps in terms of set maps, though, we actually have a nice general statement that works for lots of different categories. For example, the formula:
|{rm Hom}(G,H)| = sum_Q frac{|{rm Sur}^G_Q||{rm Inj}^Q_K|}{|{rm Aut}(Q)|}
works just fine for finite groups! The groups Q are just all of the quotients of $G$. Additionally, what’s happened is we’ve given a nice description of all of the maps between G and H: they decompose as a surjection followed by an injection. This is pretty much the content of the first isomorphism theorem: The surjection is a quotient map, and the injection is the inclusion homomorphism. We’re allowed to throw in qutomorphisms of the quotient Q without any harm done, but if we want to describe all maps, we should control for those automorphisms in order to avoid over-counting!

So what we’re seeing here is that counting set maps by size of the image is pretty much the same as proving the first isomorphism theorem, which holds for all kinds of different categories…

Fun and games!