What is your favorite example of categorification?

4$\begingroup$ amazon.com/CategoryFiftyDrawingsEdwardGorey/dp/0764937502 $\endgroup$ – Will Jagy Oct 25 '10 at 21:32

12$\begingroup$ Anybody who wants to make a more enduring contribution to the mathematics community might try to construct a concise article with the title What is a .... Categorification? for the widely distributed AMS Notices. Many of the articles published in that column are far too technical for the general reader, I think, due to the natural selfconsciousness people feel about what the experts will think. But categorification has the great advantage of being readily illustrated by userfriendly examples. (I'd do this myself if I had any expertise at all.) $\endgroup$ – Jim Humphreys Oct 27 '10 at 18:46
There are a bunch; I don't know that I have a favorite. Here's one for now:
The free commutative monoid functor is a categorification of the exponential function.
Edit: I have been asked to explain this, so I will. We'll interpret "commutative monoid" in any cocomplete symmetric monoidal category $C$ where $\otimes$ distributes over colimits (each $X \otimes $ preserves colimits); the simplest way of ensuring that is to assume the category is symmetric monoidal closed.
Then, at the level of formulas, the free commutative monoid is
$$\exp(X) = \sum_{n \geq 0} X^{\otimes n}/\mathbf{n!}$$
where $\mathbf{n!}$ is the categorifier's notation for the symmetric group $S_n$, and we divide out by the canonical action of the $S_n$ on $X^{\otimes n}$.
There is an awful lot more to say about the categorified analogy, but I'll just say one. Using the hypotheses on the symmetric monoidal category $C$, the object $\exp(X)$ carries a commutative monoid structure, and in fact it is the free commutative monoid on the object $X$ (think of the symmetric algebra for the category $C = Vect$, for instance). Like any free functor, the left adjoint $\exp$ preserves colimits, for example coproducts. What is the coproduct of two commutative monoids (in the category of commutative monoid objects)? Their tensor product in $C$! Thus, we arrive at the exponential law
$$\exp(X + Y) \cong \exp(X) \otimes \exp(Y)$$
and this has many applications.

3

5$\begingroup$ And if you do your symmetrizing in a derived way, you get the free infinite loopspace, or $E_\infty$ monoid  stable homotopy instead of homology  spectrum objects instead of abelian group objects  ... $\endgroup$ – Tom Goodwillie Oct 26 '10 at 16:25

$\begingroup$ Thanks Todd for the additional explanation, this example is really nice! Thanks Tom for the additional information! $\endgroup$ – Jan Weidner Oct 26 '10 at 21:34

$\begingroup$ @Todd: What a fantastic example!! Really, this is one of my favorite MO answers so far. $\endgroup$ – Martin Brandenburg Jan 12 '11 at 23:20

$\begingroup$ @Martin: thank you very much! The mathematics is indeed beautiful to contemplate; one of my favorite applications is to the structure of the Lie algebra operad as a categorified logarithm valued in superspaces, via the PBW theorem. I tried to say something about this a long time ago at math.ucr.edu/home/baez/trimble/trimble_lie_operad.pdf , but I'm afraid I didn't do justice to it... $\endgroup$ – Todd Trimble♦ Jan 13 '11 at 0:14
The move from betti numbers to homology groups.
Although this might not fit super tightly with the usual modern examples of "categorification" (in the way that say a monoidal category is a categorification of a monoid), it is probably the first and most important example of a concept being categorified, allowing for notions such as functoriality, naturality, etc. to flourish. [No way for a continuous map between spaces to induce a map between betti numbers! The old days before functoriality!].

3$\begingroup$ Maybe one should consider the categorification of Euler characteristic to homology groups. This is generalized in the theories of Floer homologies of 3manifolds and Khovanov homology, whose Euler characteristics give the Alexander polynomial and Jones polynomial, respectively. $\endgroup$ – Ian Agol Oct 26 '10 at 3:36

1$\begingroup$ This is just about the first example given in the paper "Categorification" by Baez and Dolan, so I'd say it fits in quite well with the modern spirit. An excellent example of structural thinking. $\endgroup$ – Todd Trimble♦ Oct 26 '10 at 13:45
Here's another example: the functor which maps a group to its classifying space is a categorification of taking the reciprocal.
Edit: The idea is that the total space $EG$ of the classifying bundle of $G$ is contractible and a cofibrant replacement of the point $1$ on which $G$ acts freely. Thus, the construction $BG = EG/G$ is taking a stacky quotient $BG = 1//G$.
There is a bit more to this idea than may first appear; let me take a related example (which may appear to have some Eulerian "wishful thinking" in it, but have a little faith here!). One way of taking the reciprocal is to pass to a geometric series, so that one suggestive notation for the free monoid construction
$$\sum_{n \geq 0} X^{\otimes n}$$
(in a suitable monoidal category; see my other comment on categorifying exponentiation) is a categorified reciprocal $1/(1  X)$. We can apply this idea in group cohomology for a group $G$ as follows: think of $\mathbb{Z}$ as being an abelianized point, and consider a standard $G$free resolution of $\mathbb{Z}$ such as the normalized homogeneous bar resolution, which we can think of as an abelianized $EG$. In one way of constructing this bar resolution (see e.g. HiltonStammbach p. 217), the degree $n$ component of $EG$ is
$$\mathbb{Z}G \otimes IG^{\otimes n}$$
where $IG$ is the augmentation ideal, i.e., the kernel of the augmentation map $\varepsilon: \mathbb{Z}G \to \mathbb{Z}$. As a bare module (or seen in degree 0), $IG$ can be seen as an abelianized "$G  1$". However, in the differentialgraded world, it is better to think of it as in degree 1, and this degree 1 shift $\Sigma IG$ can be seen as a categorified "$IG = 1  G$" (this may make more sense in the "superworld"; see for example my old notes on the Lie operad when I was doing some work with Saunders Mac Lane, or consider for example the occurrence of signs in the Euler characteristic). So now the total space of the bar resolution $EG$ is the sum of the degree $n$ components
$$\mathbb{Z}G \otimes \sum_{n \geq 0} (\Sigma IG)^{\otimes n}$$
which is an abelianized categorified form of $g \cdot \sum_{n \geq 0} (1  g)^n$ which is formally $1$ by the geometric series. Very similar types of categorified geometric series constructions occur in Joyal's theory of species (see especially his article on virtual species in Springer LNM 1234), which constructs the Lie operad by categorified constructions [if you read between the lines!], and in the bar resolution for operads as discussed by GinzburgKapranov; I tried to amplify this in my notes on the Lie operad.
Just to put one final gloss on this: consider the Schubert cell decomposition of projective space as a finite geometric series. For a field $k$ we have
$$\mathbb{P}^{n1}(k) = \frac{k^n  1}{k  1} = 1 + k + k^2 + \ldots + k^{n1}$$
(the '$1$' in the numerator is a zero vector, and the denominator is nonzero scalars $k^\ast$). We can pass to a limit and get infinitedimensional projective space. Keeping in mind that degree shifts introduce some sign changes in the geometric series, the infinitedimensional projective space $\mathbb{RP}^\infty$ would be a model of the homotopy quotient $1//\mathbb{R}^* \simeq 1//\mathbb{Z}_2$.

$\begingroup$ Which is most easily seen for finite groups... $\endgroup$ – theHigherGeometer Oct 26 '10 at 2:44

2

$\begingroup$ I will at my next available opportunity... $\endgroup$ – Todd Trimble♦ Oct 26 '10 at 11:46
The classical BGG resolution as a categorification of the Weyl character formula.

$\begingroup$ That's pretty cool! How do you deduce the Weyl character formula from the BGG resolution? $\endgroup$ – David MJC Oct 26 '10 at 8:11

$\begingroup$ The BGG resolution gives you a resolution of the simple module in terms of direct sums of Verma modules. The EulerPoincaré principle applied to the resolution, together with the formula for the character of the Verma module, gives you the Weyl character formula. (This is all from memory: I have some notes in my office and I can check tomorrow.) $\endgroup$ – José FigueroaO'Farrill Oct 27 '10 at 0:10

$\begingroup$ I would prefer to say, of the Kostant multiplicity formula, which is not the same as the Weyl character formula; they are Fourier transforms of one another. In particular there is a manifestly Weylinvariant way to state the Weyl character formula, $Tr(t_{V_\lambda}) = \sum\limits_{w\in W} w \cdot \frac{t^\lambda}{\prod_{\beta\in \Delta_} (1t^\beta)}$, but not the Kostant multiplicity formula. $\endgroup$ – Allen Knutson Nov 30 '15 at 3:18
The Monster Vertex Algebra (aka the Moonshine Module) categorifies Klein's $j$invariant, in the sense that it is a graded vector space whose graded dimension is the $q$expansion of $j744$. More generally, vertex operator algebras often categorify modular functions and (quasi)modular forms. This has something to do with invariance properties of torus partition functions.
The Monster Lie Algebra categorifies the KoikeNortonZagier $j$function product identity, in the sense that the WeylKacBorcherds denominator formula of the Lie algebra is precisely this identity. More generally, physicists seem to use constructions with words like "BPS states" and "Dbranes" in a way that categorifies automorphic forms on higher rank orthogonal groups (but I don't how it works).

1$\begingroup$ That's a great example, even for those who act like they don't like categories and "categorification". $\endgroup$ – Todd Trimble♦ Oct 26 '10 at 11:48
Grassmannian varieties as categorifying (q)binomial coefficients.
I like one of the simplest and most well known examples: the category of finite sets and bijections functions (see below for comments) categorifies the natural numbers. Or rather it undecategorifies the decategorification that led to much of mathematics in the first place. That makes it pretty special, even if it is rather basic compared with other examples.

9$\begingroup$ Isn't it more natural to take all functions as morphisms? The resulting category has initial objects, terminal objects, finite products, finite coproducts, and an exponential, which categorify 0, 1, multiplication, addition, and exponentiation respectively. $\endgroup$ – Qiaochu Yuan Oct 26 '10 at 16:11

1$\begingroup$ Quite right  that was a thinko on my part: I have most recently been interested in groupoidification, although the broader (and older) categorification was the first appeal to me. However this is a fortuitous illustration of an important point, which is that categorification, like quantization, is an art, not a functor, and what is "most natural" may depend on the context! If a set is viewed as a vector space with a canonical basis indexed by that set (or the dual of a vector space with such a canonical basis) then its groupoidification is a powerful idea in combinatorics! $\endgroup$ – David MJC Oct 27 '10 at 21:39
A small example, but I think it's nice. The generating function $C(t) = \sum_{n \ge 0} \frac{1}{n+1} {2n \choose n} t^{2n}$ of the Catalan numbers is defined by the identity $C(t) = 1 + t^2 C(t)^2$. So one might try to find a "Catalan object" in some category satisfying an isomorphism generalizing this identity. One can take the corresponding combinatorial species in the sense of Joyal, but another choice is to take the invariant subalgebra of the tensor algebra of the defining representation of $\text{SU}(2)$!
Here's an example I learned from Todd Trimble. Recall that the degree $k$ part of the exterior algebra on a vector space $V$ of dimension $n$ has dimension ${n \choose k}$, and similarly the degree $k$ part of the symmetric algebra has dimension ${n+k1 \choose k} = \left( {n \choose k} \right)$. So one can think of these constructions as categorifying binomial coefficients. More precisely, the exterior algebra categorifies its Hilbert series $(1 + t)^n$, and the symmetric algebra categorifies its Hilbert series $\frac{1}{(1  t)^n}$.
But there's more! The duality between the Hilbert series above manifests itself in the identity $\left( {n \choose k} \right) = (1)^k {n \choose k}$, which categorifies to the following statement: "the exterior algebra is the symmetric algebra of a purely odd supervector space." So isomorphisms in the category of supervector spaces categorify identities involving negative binomial coefficients.

1$\begingroup$ Yes, the degree 1 shift in the superworld can be seen as taking a negative, as I remark in my recent edit on the classifying space as reciprocal. $\endgroup$ – Todd Trimble♦ Oct 26 '10 at 15:55

$\begingroup$ Qiaochu, could you add this over on my question here: mathoverflow.net/questions/22750/… ? It sounds quite relevant. What are the power series (if there are any natural ones) that have the other pieces of the twelvefold way as their coefficients? $\endgroup$ – Zev Chonoles Jan 5 '11 at 19:31

$\begingroup$ @Zev: I don't think there's much more to say beyond what's in Stanley's answer. I also don't really think the twelvefold way is the right way to look at the vector space side of things; quantum mechanics seems to me a much better source of motivation, and it is also relevant to this supervector space stuff. I discuss this briefly at the end of my most recent blog post: qchu.wordpress.com/2011/01/02/… $\endgroup$ – Qiaochu Yuan Jan 5 '11 at 20:16
The plethystic monoidal product, or the substitution product of Joyal species, as a categorification of functional composition.
The empty category is a categorification of the empty set :))
The sphere spectrum as categorification of the integers, as remarked in a comment of Thomas Kragh below his answer here, and which I believe is due to Joyal.
Hm, that's a lot of answers from me. Should I stop now, or keep going?

