Contents

Idea

Passing from a category $C$ to its presheaf category $\mathrm{PSh}(C):=[C^{\mathrm{op}},\mathrm{Set}]$ may be regarded as the operation of “freely adjoining colimits to $C$”.

The precise version of this statement is that the Yoneda embedding

is the free cocompletion of $C$.

The universal property of the Yoneda embedding is expressed in terms of the Yoneda extension of any functor $F:C\to D$ to a category $D$ with colimits.

Technical details

The Yoneda embedding

of a small category $S$ into the category ${\mathrm{Set}}^{S^{\mathrm{op}}}$ of presheaves on $S$ is universal among functors from $S$ into cocomplete categories, in the sense that given a functor $F:S\to D$ where $D$ is cocomplete, there exists a unique (up to isomorphism) cocontinuous extension

called the Yoneda extension, meaning that $\hat{F}{y}_S\cong F$ and $\hat{F}$ preserves small colimits. Indeed, the desired $\hat{F}$ is left adjoint to the functor

An explicit formula for the left adjoint is given by the weighted colimit or coend formula

where $S\cdot d$ is notation for copowering (or tensoring) an object $d$ of $D$ by a set $S$ (in this case, a coproduct of an $S$-indexed set of copies of $D$). This formula recurs frequently throughout this wiki; see also nerve, Day convolution.

This “free cocompletion” property generalizes to enriched category theory. If $V$ is complete, cocomplete, symmetric monoidal closed, and $S$ is a small $V$-enriched category, then the enriched presheaf category $V^{S^{\mathrm{op}}}$ is a free $V$-cocompletion of $S$. The explicit meaning is analogous to the case where $V=\mathrm{Set}$, where all ordinary category concepts are replaced by their $V$-enriched analogues; in particular, the notion of ”$V$-cocontinuous functor” referes to preservation of enriched weighted colimits (not just ordinary conical colimits).

If $C$ is not small, then its free cocompletion still exists, but it is not the category of all presheaves on $C$. Rather, it is the category of small presheaves on $C$, i.e. presheaves that are small colimits of representables.

Gentle explanation

This section is a slightly new sort of experiment. Here John Baez would like to explain this remark to Mike Stay:

The idea is that I’ll write some stuff, then Mike will write some questions, and so on. Other people are welcome to join, but only if they keep it simple. Please: no showing off! In particular, Mike does not yet understand coends or Kan extensions, so part of my job is to explain these, not just use them.

First, let me state the above result precisely.

Given a small category $A$, let $\hat{A}$ be our short name for ${\mathrm{Set}}^{A^{\mathrm{op}}}$, the category of presheaves on $A$ and natural transformations between them.

The Yoneda lemma gives an embedding $Y:A\to \hat{A}$ – the Yoneda embedding.

The result says:

Our job is to understand how to construct this $\hat{F}$.

But before we do that:

Why do we care?

There are many reasons why this theorem is important. Mike Stay needs it to convert between two equivalent descriptions of profunctors from a category $A$ to a category $B$. On the one hand, we can think of them as functors

On the other hand, we can think of them as cocontinuous functors

Getting from $G$ to $\hat{G}$ here is a special case of the above Theorem. Getting from $\hat{G}$ to $G$ is vastly easier, so I’ll leave that as a little exercise:

Exercise. Given a cocontinuous functor $\hat{A}\to \hat{B}$, explain how to get a functor $A\to \hat{B}$.

Mike Stay: Precompose with $Y$.

John Baez: Right. So, going back — the hard part, which is what the Theorem lets us do — is a bit like trying to find an ‘inverse’ to precomposition with $Y$. And that’s exactly what Kan extensions are all about. So the theorem asserts that a certain Kan extension exists.

But don’t worry: I’m only mentioning this to intimidate you… err, I mean: to start getting you used to Kan extensions. They’re ‘best possible approximations to the perhaps impossible task of finding an inverse to precomposition with a functor’. But never mind!

Mike Stay: So the real content of the Theorem is saying that there’s always a “best” one; I can imagine that in other situations, you might have a bunch of inequivalent approximations, none of which is better than all the others, and would need to make an arbitrary choice.

John Baez: Yeah, for starters. However, I must admit: the Theorem actually says a lot more than the existence of a certain Kan extension. A Kan extension would merely ‘do its best’ to make a triangle commute up to natural isomorphism. In this particular case it actually succeeds! But never mind! I’m just trying to sneak certain ideas into your brain, so they’ll quietly take root: I don’t want to actually talk about them yet.

Now, try these exercises:

