nLab free cocompletion

Redirected from "free co-completion".
Contents

Context

Category theory

Limits and colimits

Yoneda lemma

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.

There is also an alternative construction of the free cocomplete category, given by the free strict cocompletion.

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” refers 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;

  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 of large categories

In general, given a locally small (but possibly large) category 𝒜\mathcal{A}, we can define a locally small category of small presheaves on 𝒜\mathcal{A} as the full subcategory of the functor category Fun(𝒜 op,Set)Fun(\mathcal{A}^{\mathrm{op}},\operatorname{Set}) spanned by those functors that are colimits of small diagrams of representables. Equivalently, a small presheaf is a functor F:𝒜 opSetF:\mathcal{A}^{\mathrm{op}} \to \operatorname{Set} such that there exists a functor γ:𝒞𝒜\gamma:\mathcal{C} \to \mathcal{A} with 𝒞\mathcal{C} small and a presheaf F:𝒞 opSetF': \mathcal{C}^{\mathrm{op}}\to \operatorname{Set} such that

F=Lan γF.F=\operatorname{Lan}_{\gamma} F'.

This process of free cocompletion defines a functor LL from the 2-category

CAT=[locallysmallcategories,functors,naturaltransformations] CAT = [locally \; small \; categories, \; functors, \; natural \; transformations ]

to the 2-category

Cocomp=[locallysmallcocompletecategories,cocontinuousfunctors,naturaltransformations] Cocomp = [locally \; small \; cocomplete \; categories, \; cocontinuous \; functors, natural \; transformations ]

where, just to be clear, ‘cocomplete’ means having all small colimits, as usual. Moreover, this functor LL is part of a pseudoadjunction where the right adjoint R:CocompCATR: Cocomp \to CAT assigns each locally small coccomplete category its underlying category, and so on.

In the case where 𝒜 op\mathcal{A}^{\mathrm{op}} is locally presentable, the category of small presheaves on 𝒜\mathcal{A} is equivalent to the category of accessible functors 𝒜 opSet\mathcal{A}^{\mathrm{op}}\to \operatorname{Set}. In this situation, the category of small functors has many nice properties and is often said to be almost a topos. In particular, under this assumption, the category of small presheaves is complete, cocomplete, and Cartesian-closed.

See Day-Lack for more details on all these matters. They handle the more general case of enriched categories.

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

This means there’s a forgetful 2-functor:

R:CocompCAT R: Cocomp \to CAT

together with a ‘free cocompletion’ 2-functor:

L:CATCocomp L: CAT \to Cocomp

And, it mean there’s an equivalence of categories

hom Cocomp(FC,D)hom CAT(C,UD) hom_{Cocomp} (F C, D) \simeq hom_{CAT} (C, U D)

for every CCATC \in CAT, DCocompD \in Cocomp. And finally, it means that this equivalence is pseudonatural as a function of CC and DD.

If we have a pseudonatural equivalence of categories

hom Cocomp(FC,D)hom CAT(C,UD) hom_{Cocomp} (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’.

The details have been worked out by Day-Lack in even more generality: they consider enriched categories. Note that the free cocompletion of a small category CC is the category of all presheaves on CC, but for a more general locally small category it’s just the category of small presheaves.

In their work on species, Fiore, Gambino, Hyland and Winskel confronted the size issues in another way. 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!

Fiore, Gambino, Hyland and Winskel later exhibited the free cocompletion of a small category as a relative pseudomonad from the 2-category Cat of small categories into the 2-category CAT of locally-small categories (via the 2-category COC of locally-small cocomplete categories). See FGHW for more details.

In higher category theory

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

References

On strict free cocompletions:

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

An early paper on free completions:

  • Věra Trnková. Limits in categories and limit-preserving functors, Commentationes Mathematicae Universitatis Carolinae 7.1 (1966): 1-73.

Last revised on June 7, 2024 at 06:34:57. See the history of this page for a list of all contributions to it.