3$\begingroup$ No, keep going! Your answers are great, especially 1/g ! $\endgroup$ – Jan Weidner Oct 26 '10 at 21:55
I don't know if I have a favourite either, but here's another one:
crossed modules in $Grp$ are strict 2groups aka group objects in $Cat$ aka category objects in $Grp$.
Of course, my favorite example is the $2$category of $2$tangles (defined below) is a categorification of the category of tangles. The category of tangles is a monoidal category with objects that correspond to the nonnegative integers, morphisms are generated by $$, $\cup$, $\cap$, $X$ and $\bar{X}$. In this $1$category, the Reidemeister moves (and zigzag and $\psi$move) are identities.
In the $2$category of $2$tangles, the $2$morphisms are generated by $\{ \} \leftrightarrow O$ (birth or death), $ \ \leftrightarrow \stackrel{\cup}{\cap}$ (saddle), and the aforementioned five Reidemeister moves (I, II, III, zigzag, and $\psi$). These are subject to the full set of (35 or so) movie moves. The $2$category of $2$tangles is a braided monoidal $2$category with duals. In fact, it is the free braided monoidal $2$category with duals on one selfdual object generator (Baez and Langford).
Okay then, here's another. 2Hilbert spaces as a categorification of Hilbert spaces, and the categorified GramSchmidt process (which I first learned from James Dolan).
This may be used to derive a $\mathbb{Z}$linear basis for the representation ring of $S_n$ that consists of permutation representations, hence a combinatorial alternative to the basis consisting of irreducible representations. The reference above sketches how this works in the case $Rep(S_4)$.
The canonical example in my mind is:
Sets ~> vector spaces ~> linear categories
This is not so trivial  it is relevant to the topic of extended TQFTs.
The category of groupoids as a categorification of the ring of rational numbers. See this MO question and this ncategory cafe post.