Exercise. Using the Theorem, show that going from a functor $A\to \hat{B}$ to a cocontinuous functor $\hat{A}\to \hat{B}$ and then precomposing with $Y$ to get a functor $A\to \hat{B}$ gets you back where you started—at least up to natural isomorphism.

Mike Stay: Well, given any functor $F:A\to \hat{B}$, you get from the Theorem a cocontinuous functor $\hat{F}:\hat{A}\to \hat{B}$ such that $\hat{F}\circ Y$ is naturally isomorphic to $F$.

John Baez: Right, so we’re back where we started, at least up to natural isomorphism.

Exercise. Also show that going from a cocontinuous functor $\hat{A}\to \hat{B}$ to a functor $A\to \hat{B}$ and then using the Theorem to turn that back into a cocontinuous functor $\hat{A}\to \hat{B}$ gets you back where you started—at least up to natural isomorphism.

Mike Stay: Call our given functor $\hat{F}:\hat{A}\to \hat{B}$. Precompose with $Y$ to get $\hat{F}\circ Y:A\to \hat{B}$. Then the theorem gives us a cocontinuous functor $G:\hat{A}\to \hat{B}$ such that $G\circ Y$ is the best approximation to $\hat{F}\circ Y$. But this is $\hat{F}$ itself–at least up to natural isomorphism.

John Baez: I don’t think that’s a proof. First, I find the hand-waving about ‘best approximations’ a bit distracting—that’s the kind of talk we use in explaining stuff, not proving stuff. And it’s not good to call the functor we start with $\hat{F}$, since it’s just any cocontinuous functor that someone handed us, not one we got from the Theorem. If we fix these problems, we get something like this:

Start with any cocontinuous functor $G:\hat{A}\to \hat{B}$. Precompose with $Y$ to get $G\circ Y:A\to \hat{B}$. Then go back using the Theorem, obtaining a cocontinuous functor $\hat{G}:\hat{A}\to \hat{B}$ such that $\hat{G}\circ Y$ is naturally isomorphic to $G\circ Y$. We need to show that we got back where we started, up to natural isomorphism. So, we need to show that $\hat{G}$ is natural isomorphic to $G$. What next?

(Hint: don’t be afraid to get stuck and realize that you could get out of being stuck if you knew a certain Lemma which might also be useful for other things we’re talking about below.)

Mike Stay: Well, we need to show that $G\circ Y\cong \hat{G}\circ Y\Rightarrow G\cong \hat{G}$; is $Y$ an epimorphism?

John Baez: That would suffice, but it’s radically overoptimistic.

To see why, consider the second decategorified analogue below, where $y:A\to \tilde{A}$ is the inclusion of a set in the vector space having that set as a basis. Is this $y$ an epimorphism? In other words: is it onto? No! The vector space $\tilde{A}$ is vastly larger than $A$.

What does this mean? It means: it’s not true that given any vector space $B$ and function $F:A\to B$, there is a unique function $\tilde{F}:\tilde{A}\to B$ making this triangle commute:

But this is okay: we don’t want a unique function $\tilde{F}$ making this diagram commute: we want a unique linear function making it commute. And that’s obviously true.

Having gained some intuition from the decategorified analogue, let’s go back to the situation we’re really interested in. If $A$ is the category with one object and one morphism, $\hat{A}$ is vastly larger than $A$: it’s the category $Set$. So, the Yoneda embedding $Y:A\to \tilde{A}$ is far from being onto in any sense.

In particular, it’s not true that given any cocomplete $B$ and functor $F:A\to B$, there is an essentially unique functor $\hat{F}:\hat{A}\to B$ making this triangle commute:

But this is okay: we don’t want a unique functor $\hat{F}$ making this diagram commute: we want a unique cocontinuous functor making it commute.

And this too should be obviously true, once we know what’s going on. What lemma would help?

Mike Stay: Oh! It would help to know this:

Lemma: Every object in $\hat{A}$ is a colimit of objects in the image of $A$.

John Baez: Right. Given that, here’s how we tackle the Exercise:

Exercise. Show that going from a cocontinuous functor $G:\hat{A}\to \hat{B}$ to a functor $G\circ Y:A\to \hat{B}$ and then using the Theorem to turn that back into a cocontinuous functor $\hat{G}:\hat{A}\to \hat{B}$ gets you back where you started—at least up to natural isomorphism.

Proof - By the Theorem, $\hat{G}$ satisfies $G\circ Y\cong \hat{G}\circ Y$. We wish to show $G\cong \hat{G}$. We’re assuming $G$ preserves colimits, and the Theorem says that $\hat{G}$ does too. We know they agree on objects in the image of $Y$, and every object is a colimit of those, by the Lemma, so they agree.

