Want to take part in these discussions? Sign in if you have an account, or apply for one below
Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.
I was looking again at this entry, while preparing my category theory notes elsewhere, and I find that this entry is really bad.
With the co-Yoneda lemma in hand (every presheaf is a colimit of representables, and that is dealt with well on its page), the statement of free cocompletion fits as an easy clear Idea into 2 lines, and as a full proof in maybe 10.
The entry should just say that!
Currently the section “technical details” starts out right, but somehow forgets along the way what it means to write a proof in mathematics.
On the other hand, the section “Gentle introduction” seems to be beating about the bush forever. Does this really help newbies?
Looks like it was from a much earlier era of the nLab, when people were experimenting around. In particular, I agree with you about “Gentle introduction”. I don’t think “Technical details” necessarily “forgot” anything; apparently it was just written to make more precise what was said in the Idea section.
I don’t think “Technical details” necessarily “forgot” anything;
Not content, but communication. This is not how one will lay out the proof to somebody who isn’t already full expert in these matters. This is not how a proof in a textbook would be organized. A proof should go: “We have this, we need to show that, so we recall this, and observe that, and finally conclude.”
Yeah, I know what you’re saying. But rather than say that [someone] forgot what it means to prove something, which is a little insulting, I believe it’s more a case of the usual way that nLab articles get constructed: not all in one shot.
Anyway, I guess you want someone to add a proof. I’ll volunteer, but maybe within a few hours, not a few minutes.
A start is being made on cleaning up this entry, starting with removing the experimental conversation between John Baez and Mike Stay.
I’m exporting some of the conversation here, for archival purposes:
This section is a slightly new sort of experiment. Here John Baez would like to explain this remark to Mike Stay:
+– {: .standout}
In the case where and is small, an important general principle is that the category of -valued presheaves on and natural transformations between them is the free cocompletion of .
=–
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 Yoneda lemma gives an embedding – the Yoneda embedding.
The result says:
+– {: .un_theorem}
Given any cocomplete category , and any functor , there is a cocontinuous functor making this triangle commute up to natural isomorphism:
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.
Hi Todd,
I am not asking you to put in the proof. I could copy over the proof from my notes. I am checking if we agree on the state of the page and which pieces deserve to be scratched and redone.
In the piece that is left after your deletion (thanks!) should we promote the subscripts on the integrals to superscripts, not to give the impression that these coends are ends?
Removed the sentence with “try to prove the bloody theorem”.
Removed “Maybe you don’t actually know fact 3, but it’s true.” and replaced it by: “The key fact in item 3 is also called the co-Yoneda lemma. For more see there, or see below.”
Hi Urs,
Yes, I was going to delete that stuff too, but I wasn’t confident that I had enough character space to archive it all in a single comment. Thanks for taking care of it.
I think we pretty much agree. If you’d like to put your proofs in the (sub)section that’s titled Proofs, then I’d be happy to take a look later and we can harmonize the entry. (We don’t have to have a section called Proofs, but that would be a good placeholder for now, since I’d rather not scrap Technical Details for the moment.)
Would it be correct to describe , where we don’t restrict to only the small presheaves, as the ’free totalization’ of ?
If isn’t small, I don’t think is total – it isn’t even locally small.
Suppose that we have universes , and suppose that is . If is locally small, then , which is a -category and not necessarily a -category, is still I think the free co-completion of , it is just that it does not (necessarily) exist in the category of -categories. The essential point is that the representable functors still land in .
If is not locally small, then is not the free co-completion of . One would need to work with instead. Again, the essential point is that the representable functors no longer (necessarily) land in . However, I think that still has a universal property, which expresses that all colimits of ’small’ objects of (by which I mean ones whose representable functor lands in ) are freely added. If has a terminal object, for instance, the terminal object will be ’small’ in this sense.
This is all off the top of my head, apologies if I have overlooked something.
[Edit: by -category, I mean that the Hom sets live in .]
No, is not the free -cocompletion of if is not -small. It’s true that it suffices for to be locally -small for its representable functors to lie in , but the other important fact in making a presheaf category a free -cocompletion is that every presheaf is a -small colimit of representables, and that’s not true for . It is true that contains the free -cocompletion of , namely the category of presheaves that are -small colimits of representables, a.k.a. small presheaves.
Thanks for the reply, Mike! What I meant is that it is the free co-completion for -small colimits (which to me is the natural notion as soon as is not small). To get the free co-completion for only -small colimits, yes, one has to restrict to small presheaves. Do you then agree?
(Where here by -small colimit I mean that the sets of objects and arrows in the source category of the functor which we have taken the colimit of are both -small.)
The free cocompletion for -small colimits is , not . The latter doesn’t even have all -small colimits.
Good to clarify this: the point I am making is that has the following properties when is locally small.
1) The Yoneda embedding of lands in .
2) Every presheaf in is a -small (not necessarily -small) colimit of presheaves of the form for some object of , i.e. of presheaves living in the image of the Yoneda embedding.
We can compare this to when is small, in which case it is enough with -small instead of -small colimits in 2); and we can compare this to when is large and not locally small, in which case we have to modify both 1) and 2) to work only with ’small’ objects of , i.e. ones whose corresponding representable functor lives in , and we have to restrict the presheaves considered in 2).
I suggest that all three cases have universal properties. The ’small’ case is the usual universal property for free co-completion with respect to -small colimits, i.e. that it is -co-complete and ’every object is a -small colimit of objects of ’ (I am using this slightly unusual formulation for ease of comparison with what I will subsequently write). The ’locally small’ case is universal with the property that it is -co-complete and ’every object is a -small colimit of objects of ’. Finally, the ’large but not locally small case’ is universal with the property that it is -co-complete and has a full subcategory consisting of -small colimits of -small objects of .
This universal property of in the locally small case is what I meant by the free co-completion here, and what I think is the most accurate universal property one can obtain if one is referring to free co-completion of a locally small category with respect to -colimits. In #17, my terminology was, in haste, confusingly expressed I now see, but ’free co-completion for -small colimits’ was meant to refer to the fact that one can get any presheaf by use of -small colimits of objects of , in the sense discussed here; not that has all -small colimits, the intention was still to speak of landing in a -co-complete category.
In both the locally small and large cases, one can of course get free co-completion in the usual sense for all -small colimits by working with instead of , but this universal property is less precise than the above ones when it comes to -small colimits.
It’s not obviously false to me that has that universal property when is locally small, but it’s certainly not obviously true to me either, and my gut instinct is that it’s probably not true. Can you prove it?
I will write down more details later, but I think the proof is essentially the same as the usual one that is a free -co-completion. The only thing that could go wrong is if the canonical way of expressing a presheaf as a -colimit of representable functors (namely, for a presheaf , as the colimit of the functor , where the first functor is canonical (part of the structure of a comma category), and the second is the Yoneda embedding ) could be done in two non-naturally isomorphic ways, and if that were the case, then that would also be true in , and the latter would not be the free -co-completion of . To see that it is indeed not possible is a straightforward application of the universal property of a comma category as a 2-limit.
I can think of lots of other things that could go wrong, so I await your proof.
The -cocompletion of any category already has the property that every object is a -small colimit of objects from .
Say that an object is ’locally -small’ if the presheaf it represents takes values in -small sets.
I think, maybe, that the property you’re trying to state is being universal for something like “having all -small colimits that would produce a locally -small object”, although I’m not entirely sure how to formulate “would produce a locally -small object” in some fashion that isn’t something tautological involving colimit-preserving maps out of .
I would also have mild skepticism that is actually a co completion. E.g. if there is a functor where is locally small and every object is a -small colimit of objects in the image of , it’s not obvious that, if a colimit preserving map extending exists, that it must be essentially surjective.
Here goes with a proof. Throughout, let be a locally small category, and let be . First, a few facts, which are completely standard.
Fact 1. Let be a presheaf in . Then is the colimit of the functor , which I’ll denote by , where is the canonical functor which is part of the structure of as a comma category, and where is the Yoneda embedding. That is a co-cone for is immediate, and that it is a colimit uses the Yoneda lemma and the universal property of .
Fact 2. Let be a presheaf in . If is a colimit of the functor for some other presheaf as well, then the structural functor factors (on the nose, not only naturally isomorphically) through the structural functor . This is an immediate consequence of the universal property of .
Fact 3. Let be an arrow in . Then there is an arrow such that whiskered with is , viewing as a natural transformation , where the first functor in the target is canonical, and the second is . This is an immediate consequence of the universal property of .
Fact 4. Let be any functor whose colimit exists, where the sets of objects and arrows of are both -small. Then the colimit of can be expressed as colimit of a diagram factoring through . This is an immediate consequence of Fact 1 and Fact 3: just view as the colimit of for every object of .
Let us introduce the following terminology.
Definition. Let be a functor. An object of is a -colimit of objects of with respect to if it can be obtained as a colimit of the diagram for some functor , where is a category whose sets of objects and arrows are both -small.
I claim the following.
Proposition. Let be a functor such that every object of can be obtained as a -colimit of objects of with respect to . Then there is a unique up to natural isomorphism functor such that is naturally isomorphic to , and such that preserves -colimits.
Proof: For every isomorphism class of objects of , pick a representative of of it. For every presheaf in , define to be the picked out representative of the isomorphism class of the colimit of the diagram , where the first arrow is as in Fact 1, and where the second arrow is . This colimit exists by our hypothesis on since the sets of objects and arrows of are both -small.
Given an arrow of , using Fact 3, we define to be the whiskering of and .
That is well-defined is an immediate consequence of Fact 2. That is a functor is obvious (using the universal property of as in Fact 3). That preserves all -colimits is an immediate consequence of Fact 4. That is unique up to natural isomorphism with the requisite properties is immediate (the up to isomorphism bit coming from our picking of representatives of isomorphism classes).
This proof is the same, except for the need to work with -colimits, as the usual one (or one of the usual ones) that presheaf categories are free co-completions in the usual sense.
One can chuck in -co-completeness in the universal property as well; the proof goes through unchanged: that the universal functor preserves -colimits obviously follows from the fact that it preserves -colimits.
Re #23: I think there is some confusion here :-). I think Mike already understood correctly the statement I had in mind, but I’ll respond in case it helps you or others.
The -cocompletion of any category already has the property that every object is a -small colimit of objects from .
The point is that is not the -co-completion of . The latter is the full subcategory on -small presheaves, i.e. presheaves which are ’locally -small’ in your terminology.
I think, maybe, that the property you’re trying to state is being universal for something like “having all -small colimits that would produce a locally -small object”
As above, I think you have slightly misunderstood the point here :-) The way I stated the universal property in #19 was essentially precise; it is now written a little more formally in #24.
I would also have mild skepticism that is actually a co completion.
As above, it is not a co-completion in the usual sense, either in the -sense or the -sense. The point is to capture a slightly different sense in which it is a co-completion, which is kind of ’between the two’.
Here’s a counterexample to your proposition: take and be the identity functor.
Every object of is a -colimit of objects of with respect to , so your proposition would imply has an extension to a colimit preserving functor for any locally small category . But this clearly doesn’t hold; e.g. it would imply every locally small category has all -small colimits. (as well as any -small colimits that exist in )
This is basically the point I was trying to get at in #23 – you aren’t including a hypothesis that talks about what colimits should exist in . I do fully expect that is universal amongst functors for which admits all -colimits of objects of with respect to that does. (but it is not obvious to me there is a simpler formulation of that property)
It’s a standard fact that any full subcategory of a presheaf category is a free cocompletion of with respect to colimits weighted by the presheaves that lie in . The proof is just the same as the usual proof that the full presheaf category is a free cocompletion. Specializing this to , I think this becomes essentially
is universal amongst functors for which admits all -colimits of objects of with respect to that does.
Note that whether or not every object of is such a colimit is irrelevant. Moreover, that the relevant colimits are not in general -small, so in this required hypothesis it does not suffice for to be -cocomplete. Thus, although the correct statement suggested by Hurkyl is true, it does nothing to justify the original claim from #19:
The ’locally small’ case is universal with the property that it is -co-complete and ’every object is a -small colimit of objects of ’.
Thanks both for the comments! This is more interesting than I originally realised!
First, some less interesting remarks: the following line in my proof was erroneous. My apologies, Hurkyl, for misunderstanding your initial comment.
This colimit exists by our hypothesis on since the sets of objects and arrows of are both -small.
Indeed, the hypothesis on only ensures that certain -colimits exist, and we do not a priori know if they include all those we need. Everything else in the proof is correct I think. As you suggested, Hurkyl, we can correct it by changing the universal property to say that has all -colimits that has. We can still chuck in -co-completeness. However, this is rather unsatisfactory.
Is the original claim true? This actually seems rather interesting. It seems to boil down to the following: in a -co-complete category, is every -colimit of objects of uniquely determined by some ’-approximation’?
To be more precise, because of the universal property of a free -co-completion, we do get a -colimit preserving functor from the category of -small presheaves to . Can we extend it to a functor from to ? This seems an interesting question. It seems possible to me, but I do not yet have a proof.
We could begin by asking the following question, which seems related: does the inclusion functor from the category of -small presheaves into admit a left or right adjoint? It seems to me that it might admit a left adjoint, which would be something like the ’best -small approximation to ’ for a presheaf . For example if one covers the set of objects of by -small subsets and glues the restrictions of to these -small full sub-categories together. I have not carefully thought through whether this works, but am throwing the thought out there in case others have ideas/insight.
I do not have time just now to think carefully through the size restrictions on standard theorems like the nerve-realisation adjunction or the adjoint functor theorem to figure out whether they can be of help here.
Here is a line of thought, similar to the some of the ideas suggested in #28.
Take some category such that every object is a -colimit of objects of . Now, it seems to me that we can canonically express such a colimit as the -colimit of restrictions of to -small full subcategories of the source of the functor of which is a colimit.
Then one can ask in general whether any -colimit of objects of in must be a -colimit of objects of in by a diagram out of the category of inclusions of -small full subcategories of to , and whether has all such colimits. At first I was inclined to think that this was highly unlikely, but on second thoughts I’m not sure.
One can put this in a nicer form in various cases I think. E.g if has every colimit of diagrams of restrictions of it to -small full subcategories, then the universal property ’-co-complete and every object is a -colimit of objects of ’ would hold I think under some size assumption on which says that its set of objects is at least as large as that of (and maybe this size assumption could be removed).
Disclaimer: I have only skimmed the above thread, so apologies if the following is already addressed.
The proof of the main theorem in this page proves uniqueness but seems to stop short of existence. Why does the functor preserve all colimits? Maybe this would be obvious if I knew more about coends.
added cross-links, all previously missing:
Am seeing the question in #30 only now:
The coend is just a particular colimit. So it follows since colimits commute with colimits.
Cross-referenced free strict cocompletion.
1 to 34 of 34