Free cocompletions

I’ve just learned a pretty cool presentation of the free cocompletion of a category C I’d like to share here.

Why another cocompletion?

First, yes, we already have a lovely presentation of this free cocompletion in the category C^{\mathrm{op}}\to \mathbf{Set} of presheaves on C. But this one has some weaknesses!

  • A presheaf is a lot of data. In particular we can’t easily specify functors into C^{\mathrm{op}}\to \mathbf{Set} directly on the computer, even if C is finite and we look at finite presheaves, which is why that’s not what we do when programming data migrations. Instead we need some kind of presentation of a presheaf, such as by a diagram D:J\to C.
  • The category of presheaves is only the free cocompletion in the bicategorical sense. There’s abstract nonsense telling you there exists a free cocompletion \hat{C} in the 1-categorical sense, so that you can extend a functor C\to D with D cocomplete uniquely to cocontinuous \hat C\to D, but the abstract nonsense isn’t useful for getting your hands on such a completion.
  • It’s hard to compute colimits in the presheaf category! The issue is basically that coequalizers of sets are, generally, wild, because you have to know how to take the transitive closure of a relation to compute them, and the transitive closure of a relation can be really big relative to the relation itself. It seems like colimits in a free cocompletion ought to be easy to compute, just as the product in a free group is easy to compute.[1]

Desiderate for a free cocompletion

Well, I hope I’ve got you convinced you want something better, because I have it![2]We can define a free cocompletion of C with the following properties:

  • The objects of \hat C are just small diagrams D:J\to C (the thing we were already using to present presheaves in Catlab!)
  • If i:C\to \hat C is the structure map (fully faithful, like Yoneda) making \hat C a free cocompletion, then given any diagram i\circ D:J\to \hat C of “representables”, there’s a colimiting cocone i\circ D\Rightarrow \Delta_D to D. That is, any diagram in C is “its own” colimit when viewed in \hat C, and computing colimits becomes a no-op!
  • If f:C\to C' is a functor into a cocomplete category then there is a unique, like, unique-unique, extension along i given by f_!(D)=\mathrm{colim}(f\circ D). Bam. Easy.

So how do we do this? Basically, being a free cocompletion will mean that \hat C must be equivalent to C^{\mathrm{op}}\to \mathbf{Set} under C, which means that maps between diagrams must be the same as the maps between the presheaves they generate. If you’re familiar with the usual definition of the category of diagrams, you know this won’t work; in general a diagram generates a big huge presheaf and there might be lots of maps of presheaves that aren’t represented on the generating diagrams. What we want is an honest representation of the “stupid” solution that just takes the bijective on object-fully faithful factorization of the functor from diagrams to presheaves.

More honest, but complicated

OK, so, if D:J\to C,E:K\to C, consider a map of the presheaves D and E generate. We’ll view this as a map of discrete fibrations f:\bar J\to \bar K over maps \bar D:\bar J\to C,\bar E:\bar K\to C.[3] This f is uniquely determined by its restriction to J, by generalities about orthogonal factorization systems applied to the so-called “comprehensive” factorization system, so we’d like to describe maps J\to \bar K over C. Well, what’s \bar K? It’s the Grothendieck construction of the presheaf on C you get by left Kan extending the terminal presheaf K^{\mathrm{op}}\to \mathbf{Set} along E^{\mathrm{op}}. By the definition of left Kan extensions, that means the fiber of \bar E:\bar K\to C is given by the colimit of singleton sets, indexed by the comma E^\mathrm{op}\downarrow c\cong c\downarrow E. The colimit of a terminal functor into \mathbf{Set} gives the set of connected components, so in short, the fiber \bar E_c=\pi_0(c\downarrow E), and to choose our morphism J\to \bar K over c is to choose, for each j:J, a connected component of j\downarrow E, functorially in j.

Still honest, but simpler?

What does that mean, though?

It means that we need to choose, for every j, a k_j and a map a_j:D(j)\to E(k_j), such that if m:j\to j' then D(m)a_{j'} and a_j are in the same connected component of j\downarrow E, so there’s a zigzag in K whose image under E fills the gap below:[4]

Two such choices a,b are equivalent if [a_j]=[b_j] in \pi_0(j\downarrow E) for all j. We can compose such choices by composing in C. And that’s it, that’s the cocompletion \hat C!

Are colimits nice now?

The analogue of the Yoneda embedding i:C\to \hat C sends c to its singleton diagram \hat c:1\to C and f:c_1\to c_2 to the morphism \hat f whose sole component is, of course, f. If * is the object of 1, then *\downarrow \hat{c_2} is the discrete category C(c_1,c_2) (equal to its set of connected components) so i is fully faithful.

If D:J\to C then let’s build the canonical cocone \lambda:i\circ D \Rightarrow D. We first need morphisms \lambda_j:\widehat{D(j)}\to D in \hat C for j\in J; we take them to be represented by \mathrm{id}_{D(j)}. Now for the key bit. If m:j\to j' then to be a cocone we have to show \lambda_{j'}\circ \widehat{D(m)}=\lambda_j as morphisms \widehat{D(j)}\to D. These morphisms are represented, respectively, by D(m):D(j)\to D(j') and by \mathrm{id}_{D(j)}. These aren’t equal, and these morphisms are different in the plain diagram category. But they are equal in \pi_0(j\downarrow D), using the short “zigzag” m to fill the gap!

So \lambda forms a cocone, and it’s easy to check that it’s even a colimiting cocone, as well as the strict universal property.

Yes colimits are nice now. Yay.

  1. Something something normal form… ↩︎

  2. Via various people who already knew it, see here. ↩︎

  3. For D to “generate” the discrete fibration \bar D means exactly that D factors through \bar D via a final functor J\to \bar J. ↩︎

  4. Again, for those familiar with the usual diagram category, you see the difference: in there, there would be a single morphism, not an arbitrary zigzag, k_j\to k_{j'}. It turns out this is the heart of the whole difference between the diagram category and the presheaf category! ↩︎