Now for one more exercise:

Exercise. What is the hole in the above proof?

Mike Stay: I don’t know. Something about naturality?

How should we think about this, intuitively?

When we say $\hat{A}$ is the ‘free cocompletion’ of the category $A$, it means we’re freely throwing in colimits (and thus wrecking the old colimits $A$ may have had). Since colimits are generalized ‘sums’, we can consider a decategorified analogue:

Decategorified Theorem. Given any set $A$, let $\tilde{A}$ be the free commutative monoid on $A$, and let $y:A\to \tilde{A}$ be the obvious inclusion. If $B$ is a commutative monoid, given any function $F:A\to B$, there is a monoid homomorphism $\tilde{F}:\tilde{A}\to B$ making this triangle commute:

Proof. The proof here is easy. Elements of $\tilde{A}$ are formal sums of elements of $A$, like

So, $\tilde{F}$ is determined by the fact that it preserves addition and acts like $F$ on guys in $A$:

Lo and behold — now we have a formula for $\tilde{F}$. So, we just need to check some stuff. Check that $\tilde{F}$ is well-defined. Check that it’s a monoid homomorphism. Check that it makes the diagram commute. Check that it’s unique. All this is follow-your-nose stuff.

David Corfield: In the above Decategorified Theorem, shouldn’t you say commutative monoid $A$, and then $\tilde{A}$ is the free commutative monoid on the underlying set of $A$?

John Baez: No! We’re taking a set $A$ and freely throwing in sums to get the commutative monoid $\tilde{A}$. This is like taking a category $A$ and freely throwing in colimits to get the cocomplete category $\hat{A}$. See? There may be other fun things to do when our set was already a commutative monoid, but they’re not relevant to the analogy here.

David Corfield: Oh I see. Though I wonder if prettier category theory would have you talk about the underlying sets of $\tilde{A}$ and $B$, and of commutative monoid morphism.

John Baez: You’re right: in some gold-plated treatment it would be good to carefully distinguish between commutative monoids and their underlying categories, or cocomplete categories and their underlying categories. That would be especially nice if we wanted to see ‘free commutative monoid’ or ‘free cocompletion’ as some sort of monad. But let’s prove the Theorem first and gold-plate it later, in the section below called Free cocompletion as a pseudomonad.

Proving the theorem

Okay, now let’s stop fiddling around and try to prove the bloody Theorem:

There are probably lots of ways to prove it, but let’s take a simple-minded approach that mimics the obvious proof of the Decategorified Theorem. We proved the Decategorified Theorem by finding a formula for the map we needed. So let’s try to write a formula for $\hat{F}$, based on three ideas:

1. Since the triangle commutes, we know what $\hat{F}$ should do to guys in the image of $Y$. Namely:

   $$\hat{F}(Y(x))=F(x)$$\widehat{F}(Y(x)) = F(x)

   (The triangle could just commute up to natural isomorphism, but let’s not worry about that yet — that’s just a nuance.)

2. We know that $\hat{F}$ preserves colimits.

3. We know that every object in $\hat{A}$ is a colimit of guys in the image of $Y$. (Such guys are called representable.)

Maybe you don’t actually know fact 3, but it’s true. If you don’t know why, don’t worry — you’ll soon find out!

These three facts are already enough to determine $\hat{F}$ on objects.

Exercise: Why?

So $\hat{F}$ is well on its way to being unique.

But why does $\hat{F}$ exist? For this it will really be good to have a formula expressing every object in $\hat{A}$ as a colimit of guys in the image of $Y$. As a side-effect this will prove fact 3. But even better: thanks to fact 2, this formula will yield a formula for $\hat{F}$. And a formula is the best way to prove existence.

Mike Stay: Given categories $A,B$ and a functor $F:A\to \hat{B}$, the fact that all objects in $\hat{B}$ can be written as a sum over representables says that

In a similar way, the Yoneda embedding says

That is, the set of morphisms from $-$ to $a$ is the set of morphisms from $-$ to an intermediate object $a\prime$ times the morphisms from $a\prime$ to $a$, where $a\prime$ ranges over all possible objects in $A$.

Doing the same for an arbitrary cocontinuous functor $G:\hat{A}\to \hat{B}$ says

maps to

which simplifies to

by taking $a$ as the midpoint between $-$ and $b$. So $G$ is completely determined (up to isomorphism) by its values on the embedding of $A$.

John Baez: Very good! But let me ask a few questions, starting with this. You say

“Given categories $A,B$ and a functor $F:A\to \hat{B}$, the fact that all objects in $B$ can be written as a sum over representables says that

