# What is the Grothendieck construction like?

This is my best attempt at an intuitive introduction to the Grothendieck construction. I’ll give you the definition, but not before warming up to the idea. I’ll start with the earliest conceptual ancestor I could come up with: addition.

What am I going to tell you about addition that you don’t already know? Nothing. I’m just going to frame it in a way that lends itself to the story I’m trying to tell.

What is addition? You take some numbers, a, b, and you make up a new number, called a+b. You could take a bunch of numbers $a_1, \dots, a_n$ and make up a new number by repetition of the two-number version, call it $a_1 + \dots + a_n$. Taking a bunch of numbers $a_1, \dots, a_n$ is the same thing as a function $\{1, \dots, n\} \to \mathbb N$.

Let k be a natural number. A partition of k is a list of numbers $a_1, \dots, a_n$ that add up to k. I’ll skip the rigor for this example… its pretty clear that lists of natural numbers and partitions of natural numbers are basically the same thing. The connection is you just add up the numbers in the list, and then call the list a partition of the sum.

So, yeah… this stuff is pretty trivial at this level. But that’s always how it goes, right? Well, it’s not completely trivial: there is no closed form for the number of partitions of an natural number.

### Multisets, Disjoint Union

I can’t transition to the next step up better than Baez and Dolan did in their paper Categorification:

Long ago, when shepherds wanted to see if two herds of sheep were isomorphic, they would look for an explicit isomorphism. In other words, they would line up both herds and try to match each sheep in one herd with a sheep in the other. But one day, along came a shepherd who invented decategorification. She realized one could take each herd and ‘count’ it, setting up an isomorphism between it and some set of ‘numbers’, which were nonsense words like ‘one, two, three, . . . ’ specially designed for this purpose. By comparing the resulting numbers, she could show that two herds were isomorphic without explicitly establishing an isomorphism! In short, by decategorifying the category of finite sets, the set of natural numbers was invented.

The categorification of adding natural numbers is taking the disjoint union of sets. You can take a pair of set, A, B, and take their disjoint union, which we write as A+B to emphasize the analogy. We could take a bunch of sets $A_1, \dots$ like we did with numbers, and take their disjoint union too $\sum A_i$. Taking a bunch of sets $A_1, \dots, A_n$ is same thing as a functor $A : \{1, \dots, n\} \to \mathsf{Set}$, where we’re thinking of the set {1, …, n} as a category with only identity morphisms.

Definition: A multiset is a set X and a functor $f: X \to \mathsf{Set}$. A multifunction between two multisets (X,f) and (Y,g) is a function $\phi : X \to Y$ and a natural transformation as below. Let MSet denote the category of multisets and multifunctions.

If you like the word “presheaf”, a multiset is a presheaf on a discrete category. Note that naturality of $\alpha$ is trivial since X is discrete. Thus you get one of these by gathering any old collection of functions that fit the types.

In simple terms, a multiset is a family of sets $\{f_x\}_{x \in X}$, and a multi function $(\phi, \alpha) : \{f_x\}_{x \in X} \to \{g_y\}_{y \in Y}$ is a function between the indexing sets $\phi : X \to Y$, and a family of functions $\{\alpha_x : f_x \to g_{\phi(x)}\}_{x \in X}$. These multisets don’t just have multiple copies of an element sitting together, it’s like there’s an address system built in that tells you where each copy lives, so you can distinguish between them. Maybe I risk running this analogy into the ground, but its like each x in X gives a town in a county, and you can have multiple people named Joe living in the same county, but at most one per town!

A multifunction has to use this address system. The $\phi$ part assigns each town in (X,f) to a town in (Y,g), and then $\alpha_x$ assigns each person in town $f_x$ to a person in the corresponding town $g_{\phi(x)}$… Maybe this analogy is getting a little weird…

If we take the disjoint union of the sets in a multiset (X,f), we lose some of the information. We lose the distinction between the different sets. What we get is just a set $A = \sum f_x$ with cardinality equal to the sum of the cardinalities. There’s another way you could record this information though. Define a function $A \to X$ which sends each element to the index of the set it originally comes from. Then the preimage of an element x is precisely the set $f_x$. In the towns and counties analogy, this is record of which town each person in the county lives in. It’s easy to see this really just a different way of recording the exact same data as a multiset. What we’re really talking about now is the arrow category of the category of sets. This has functions for the objects, and commutative squares of functions as the morphisms.

Theorem: MSet is equivalent to the arrow category of Set.

I told you how to turn a multiset into a function. If $(\phi, \alpha)$ is a multifunction as above, I get a commutative square like this:

where $\widetilde{\alpha}$ is a function you get by combining all the $\alpha_x$‘s in an obvious way. You can get this from universal property of the coproduct, but I’ll let you figure that out. The fact that this commutes just comes directly from the fact that $\alpha_x$ is a function from $f_x$ to $g_{\phi(x)}$.