$\begingroup$ Relevant to this is . arXiv:1207.6404 "Groupoids and Faa di Bruno formulae for Green functions in bialgebras of trees" Imma GalvezCarrillo, Joachim Kock, Andrew Tonks $\endgroup$ – Ronnie Brown Sep 11 '15 at 21:13
Is it perverse to just quote the original inception by Crane?
An obvious nice collection would be the paper with Yetter on examples of Categorification.
However, I actually like another Paper of Yetter's better in this direction; categorical linear algebra.
Also, Rosenberg's Noncommutative spectrum is a categorification: pdflink. Not in the strict sense, but "morally". That would be undoubtedly my favorite.

1$\begingroup$ But what is Rosenberg's reconstruction theorem (morally) a categorification of? $\endgroup$ – Todd Trimble♦ Oct 27 '10 at 0:30

$\begingroup$ I am saying the spectrum is the categorification of the spectrum in the classical case. By considering the main object of study Rmod(corresponding to QCsheaves on a scheme) we make the transition from sets to abelian categories. We replaces our spaces with 'spaces' which are simply categories. In this sense, it is a categorification. $\endgroup$ – B. Bischof Oct 27 '10 at 2:50

$\begingroup$ The proof in this old paper is incomplete (which was first noticed by Gabber). $\endgroup$ – Martin Brandenburg Jan 12 '11 at 23:27
In my limited experience of categories, I liked Quillen's notion of homotopy fibre (his paper Higher Algebraic KTheory I) for a functor between categories modelling the homotopy fibre of any map.

1$\begingroup$ Hmmm... I don't think I know quite what you mean here. Quillen's Theorem B says that when all the categorical fibers are homotopy equivalent to one another under base change, then they do indeed all model the homotopy fiber. But if they're not all equivalent, then Theorem B tells you nothing. In general I think it's a very hard (and unsolved) problem to find a category whose classifying space is the homotopy fiber of a functor
$C\to D$
. On the other hand, the dual problem of modeling the homotopy colimit of a diagram of categories was solved by Thomason in his thesis. $\endgroup$ – Dan Ramras Oct 26 '10 at 0:54