I feel funny about this, because you say “all objects of $B$ can be written as a sum over representables”, but this doesn’t really make sense. It’s true that “all objects of $\hat{B}$ can be written as a colimit of representables” — is that what you meant? But even if so, how does this fact “say that

And I’d like us to write up a proof of the Theorem, so try to fit what you’ve written into a proof.

Mike Stay. Yes, I was being sloppy when I said “sum”. As for how it’s a colimit, consider two functors $F:C^{\mathrm{op}}\to \mathrm{Set},G:C\to \mathrm{Set}.$ Then

is a colimit: for each $f:c\to c\prime$ in $C$, we get a diagram

and the colimit of all these is the “integral” above.

If I do a “search and replace” on the decategorified proofs, I get this:

”Proof. The proof here is easy. Objects of $\hat{A}$ are colimits of objects of $Y(A)=\mathrm{hom}(-,A)$, like

with some “coefficients” $x(a).$ So, $\hat{F}$ is determined by the fact that it preserves colimits and acts like $F$ on guys in $\mathrm{hom}(-,A)$:

Lo and behold — now we have a formula for $\hat{F}$. So, we just need to check some stuff. Check that $\hat{F}$ is well-defined. Check that it preserves colimits. Check that it makes the diagram commute up to natural isomorphism. Check that it’s unique up to natural isomorphism. All this is follow-your-nose stuff.”

But I bet you want me to actually follow my nose this time.

Free cocompletion as a pseudomonad

David Corfield: So is this ‘free cocompletion’ part of an adjunction between the category of categories and the category of cocomplete categories (modulo size worries?). Or should we think of it as part of a pseudoadjunction between 2-categories? (I would start a page on that, but how are naming conventions going in this area?)

John Baez: Equations between functors tends to hold only up to natural isomorphism. So, your first guess should not be that there’s an adjunction between the categories $\mathrm{Cat}$ and $\mathrm{CocompleteCat}$, but rather, a pseudoadjunction between the 2-categories $\mathrm{Cat}$ and $\mathrm{CocompleteCat}$.

If this were true, what would it mean? It would mean that there’s a forgetful 2-functor:

together with a ‘free cocompletion’ 2-functor, which right now we’ve been calling ‘hat’:

And, it would mean there’s an equivalence of categories

for every $C\in \mathrm{Cat}$, $D\in \mathrm{CocompleteCat}$. And fiinally, it would also be saying that this equivalence is pseudonatural as a function of $C$ and $D$.

If we have a pseudonatural equivalence of categories

instead of a natural isomorphism of sets, then we say we have a ‘pseudoadjunction’ instead of an adjunction. A pseudoadjunction is the right generalization of adjunction when we go to 2-categories; if we were feeling in a modern mood we might just say ‘adjunction’ and expect people to know we meant ‘pseudo’.

Naively, it seems we do have such a pseudoadjunction, at least modulo size issues—which unfortunately is sort of like saying “modulo truth”! The problem is that if Cat is the 2-category of small categories then to define the free cocompletion functor

we need $\mathrm{CocompleteCat}$ to be the 2-category of large categories. But if $\mathrm{CocompleteCat}$ is the 2-category of large categories then to define

we need $\mathrm{Cat}$ to be the 2-category of large categories! So, instead of an honest pseudoadjunction that bounces us back and forth between two 2-categories, the size keeps ratcheting up each time we make a round trip!

In particular, if we try to define a pseudomonad

we’re stuck: the ’$\mathrm{Cat}$’ at right contains larger categories than the one at left.

In their work on species, Fiore, Gambino, Hyland and Winskel had to confront this issue. In one draft of this paper they had a very artful and sophisticated device for dealing with this size problem. In the latest draft they seem to have sidestepped it entirely: you’ll see they discuss the ‘free symmetric monoidal category on a category’ pseudomonad, but never the ‘free cocomplete category on a category’ pseudomonad, even though they do use the $\hat{C}$ construction all over the place. Somehow they’ve managed to avoid the need to consider this construction as a pseudomonad!

In higher category theory

One can ask for the notion of free cocompletion in the wider context of higher category theory.

• for (∞,1)-category theory there is free (∞,1)-cocompletion .

References

This reference might also give helpful clues:

• Daniel Dugger, Sheaves and Homotopy Theory (web, pdf)

A pedagogical explanation of the universal property of the Yoneda embedding is given starting on page 7. On page 8 there’s an explanation with lots of pictures how a presheaf is an “instruction for how to build a colimit”. Then on p. 9 the universal morphism that we are looking for here is identified as the one that “takes the instructions for building a colimit and actually builds it”.

(This text, by the way, contains various other gems. A pity that it is left unfinished.)