I’ll just describe the inverse of this functor and move on. Given an object of the arrow category of Set, i.e. a function $f : A \to X$, we can define a functor $X \to \mathsf{Set}$ by sending an element x in X to $f^{-1}(x)$. That’s sufficient to define a functor since X is a discrete category. I’ll abuse notation and call this functor $f^{-1} : X \to \mathsf{Set}$. Given a morphism in the arrow category of Set, i.e. a commutative square:

we can define a multifunction like this:

where $\widetilde{\phi_1}_x : f^{-1}(x) \to g^{-1}(\phi_2(x))$ is given by restricting $\phi_1$ to $f^{-1}(x)$. We can corestrict to that codomain by commutativity of the square.

### Indexed Categories, Grothendieck construction

An easy naive way to categorify something is to replace all the sets in it with categories. In the last section, we considered multisets as functors $X \to \mathsf{Set}$ where X is some set. So the obvious thing to try out if we want to go up another level is functors $F : X \to \mathsf{Cat}$ where X is a category. Mostly because of some motivating examples I’ll explain later, we actually want to consider contravariant functors, i.e. $F : X^{op} \to \mathsf{Cat}$. Described more simply, we have an indexing category, X, and for each object x in X, we have a category $F_x$, and for each morphism $f: x \to y$ in X, we get a functor $Ff : F_y \to F_x$. It’s reasonable then that these things are called indexed categories.

So now our towns have streets, and our county has highways between the towns!

To a degree, this setup is fine. There is a naivete to it, but the story works out mostly the same as the real deal. I’ll describe the real deal in the next paragraph, but it involves 2-category theory. If you aren’t comfortable with that stuff, feel free to skim or skip the next paragraph and continue reading.

The naivete of this attempt is that we should bump categories in the multisets stuff to 2-categories. In multisets, X was a set, and we bumped it up to a category really just because the collection of sets naturally wants to be a category. We could have just as well have said that a multiset was a function $X \to ob(\mathsf{Set})$, if you don’t mind that one of those isn’t a set. In the same way, the collection of categories naturally wants to be a 2-category, so we should bump the category X up to a 2-category and consider the corresponding type of thing that can go $X^{op} \to \mathsf{Cat}$. A slight snag here is that we actually have enough room now to have multiple option of things that could be considered as naturally fitting into this situation. I’ll just assert that the right thing to pick is a pseudofunctor, which is like a 2-functor, but only associative up to isomorphism.

In the last section, we transformed multisets into an equivalent form of data by taking the disjoint union of all the pieces of a multiset, and remembering the distinction with a function back to the indexing set. Maybe we could do the same thing here? Given an indexed category $F : X^{op} \to \mathsf{Cat}$, we can turn it into a single category by taking the disjoint union of the pieces $\sum F_x$. And we can get a functor $\sum F_x \to X$ by sending everything in $F_x$ to x.

Oops. There’s something clearly missing from this picture. This picture of the county doesn’t contain any info about the highways! How can we retain the information about the highways in the county map, where the only things we can draw are places and streets between them? You can draw in a new street for everywhere you can get between cities that involves taking a highway. Now it’s time for the definition of the Grothendieck construction.

Definition: Given an indexed category $F: X^{op} \to \mathsf{Cat}$, define a category $\int F$ where

• objects are pairs (x, a) where x is an object of X and a is an object of $F_x$
• morphisms are pairs $(f,g) : (x,a) \to (y,b)$ where $f : x \to y$ is a morphism in X, and $g : a \to Ff(b)$ is a morphism in $F_x$
• composition is given by $(f,g) \circ (f',g') = (f \circ f', Ff'(g) \circ g')$

I’m claiming that this will solve our problem of the missing highways. First, notice that the objects of $\int F$ are exactly the disjoint union of the objects of the $F_x$‘s. What about the morphisms? If $f: a \to b$ was a morphism in $\sum F_x$, i.e. a morphism in one of the $F_x$‘s, then it is also in $\int F$, but now its called $(id_x, f) : (x, a) \to (x, b)$. So $\sum F_x$ is sitting inside of $\int F$.

This is essentially keeping track of the information that the highways added to the map, but in this new map where you only have one type of road.

The formula for composition would look a little more complicated if we were doing it for pseudofunctors instead of functors, but the idea is the same. The formula might seem a little goofy, but actually it’s completely natural! I always remember it by drawing out this picture for morphisms $(f',g') : (x,a) \to (y,b)$ and $(f,g) : (y,b) \to (z,c)$:

We are still able to define a functor $\int F \to X$ like this:

where you send an object (x,a) to x, and a morphism (f,g) to f. In fact, this functor has a nice lifting property which makes it a fibration of categories, and we say that $\int F$ is fibred over X. I won’t get into exactly what this lifting property is, but its precisely what is needed to take all the arrows that cross the dotted lines in the picture above, and turn them into a functor between those two subcategories.

Theorem: The 2-category of X-indexed categories is 2-equivalent to the 2-category of categories fibred over X.

I already described one direction of this equivalence (that’s the Grothendieck construction). The inverse is given by sending an object x of X to its fibre, which is basically its preimage subcategory.

### Examples

I plan on writing a sequel to this with some examples I have in mind that I think give a lot of the flavor of what the Grothendieck construction can do.

1. Bruno Gavranović says: