Start a new discussion

Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

Site Tag Cloud

Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.

• CommentRowNumber1.
• CommentAuthorUrs
• CommentTimeJun 23rd 2018
• (edited Jun 23rd 2018)

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?

• CommentRowNumber2.
• CommentAuthorTodd_Trimble
• CommentTimeJun 23rd 2018

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.

• CommentRowNumber3.
• CommentAuthorUrs
• CommentTimeJun 23rd 2018

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.”

• CommentRowNumber4.
• CommentAuthorTodd_Trimble
• CommentTimeJun 23rd 2018
• (edited Jun 23rd 2018)

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.

• CommentRowNumber5.
• CommentAuthorTodd_Trimble
• CommentTimeJun 24th 2018
• (edited Jun 24th 2018)

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:

Gentle explanation

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 $C = Set$ and $S$ is small, an important general principle is that the category of $C$-valued presheaves on $S$ and natural transformations between them is the free cocompletion of $S$.

=–

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 $Set^{A^{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:

+– {: .un_theorem}

Theorem

Given any cocomplete category $B$, and any functor $F : A \to B$, there is a cocontinuous functor $\widehat{F} : \hat{A} \to B$ making this triangle commute up to natural isomorphism:

$\array{ A &\stackrel{F}{\to}& B \\ \downarrow^Y & \nearrow_{\widehat{F}} \\ \widehat{A} }$

Moreover, $\widehat{F}$ is unique up to natural isomorphism.

=–

Our job is to understand how to construct this $\widehat{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

$G : A \to \widehat{B}$

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

$\widehat{G} : \widehat{A} \to \widehat{B}$

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

Exercise. Given a cocontinuous functor $\widehat{A} \to \widehat{B}$, explain how to get a functor $A \to \widehat{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 \widehat{B}$ to a cocontinuous functor $\widehat{A} \to \widehat{B}$ and then precomposing with $Y$ to get a functor $A \to \widehat{B}$ gets you back where you started—at least up to natural isomorphism.

Mike Stay: Well, given any functor $F:A \to \widehat{B}$, you get from the Theorem a cocontinuous functor $\widehat{F}:\widehat{A} \to \widehat{B}$ such that $\widehat{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 $\widehat{A} \to \widehat{B}$ to a functor $A \to \widehat{B}$ and then using the Theorem to turn that back into a cocontinuous functor $\widehat{A} \to \widehat{B}$ gets you back where you started—at least up to natural isomorphism.

Mike Stay: Call our given functor $\widehat{F}: \widehat{A} \to \widehat{B}$. Precompose with $Y$ to get $\widehat{F} \circ Y: A \to \widehat{B}$. Then the theorem gives us a cocontinuous functor $G: \widehat{A} \to \widehat{B}$ such that $G \circ Y$ is the best approximation to $\widehat{F} \circ Y$. But this is $\widehat{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 $\widehat{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: \widehat{A} \to \widehat{B}$. Precompose with $Y$ to get $G \circ Y: A \to \widehat{B}$. Then go back using the Theorem, obtaining a cocontinuous functor $\widehat{G}: \widehat{A} \to \widehat{B}$ such that $\widehat{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 $\widehat{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 \widehat{G} \circ Y \Rightarrow G \cong \widehat{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 \widetilde{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 $\widetilde{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:

$\array{ A &\stackrel{F}{\to}& B \\ \downarrow^y & \nearrow_{\tilde{F}} \\ \tilde{A} }$

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, $\widehat{A}$ is vastly larger than $A$: it’s the category $\Set$. So, the Yoneda embedding $Y : A \to \widetilde{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 $\widehat{F} : \widehat{A} \to B$ making this triangle commute:

$\array{ A &\stackrel{F}{\to}& B \\ \downarrow^Y & \nearrow_{\widehat{F}} \\ \widehat{A} }$

But this is okay: we don’t want a unique functor $\widehat{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 $\widehat{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 : \widehat{A} \to \widehat{B}$ to a functor $G \circ Y : A \to \widehat{B}$ and then using the Theorem to turn that back into a cocontinuous functor $\widehat{G}: \widehat{A} \to \widehat{B}$ gets you back where you started—at least up to natural isomorphism.

Proof - By the Theorem, $\widehat{G}$ satisfies $G \circ Y \cong \widehat{G} \circ Y$. We wish to show $G \cong \widehat{G}$. We’re assuming $G$ preserves colimits, and the Theorem says that $\widehat{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?

When we say $\widehat{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:

$\array{ A &\stackrel{F}{\to}& B \\ \downarrow^y & \nearrow_{\tilde{F}} \\ \tilde{A} }$

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

$x = \sum a_i$

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

$\tilde{F}(x) = \tilde{F} (\sum a_i) = \sum \tilde{F}(a_i) = \sum F(a_i)$

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 $\widehat{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.

• CommentRowNumber6.
• CommentAuthorUrs
• CommentTimeJun 24th 2018

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?

• CommentRowNumber7.
• CommentAuthorUrs
• CommentTimeJun 24th 2018
• (edited Jun 24th 2018)

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.”

• CommentRowNumber8.
• CommentAuthorTodd_Trimble
• CommentTimeJun 24th 2018

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.)

• CommentRowNumber9.
• CommentAuthorUrs
• CommentTimeJun 24th 2018

inserted statement and proof: here

1. Added reference to Day-Lack paper about free cocompletions of large categories.

Anonymous

• CommentRowNumber11.
• CommentAuthorvarkor
• CommentTimeJan 8th 2020

Added a reference to Fiore, Gambino, Hyland and Winskel’s paper Relative pseudomonads, Kleisli bicategories, and substitution monoidal structures showing that the free cocompletion (of a small category) construction is a relative pseudomonad.

• CommentRowNumber12.
• CommentAuthorJohn Baez
• CommentTimeFeb 2nd 2020

I clarified some size issues.

2. Would it be correct to describe $Set^{C^\mathrm{op}}$, where we don’t restrict to only the small presheaves, as the ’free totalization’ of $C$?

• CommentRowNumber14.
• CommentAuthorMike Shulman
• CommentTimeJun 17th 2020

If $C$ isn’t small, I don’t think $Set^{C^{op}}$ is total – it isn’t even locally small.

• CommentRowNumber15.
• CommentAuthorRichard Williamson
• CommentTimeJun 18th 2020
• (edited Jun 18th 2020)

Suppose that we have universes $\mathbb{U} \subset \mathbb{V}$, and suppose that $Set$ is $\mathbb{U}-\mathsf{Set}$. If $C$ is locally small, then $\mathsf{Set}^{C^{op}}$, which is a $\mathbb{V}$-category and not necessarily a $\mathbb{U}$-category, is still I think the free co-completion of $C$, it is just that it does not (necessarily) exist in the category of $\mathbb{U}$-categories. The essential point is that the representable functors $Hom_{C}(-, c)$ still land in $\mathsf{Set}$.

If $C$ is not locally small, then $\mathsf{Set}^{C^{op}}$ is not the free co-completion of $C$. One would need to work with $\mathbb{V}-\mathsf{Set}$ instead. Again, the essential point is that the representable functors no longer (necessarily) land in $\mathsf{Set}$. However, I think that $\mathsf{Set}^{C^op}$ still has a universal property, which expresses that all colimits of ’small’ objects of $C$ (by which I mean ones whose representable functor lands in $\mathsf{Set}$) are freely added. If $C$ 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 $\mathbb{U}$-category, I mean that the Hom sets live in $\mathbb{U}$.]

• CommentRowNumber16.
• CommentAuthorMike Shulman
• CommentTimeJun 19th 2020

No, $\mathbb{U}Set^{C^{op}}$ is not the free $\mathbb{U}$-cocompletion of $C$ if $C$ is not $\mathbb{U}$-small. It’s true that it suffices for $C$ to be locally $\mathbb{U}$-small for its representable functors to lie in $\mathbb{U}Set^{C^{op}}$, but the other important fact in making a presheaf category a free $\mathbb{U}$-cocompletion is that every presheaf is a $\mathbb{U}$-small colimit of representables, and that’s not true for $\mathbb{U}Set^{C^{op}}$. It is true that $\mathbb{U}Set^{C^{op}}$ contains the free $\mathbb{U}$-cocompletion of $C$, namely the category of presheaves that are $\mathbb{U}$-small colimits of representables, a.k.a. small presheaves.

• CommentRowNumber17.
• CommentAuthorRichard Williamson
• CommentTimeJun 19th 2020
• (edited Jun 19th 2020)

Thanks for the reply, Mike! What I meant is that it is the free co-completion for $\mathbb{V}$-small colimits (which to me is the natural notion as soon as $C$ is not small). To get the free co-completion for only $\mathbb{U}$-small colimits, yes, one has to restrict to small presheaves. Do you then agree?

(Where here by $\mathbb{U}$-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 $\mathbb{U}$-small.)

• CommentRowNumber18.
• CommentAuthorMike Shulman
• CommentTimeJun 19th 2020

The free cocompletion for $\mathbb{V}$-small colimits is $\mathbb{V}Set^{C^{op}}$, not $\mathbb{U}Set^{C^{op}}$. The latter doesn’t even have all $\mathbb{V}$-small colimits.

• CommentRowNumber19.
• CommentAuthorRichard Williamson
• CommentTimeJun 20th 2020
• (edited Jun 20th 2020)

Good to clarify this: the point I am making is that $\mathbb{U}-\mathsf{Set}^{C^{op}}$ has the following properties when $C$ is locally small.

1) The Yoneda embedding of $C$ lands in $\mathbb{U}-\mathsf{Set}^{C^{op}}$.

2) Every presheaf in $\mathbb{U}-\mathsf{Set}^{C^{op}}$ is a $\mathbb{V}$-small (not necessarily $\mathbb{U}$-small) colimit of presheaves of the form $Hom_C(-,c)$ for some object $c$ of $C$, i.e. of presheaves living in the image of the Yoneda embedding.

We can compare this to when $C$ is small, in which case it is enough with $\mathbb{U}$-small instead of $\mathbb{V}$-small colimits in 2); and we can compare this to when $C$ is large and not locally small, in which case we have to modify both 1) and 2) to work only with ’small’ objects of $C$, i.e. ones whose corresponding representable functor lives in $\mathbb{U}-\mathsf{Set}^{C^{op}}$, 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 $\mathbb{U}$-small colimits, i.e. that it is $\mathbb{U}$-co-complete and ’every object is a $\mathbb{U}$-small colimit of objects of $C$’ (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 $\mathbb{U}$-co-complete and ’every object is a $\mathbb{V}$-small colimit of objects of $C$’. Finally, the ’large but not locally small case’ is universal with the property that it is $\mathbb{U}$-co-complete and has a full subcategory consisting of $\mathbb{V}$-small colimits of $\mathbb{U}$-small objects of $C$.

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 $\mathbb{U}$-colimits. In #17, my terminology was, in haste, confusingly expressed I now see, but ’free co-completion for $\mathbb{V}$-small colimits’ was meant to refer to the fact that one can get any presheaf by use of $\mathbb{V}$-small colimits of objects of $C$, in the sense discussed here; not that $\mathbb{U}-\mathsf{Set}^{C^{op}}$ has all $\mathbb{V}$-small colimits, the intention was still to speak of landing in a $\mathbb{U}$-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 $\mathbb{V}$-small colimits by working with $\mathbb{V}-\mathsf{Set}$ instead of $\mathbb{U}-\mathsf{Set}$, but this universal property is less precise than the above ones when it comes to $\mathbb{U}$-small colimits.

• CommentRowNumber20.
• CommentAuthorMike Shulman
• CommentTimeJun 20th 2020

It’s not obviously false to me that $\mathbb{U}Set^{C^{op}}$ has that universal property when $C$ 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?

• CommentRowNumber21.
• CommentAuthorRichard Williamson
• CommentTimeJun 21st 2020
• (edited Jun 21st 2020)

I will write down more details later, but I think the proof is essentially the same as the usual one that $\mathbb{U}-\mathsf{Set}^{C^{op}}$ is a free $\mathbb{U}$-co-completion. The only thing that could go wrong is if the canonical way of expressing a presheaf as a $\mathbb{V}$-colimit of representable functors (namely, for a presheaf $F$, as the colimit of the functor $y/F \rightarrow C \rightarrow \mathbb{U}-\mathsf{Set}^{C^{op}}$, where the first functor is canonical (part of the structure of a comma category), and the second is the Yoneda embedding $y$) could be done in two non-naturally isomorphic ways, and if that were the case, then that would also be true in $\mathbb{V}-\mathsf{Set}^{C^{op}}$, and the latter would not be the free $\mathbb{V}$-co-completion of $C$. To see that it is indeed not possible is a straightforward application of the universal property of a comma category as a 2-limit.

• CommentRowNumber22.
• CommentAuthorMike Shulman
• CommentTimeJun 21st 2020

I can think of lots of other things that could go wrong, so I await your proof.

• CommentRowNumber23.
• CommentAuthorHurkyl
• CommentTimeJun 21st 2020
• (edited Jun 21st 2020)

The $\mathbb{U}$-cocompletion of any category $C$ already has the property that every object is a $\mathbb{V}$-small colimit of objects from $\mathbb{V}$.

Say that an object is ’locally $\mathbb{U}$-small’ if the presheaf it represents takes values in $\mathbb{U}$-small sets.

I think, maybe, that the property you’re trying to state is being universal for something like “having all $\mathbb{V}$-small colimits that would produce a locally $\mathbb{U}$-small object”, although I’m not entirely sure how to formulate “would produce a locally $\mathbb{U}$-small object” in some fashion that isn’t something tautological involving colimit-preserving maps out of $\mathbb{U}Set^C$.

I would also have mild skepticism that $\mathbb{U}Set^C$ is actually a co completion. E.g. if there is a functor $F : C \to D$ where $D$ is locally small and every object is a $\mathbb{V}$-small colimit of objects in the image of $F$, it’s not obvious that, if a colimit preserving map $\mathbb{U}Set^C \to D$ extending $F$ exists, that it must be essentially surjective.

• CommentRowNumber24.
• CommentAuthorRichard Williamson
• CommentTimeJun 22nd 2020
• (edited Jun 22nd 2020)

Here goes with a proof. Throughout, let $C$ be a locally small category, and let $P(C)$ be $\mathbb{U}-\mathsf{Set}^{C^{op}}$. First, a few facts, which are completely standard.

Fact 1. Let $X$ be a presheaf in $P(C)$. Then $X$ is the colimit of the functor $y / X \rightarrow C \rightarrow P(C)$, which I’ll denote by $f_X$, where $y / X \rightarrow C$ is the canonical functor which is part of the structure of $y / X$ as a comma category, and where $y : C \rightarrow P(C)$ is the Yoneda embedding. That $X$ is a co-cone for $f_X$ is immediate, and that it is a colimit uses the Yoneda lemma and the universal property of $y/X$.

Fact 2. Let $X$ be a presheaf in $P(C)$. If $X$ is a colimit of the functor $f_Y$ for some other presheaf $Y$ as well, then the structural functor $y/Y \rightarrow C$ factors (on the nose, not only naturally isomorphically) through the structural functor $y / X \rightarrow C$. This is an immediate consequence of the universal property of $y / X$.

Fact 3. Let $r: X \rightarrow Y$ be an arrow in $P(C)$. Then there is an arrow $f_r : y / X \rightarrow y / Y$ such that $colim(f_Y)$ whiskered with $f_r$ is $r$, viewing $colim(f_Y)$ as a natural transformation $f_Y \rightarrow (y / Y \rightarrow 1 \rightarrow P(C))$, where the first functor in the target is canonical, and the second is $Y$. This is an immediate consequence of the universal property of $y / Y$.

Fact 4. Let $G: A \rightarrow P(C)$ be any functor whose colimit exists, where the sets of objects and arrows of $A$ are both $\mathbb{V}$-small. Then the colimit of $G$ can be expressed as colimit of a diagram factoring through $C$. This is an immediate consequence of Fact 1 and Fact 3: just view $F(a)$ as the colimit of $f_{F(a)}$ for every object $a$ of $A$.

Let us introduce the following terminology.

Definition. Let $F : C \rightarrow D$ be a functor. An object of $D$ is a $\mathbb{V}$-colimit of objects of $C$ with respect to $F$ if it can be obtained as a colimit of the diagram $F \circ G : A \rightarrow C \rightarrow D$ for some functor $G: A \rightarrow C$, where $A$ is a category whose sets of objects and arrows are both $\mathbb{V}$-small.

I claim the following.

Proposition. Let $F: C \rightarrow D$ be a functor such that every object of $D$ can be obtained as a $\mathbb{V}$-colimit of objects of $C$ with respect to $F$. Then there is a unique up to natural isomorphism functor $U: P(C) \rightarrow D$ such that $U \circ y$ is naturally isomorphic to $F$, and such that $U$ preserves $\mathbb{V}$-colimits.

Proof: For every isomorphism class of objects of $D$, pick a representative of of it. For every presheaf $X$ in $P(C)$, define $U(X)$ to be the picked out representative of the isomorphism class of the colimit of the diagram $y / X \rightarrow C \rightarrow D$, where the first arrow is as in Fact 1, and where the second arrow is $F$. This colimit exists by our hypothesis on $D$ since the sets of objects and arrows of $y / X$ are both $\mathbb{V}$-small.

Given an arrow $r: X \rightarrow Y$ of $P(C)$, using Fact 3, we define $U(f)$ to be the whiskering of $U(X)$ and $F(f_r)$.

That $U$ is well-defined is an immediate consequence of Fact 2. That $U$ is a functor is obvious (using the universal property of $y / X$ as in Fact 3). That $U$ preserves all $\mathbb{V}$-colimits is an immediate consequence of Fact 4. That $U$ 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 $\mathbb{V}$-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 $\mathbb{U}$-co-completeness in the universal property as well; the proof goes through unchanged: that the universal functor preserves $\mathbb{U}$-colimits obviously follows from the fact that it preserves $\mathbb{V}$-colimits.

• CommentRowNumber25.
• CommentAuthorRichard Williamson
• CommentTimeJun 22nd 2020
• (edited Jun 22nd 2020)

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 $\mathbb{U}$-cocompletion of any category $C$ already has the property that every object is a $\mathbb{V}$-small colimit of objects from $\mathbb{V}$.

The point is that $\mathbb{U}-\mathsf{Set}^{C^{op}}$ is not the $\mathbb{U}$-co-completion of $C$. The latter is the full subcategory on $\mathbb{U}$-small presheaves, i.e. presheaves which are ’locally $\mathbb{U}$-small’ in your terminology.

I think, maybe, that the property you’re trying to state is being universal for something like “having all $\mathbb{V}$-small colimits that would produce a locally $\mathbb{U}$-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 $\mathbb{U}Set^C$ is actually a co completion.

As above, it is not a co-completion in the usual sense, either in the $\mathbb{U}$-sense or the $\mathbb{V}$-sense. The point is to capture a slightly different sense in which it is a co-completion, which is kind of ’between the two’.

• CommentRowNumber26.
• CommentAuthorHurkyl
• CommentTimeJun 22nd 2020
• (edited Jun 22nd 2020)

Here’s a counterexample to your proposition: take $D = C$ and $F : C \to D$ be the identity functor.

Every object of $D$ is a $\mathbb{V}$-colimit of objects of $C$ with respect to $F$, so your proposition would imply $F$ has an extension to a colimit preserving functor $P(C) \to C$ for any locally small category $C$. But this clearly doesn’t hold; e.g. it would imply every locally small category has all $\mathbb{U}$-small colimits. (as well as any $\mathbb{V}$-small colimits that exist in $P(C)$)

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 $D$. I do fully expect that $C \to P(C)$ is universal amongst functors $F : C \to D$ for which $D$ admits all $\mathbb{V}$-colimits of objects of $C$ with respect to $F$ that $P(C)$ does. (but it is not obvious to me there is a simpler formulation of that property)

• CommentRowNumber27.
• CommentAuthorMike Shulman
• CommentTimeJun 22nd 2020

It’s a standard fact that any full subcategory $D$ of a presheaf category $Set^{C^{op}}$ is a free cocompletion of $C$ with respect to colimits weighted by the presheaves that lie in $D$. The proof is just the same as the usual proof that the full presheaf category is a free cocompletion. Specializing this to $\mathbb{U}Set^{C^{op}} \subseteq \mathbb{V}Set^{C^{op}}$, I think this becomes essentially

$C \to P(C)$ is universal amongst functors $F : C \to D$ for which $D$ admits all $\mathbb{V}$-colimits of objects of $C$ with respect to $F$ that $P(C)$ does.

Note that whether or not every object of $D$ is such a colimit is irrelevant. Moreover, that the relevant colimits are not in general $\mathbb{U}$-small, so in this required hypothesis it does not suffice for $D$ to be $\mathbb{U}$-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 $\mathbb{U}$-co-complete and ’every object is a $\mathbb{V}$-small colimit of objects of $C$’.

• CommentRowNumber28.
• CommentAuthorRichard Williamson
• CommentTimeJun 23rd 2020
• (edited Jun 23rd 2020)

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 $D$ since the sets of objects and arrows of $y/X$ are both $\mathbb{V}$-small.

Indeed, the hypothesis on $D$ only ensures that certain $\mathbb{V}$-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 $D$ has all $\mathbb{V}$-colimits that $P(C)$ has. We can still chuck in $\mathbb{U}$-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 $\mathbb{U}$-co-complete category, is every $\mathbb{V}$-colimit of objects of $C$ uniquely determined by some ’$\mathbb{U}$-approximation’?

To be more precise, because of the universal property of a free $\mathbb{U}$-co-completion, we do get a $\mathbb{U}$-colimit preserving functor from the category of $\mathbb{U}$-small presheaves to $D$. Can we extend it to a functor from $P(C)$ to $D$? 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 $\mathbb{U}$-small presheaves into $P(C)$ admit a left or right adjoint? It seems to me that it might admit a left adjoint, which would be something like the ’best $\mathbb{U}$-small approximation to $X$’ for a presheaf $X$. For example if one covers the set of objects of $C$ by $\mathbb{U}$-small subsets and glues the restrictions of $X$ to these $\mathbb{U}$-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.

• CommentRowNumber29.
• CommentAuthorRichard Williamson
• CommentTimeJun 26th 2020
• (edited Jun 26th 2020)

Here is a line of thought, similar to the some of the ideas suggested in #28.

Take some category $D$ such that every object $d$ is a $\mathbb{V}$-colimit of objects of $C$. Now, it seems to me that we can canonically express such a colimit as the $\mathbb{V}$-colimit of restrictions of $d$ to $\mathbb{U}$-small full subcategories of the source of the functor of which $d$ is a colimit.

Then one can ask in general whether any $\mathbb{V}$-colimit of objects of $C$ in $D$ must be a $\mathbb{V}$-colimit of objects of $C$ in $D$ by a diagram out of the category of inclusions of $\mathbb{U}$-small full subcategories of $C$ to $C$, and whether $D$ 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 $C$ has every colimit of diagrams of restrictions of it to $\mathbb{U}$-small full subcategories, then the universal property ’$\mathbb{U}$-co-complete and every object is a $\mathbb{V}$-colimit of objects of $C$’ would hold I think under some size assumption on $D$ which says that its set of objects is at least as large as that of $C$ (and maybe this size assumption could be removed).

• CommentRowNumber30.
• CommentAuthorJoshua Meyers
• CommentTimeJul 18th 2021

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 $\widetilde F(\mathbf{X}) \coloneqq \int^{c \in \mathcal{C}} F(c) \cdot \mathbf{X}(c)$ preserve all colimits? Maybe this would be obvious if I knew more about coends.

• CommentRowNumber31.
• CommentAuthorUrs
• CommentTimeOct 12th 2021

• CommentRowNumber32.
• CommentAuthorUrs
• CommentTimeOct 12th 2021

Am seeing the question in #30 only now:

The coend is just a particular colimit. So it follows since colimits commute with colimits.

• Please log in or leave your comment as a "guest post". If commenting as a "guest", please include your name in the message as a courtesy. Note: only certain categories allow guest posts.
• To produce a hyperlink to an nLab entry, simply put double square brackets around its name, e.g. [[category]]. To use (La)TeX mathematics in your post, make sure Markdown+Itex is selected below and put your mathematics between dollar signs as usual. Only a subset of the usual TeX math commands are accepted: see here for a list.

• (Help)