nLab
free cocompletion

Contents

Contents

Idea

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

A slightly more precise version of this statement is that the Yoneda embedding

Y:CPSh(C) Y : C \hookrightarrow PSh(C)

is the free cocompletion of CC.

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

Technical details

The rough statement is that the Yoneda embedding

y S:SSet S opy_S: S \to Set^{S^{op}}

of a small category SS into the category Set S opSet^{S^{op}} of presheaves on SS is universal among functors from SS into cocomplete categories. Technically, this should be understood in an appropriate 2-categorical sense: given a functor F:SDF: S \to D where DD is (small-)cocomplete, there exists a unique (up to isomorphism) cocontinuous extension

F^:Set S opD,\hat{F}: Set^{S^{op}} \to D,

called the Yoneda extension, meaning that F^y SF\hat{F} y_S \cong F and F^\hat{F} preserves small colimits.

Put slightly differently: let CocompCocomp denote the 2-category of cocomplete categories, cocontinuous functors, and natural transformations between them. Then for cocomplete DD, the Yoneda embedding yS:SSet S opy S: S \to Set^{S^{op}} induces by restriction a functor

res ySD:Cocomp(Set S op,D)Cat(S,D)res_{y S} D: Cocomp(Set^{S^{op}}, D) \to Cat(S, D)

that is an equivalence for each DD, one that is 2-natural in DD. In fact we show that the Yoneda extension FF^F \mapsto \hat{F} gives a functor ext ySD:Cat(S,D)Cocomp(Set S op,D)ext_{y S}D: Cat(S, D) \to Cocomp(Set^{S^{op}}, D) that is a left adjoint to res ySDres_{y S}D, giving a 2-natural adjoint equivalence.

As a first step, we construct the desired extension F^\hat{F} as a left adjoint to the functor

DSet S op:dhom D(F,d).D \to Set^{S^{op}}: d \mapsto \hom_D(F-, d).

Being a left adjoint, F^\hat{F} is cocontinuous.

An explicit formula for the left adjoint is given by the weighted colimit, coend, or tensor product of functors formula

F^(X)=X SF= s:SX(s)F(s)\hat{F}(X) = X \otimes_S F = \int^{s: S} X(s) \cdot F(s)

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

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

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

Proofs

Proposition

For 𝒞\mathcal{C} a small category, its Yoneda embedding 𝒞y[𝒞 op,Set]\mathcal{C} \overset{y}{\hookrightarrow} [\mathcal{C}^{op}, Set] exhibits the category of presheaves [𝒞 op,Set][\mathcal{C}^{op}, Set] as the free co-completion of 𝒞\mathcal{C}, in that it is a universal morphism (as in this Def. but “up to natural isomorphism”) into a cocomplete category, in that:

  1. for 𝒟\mathcal{D} any cocomplete category category;

  2. for F:𝒞𝒟F \;\colon\; \mathcal{C} \longrightarrow \mathcal{D} any functor;

there is a functor F˜:[𝒞 op,Set]𝒟\widetilde F \;\colon\; [\mathcal{C}^{op}, Set] \longrightarrow \mathcal{D}, unique up to natural isomorphism, such that

  1. F˜\widetilde F preserves all colimits,

  2. F˜\widetilde F extends FF through the Yoneda embedding, in that the following diagram commutes, up to natural isomorphism:

𝒞 y F [𝒞 op,Set] F˜ 𝒟 \array{ && \mathcal{C} \\ & {}^{y}\swarrow &\swArrow& \searrow^{\mathrlap{F}} \\ \mathrlap{ \!\!\!\!\!\!\!\!\!\!\!\!\! [\mathcal{C}^{op}, Set] } && \underset{ \widetilde F }{\longrightarrow} && \mathcal{D} }
Proof

The last condition says that F˜\widetilde F is fixed on representable presheaves, up to isomorphism, by

(1)F˜(y(c))F(c) \widetilde F( y(c) ) \simeq F(c)

and in fact naturally so:

(2)c 1 F˜(y(c 1)) F(c 1) f F(y(f)) F(f) c 2 F˜(y(c 2)) F(c 2) \array{ c_1&& \widetilde F( y(c_1) ) &\simeq& F(c_1) \\ {}^{\mathllap{f}}\big\downarrow && {}^{\mathllap{ F(y(f)) }}\big\downarrow && \big\downarrow^{\mathrlap{ F(f) }} \\ c_2 && \widetilde F (y(c_2)) &\simeq& F(c_2) }

But the co-Yoneda lemma expresses every presheaf X[𝒞 op,Set]\mathbf{X} \in [\mathcal{C}^{op}, Set] as a colimit of representable presheaves

X c𝒞y(c)X(c). \mathbf{X} \;\simeq\; \int^{c \in \mathcal{C}} y(c) \cdot \mathbf{X}(c) \,.

Since F˜\tilde F is required to preserve any colimit and hence these particular colimits, (1) implies that F˜\widetilde F is fixed to act, up to isomorphism, as

F˜(X) =F˜( c𝒞y(c)X(c)) c𝒞F(c)X(c)𝒟 \begin{aligned} \widetilde F(\mathbf{X}) & = \widetilde F \left( \int^{c \in \mathcal{C}} y(c) \cdot \mathbf{X}(c) \right) & \coloneqq \int^{c \in \mathcal{C}} F(c) \cdot \mathbf{X}(c) \;\;\;\;\in \mathcal{D} \end{aligned}

(where the colimit (a coend) on the right is computed in 𝒟\mathcal{D}!).

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 CatCat and CocompleteCatCocompleteCat, but rather, a pseudoadjunction between the 2-categories CatCat and CocompleteCatCocompleteCat.

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

U:CocompleteCatCat U: CocompleteCat \to Cat

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

F:CatCocompleteCat F: Cat \to CocompleteCat
F:CC^=Set C op F: C \mapsto \widehat{C} = Set^{C^{op}}

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

hom CocompleteCat(FC,D)hom Cat(C,UD) hom_{CocompleteCat} (F C, D) \simeq hom_{Cat} (C, U D)

for every CCatC \in Cat, DCocompleteCatD \in CocompleteCat. And fiinally, it would also be saying that this equivalence is pseudonatural as a function of CC and DD.

If we have a pseudonatural equivalence of categories

hom CocompleteCat(FC,D)hom Cat(C,UD) hom_{CocompleteCat} (F C, D) \simeq hom_{Cat} (C, U D)

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

F:CatCocompleteCat F : Cat \to CocompleteCat

we need CocompleteCatCocompleteCat to be the 2-category of large categories. But if CocompleteCatCocompleteCat is the 2-category of large categories then to define

U:CocompleteCatCat U: CocompleteCat \to Cat

we need CatCat 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

UF:CatCat U F : Cat \to Cat

we’re stuck: the ‘CatCat’ 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 C^\widehat{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.

References

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

Last revised on July 6, 2018 at 14:45:53. See the history of this page for a list of all contributions to it.