The precise version of this statement is that the Yoneda embedding
is the free cocompletion of .
The Yoneda embedding
of a small category into the category of presheaves on is universal among functors from into cocomplete categories, in the sense that given a functor where is cocomplete, there exists a unique (up to isomorphism) cocontinuous extension
where is notation for copowering (or tensoring) an object of by a set (in this case, a coproduct of an -indexed set of copies of ). This formula recurs frequently throughout this wiki; see also nerve, Day convolution.
This “free cocompletion” property generalizes to enriched category theory. If is complete, cocomplete, symmetric monoidal closed, and is a small -enriched category, then the enriched presheaf category is a free -cocompletion of . The explicit meaning is analogous to the case where , where all ordinary category concepts are replaced by their -enriched analogues; in particular, the notion of “-cocontinuous functor” referes to preservation of enriched weighted colimits (not just ordinary conical colimits).
If is not small, then its free cocompletion still exists, but it is not the category of all presheaves on . Rather, it is the category of small presheaves on , i.e. presheaves that are small colimits of representables.
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 , let be our short name for , the category of presheaves on and natural transformations between them.
The result says:
Moreover, is unique up to natural isomorphism.
Our job is to understand how to construct this .
But before we do that:
There are many reasons why this theorem is important. Mike Stay needs it to convert between two equivalent descriptions of profunctors from a category to a category . 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 to here is a special case of the above Theorem. Getting from to is vastly easier, so I’ll leave that as a little exercise:
Exercise. Given a cocontinuous functor , explain how to get a functor .
Mike Stay: Precompose with .
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 . 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 to a cocontinuous functor and then precomposing with to get a functor gets you back where you started—at least up to natural isomorphism.
Mike Stay: Well, given any functor , you get from the Theorem a cocontinuous functor such that is naturally isomorphic to .
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 to a functor and then using the Theorem to turn that back into a cocontinuous functor gets you back where you started—at least up to natural isomorphism.
Mike Stay: Call our given functor . Precompose with to get . Then the theorem gives us a cocontinuous functor such that is the best approximation to . But this is 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 , 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 . Precompose with to get . Then go back using the Theorem, obtaining a cocontinuous functor such that is naturally isomorphic to . We need to show that we got back where we started, up to natural isomorphism. So, we need to show that is natural isomorphic to . 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 ; is an epimorphism?
John Baez: That would suffice, but it’s radically overoptimistic.
To see why, consider the second decategorified analogue below, where is the inclusion of a set in the vector space having that set as a basis. Is this an epimorphism? In other words: is it onto? No! The vector space is vastly larger than .
What does this mean? It means: it’s not true that given any vector space and function , there is a unique function making this triangle commute:
But this is okay: we don’t want a unique function 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 is the category with one object and one morphism, is vastly larger than : it’s the category . So, the Yoneda embedding is far from being onto in any sense.
In particular, it’s not true that given any cocomplete and functor , there is an essentially unique functor making this triangle commute:
But this is okay: we don’t want a unique functor 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 is a colimit of objects in the image of .
John Baez: Right. Given that, here’s how we tackle the Exercise:
Exercise. Show that going from a cocontinuous functor to a functor and then using the Theorem to turn that back into a cocontinuous functor gets you back where you started—at least up to natural isomorphism.
Proof - By the Theorem, satisfies . We wish to show . We’re assuming preserves colimits, and the Theorem says that does too. We know they agree on objects in the image of , 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?
When we say is the ‘free cocompletion’ of the category , it means we’re freely throwing in colimits (and thus wrecking the old colimits may have had). Since colimits are generalized ‘sums’, we can consider a decategorified analogue:
Decategorified Theorem. Given any set , let be the free commutative monoid on , and let be the obvious inclusion. If is a commutative monoid, given any function , there is a monoid homomorphism making this triangle commute:
Proof. The proof here is easy. Elements of are formal sums of elements of , like
So, is determined by the fact that it preserves addition and acts like on guys in :
Lo and behold — now we have a formula for . So, we just need to check some stuff. Check that 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 , and then is the free commutative monoid on the underlying set of ?
John Baez: No! We’re taking a set and freely throwing in sums to get the commutative monoid . This is like taking a category and freely throwing in colimits to get the cocomplete category . 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 and , 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.
Okay, now let’s stop fiddling around and try to prove the bloody Theorem:
Moreover, is unique up to natural isomorphism.
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 , based on three ideas:
(The triangle could just commute up to natural isomorphism, but let’s not worry about that yet — that’s just a nuance.)
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 on objects.
So is well on its way to being unique.
But why does exist? For this it will really be good to have a formula expressing every object in as a colimit of guys in the image of . As a side-effect this will prove fact 3. But even better: thanks to fact 2, this formula will yield a formula for . And a formula is the best way to prove existence.
Mike Stay: Given categories and a functor , the fact that all objects in 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 is the set of morphisms from to an intermediate object times the morphisms from to , where ranges over all possible objects in .
Doing the same for an arbitrary cocontinuous functor says
which simplifies to
by taking as the midpoint between and . So is completely determined (up to isomorphism) by its values on the embedding of .
John Baez: Very good! But let me ask a few questions, starting with this. You say
“Given categories and a functor , the fact that all objects in can be written as a sum over representables says that
I feel funny about this, because you say “all objects of can be written as a sum over representables”, but this doesn’t really make sense. It’s true that “all objects of 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 Then
is a colimit: for each in , 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 are colimits of objects of , like
with some “coefficients” So, is determined by the fact that it preserves colimits and acts like on guys in :
Lo and behold — now we have a formula for . So, we just need to check some stuff. Check that 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.
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 and , but rather, a pseudoadjunction between the 2-categories and .
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 , . And fiinally, it would also be saying that this equivalence is pseudonatural as a function of and .
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 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 ‘’ 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 construction all over the place. Somehow they’ve managed to avoid the need to consider this construction as a pseudomonad!
One can ask for the notion of free cocompletion in the wider context of higher category theory.
This reference might also give helpful clues:
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.)