Feeds:
Posts

The free cocompletion I

Let $C$ be a (locally small) category. Recall that any such category naturally admits a Yoneda embedding

$\displaystyle Y : C \ni c \mapsto \text{Hom}(-, c) \in \widehat{C}$

into its presheaf category $\widehat{C} = [C^{op}, \text{Set}]$ (where we use $[C, D]$ to denote the category of functors $C \to D$). The Yoneda lemma asserts in particular that $Y$ is full and faithful, which justifies calling it an embedding.

When $C$ is in addition assumed to be small, the Yoneda embedding has the following elegant universal property.

Theorem: The Yoneda embedding $Y : C \to \widehat{C}$ exhibits $\widehat{C}$ as the free cocompletion of $C$ in the sense that for any cocomplete category $D$, the restriction functor

$\displaystyle Y^{\ast} : [\widehat{C}, D]_{\text{cocont}} \to [C, D]$

from the category of cocontinuous functors $\widehat{C} \to D$ to the category of functors $C \to D$ is an equivalence. In particular, any functor $C \to D$ extends (uniquely, up to natural isomorphism) to a cocontinuous functor $\widehat{C} \to D$, and all cocontinuous functors $\widehat{C} \to D$ arise this way (up to natural isomorphism).

Colimits should be thought of as a general notion of gluing, so the above should be understood as the claim that $\widehat{C}$ is the category obtained by “freely gluing together” the objects of $C$ in a way dictated by the morphisms. This intuition is important when trying to understand the definition of, among other things, a simplicial set. A simplicial set is by definition a presheaf on a certain category, the simplex category, and the universal property above says that this means simplicial sets are obtained by “freely gluing together” simplices.

In this post we’ll content ourselves with meandering towards a proof of the above result. In a subsequent post we’ll give a sampling of applications.

A toy version of the above result

Coproducts in particular are examples of colimits, so if we think of coproducts as being analogous to addition, we can think of a cocomplete category as being analogous to a commutative monoid and a cocontinuous functor as being analogous to a morphism of commutative monoids. The universal property above can then be thought of as analogous to the following. Let $C$ be a set and let $\widehat{C}$ be the set of functions $C \to \mathbb{Z}_{\ge 0}$ which vanish except at finitely many points in $C$. There is an inclusion $C \mapsto \widehat{C}$ sending a point in $C$ to the indicator function which is equal to $1$ at that point and $0$ elsewhere.

Theorem: The natural inclusion $C \to \widehat{C}$ exhibits $\widehat{C}$ as the the free commutative monoid on $C$ in the sense that for any commutative monoid $D$, the restriction map

$\displaystyle \text{Hom}_{\text{CMon}}(\widehat{C}, D) \to \text{Hom}_{\text{Set}}(C, D)$

from the set of monoid homomorphisms $\widehat{C} \to D$ to the set of functions $C \to D$ is a bijection.

(Of course an intriguing difference between the toy theorem and the real theorem is that being cocomplete is a property of a category, while being a commutative monoid is a structure placed on a set.)

In the setting of commutative monoids, a shorter description of the above theorem is that there’s a forgetful functor from commutative monoids to sets and that $C \mapsto \widehat{C}$ describes its left adjoint. Similarly, we’d like to be able to say that there’s a forgetful functor from cocomplete categories to categories and that the Yoneda embedding is its left adjoint. Unfortunately, there are nontrivial size issues that get in the way: $\widehat{C}$ is never small, and in fact, the only cocomplete small categories are preorders by a theorem of Freyd.

In any case, before we get to discussing the result in full generality, let’s look at some illustrative examples.

Sets

Take $C = \{ \bullet \}$ to be the terminal category. Then $\widehat{C} \cong \text{Set}$ is just the category of sets. This example already says something interesting: the universal property implies that $\text{Set}$ is the free cocomplete category on an object in the sense that if $D$ is a cocomplete category, then the category of cocontinuous functors $\text{Set} \to D$ is equivalent to $D$ itself. The inverse of this equivalence sends an object $d \in D$ to the functor

$\displaystyle \text{Set} \ni S \mapsto \bigsqcup_{s \in S} d \in D$

which, given a set $S$, returns the coproduct of $|S|$ copies of $d$, and conversely every cocontinuous functor has this form. This statement should be thought of as analogous to the statement that $\mathbb{Z}_{\ge 0}$ is the free commutative monoid on a point.

Graphs

Take $C = \{ V \rightrightarrows E \}$ to be the category with two objects and two parallel morphisms between them. (This category is in fact a truncation of the simplex category.) Think of $V$ as a vertex, $E$ as an edge, and the two morphisms as the two inclusions of the endpoints of the edge. A presheaf $F \in \widehat{C}$ is then precisely a pair of sets $F(V), F(E)$ together with a pair of functions

$\displaystyle s, t : F(E) \to F(V)$.

The two maps have been named $s, t$ because we can think of them as source and target maps: in fact, $F$ is precisely a (directed multi)graph with vertex set $F(V)$ and edge set $F(E)$. Here the universal property of presheaves can be interpreted as the claim that graphs are obtained by freely gluing together edges along vertices.

The universal property also gives a natural way of describing graphs as topological spaces, as follows: $\text{Top}$ is a cocomplete category, and there is a functor $C \to \text{Top}$ sending $V$ to a point, $E$ to an interval $[0, 1]$, and the two arrows $V \to E$ to the two inclusions of the endpoints of the interval. By the universal property, this functor extends to a cocontinuous functor $\text{Graph} \to \text{Top}$ sending a graph to its underlying topological space (with directions on the edges ignored). This is a simple version of geometric realization.

But of course the universal property implies that there are many other more exotic notions of geometric realization for graphs. For example, instead of using topological spaces we could use affine schemes: fixing a field $k$, the category $k\text{-Aff}$ of affine schemes over $k$ is cocontinuous, and there is a functor $C \to k\text{-Aff}$ sending $V$ to a point $\text{Spec } k$, $E$ to $\text{Spec } k[t] \cong \mathbb{A}^1$, and the two maps $V \to E$ to the inclusions of the two points $1, -1$ into $\mathbb{A}^1$ (for example). By the universal property we obtain a geometric realization functor $\text{Graph} \to \text{Aff}$ which, for example, sends the loop (the graph consisting of a vertex and an edge from that vertex to itself) to the affine scheme with ring of functions

$\displaystyle \{ f \in k[t] : f(1) = f(-1) \} = k[t^2, t^3 - t]$.

This affine scheme is precisely the nodal cubic. To see this, write the loop as the coequalizer of the two maps $V \rightrightarrows E$, thought of as natural transformations between the corresponding presheaves. To compute the ring of functions on the resulting affine scheme means computing the equalizer of the two maps $k[t] \to k$ given by evaluation at $1$ and $-1$ respectively.

Species

Write $S$ for the category (really groupoid) of finite sets and bijections. This is equivalently the core of the category $\text{FinSet}$ of finite sets and functions. It is equivalent, as a category, to the disjoint union

$\displaystyle S \cong \bigsqcup_{n \ge 0} BS_n$

of the one-object groupoids corresponding to the symmetric groups $S_n$, hence the name $S$. We will often think of the objects of $S$ as the non-negative integers. A presheaf $F \in \widehat{S}$ is, depending on who you ask, a species, $S$-module, or symmetric sequence in sets; we’ll use the term species. More concretely, a species is a collection of sets $F(n)$ indexed by the non-negative integers such that each set $F(n)$ is equipped with a (right) action of the symmetric group $S_n$.

Species are surprisingly fundamental objects in mathematics. Under the name species, they were introduced by Joyal to study combinatorics, and among other things to categorify the theory of exponential generating functions; see, for example, Bergeron, Labelle, and Leroux. I think the names $S$-module and symmetric sequence are used by authors studying operads, as operads are species with extra structure (see the nLab for details).

The universal property tells us that we can extend any functor $S \to D$ from $S$ to a cocomplete category $D$ to a cocontinuous functor $\widehat{S} \to D$. An important source of functors $S \to D$ is given by taking $D$ to be a symmetric monoidal category, $d \in D$ to be an object, and considering the functor

$\displaystyle S \ni n \mapsto d^{\otimes n} \in D$.

This observation can be codified as the following universal property.

Theorem: $S$, equipped with disjoint union, is the free symmetric monoidal category on an object in the sense that for any symmetric monoidal category $D$, the restriction functor from the category of symmetric monoidal functors $S \to D$ to the category of functors $1 \to D$, which is just $D$, is an equivalence.

If $D$ is in addition cocomplete, in such a way that the monoidal operation is cocontinuous in both arguments (symmetric monoidally cocomplete), then after choosing an object $d \in D$, we get not only a symmetric monoidal functor $S \to D$ but even a functor $\widehat{S} \to D$, which turns out to be symmetric monoidal if $\widehat{S}$ is given a monoidal structure via Day convolution. (Day convolution is the monoidal structure categorifying the product of exponential generating functions.) This observation can in turn be codified as a universal property.

Theorem: $\widehat{S}$, equipped with Day convolution, is the free symmetric monoidally cocomplete category on an object in the sense that for any symmetric monoidally cocomplete category $D$, the restriction functor from the category of symmetric monoidal cocontinuous functors $\widehat{S} \to D$ to the category of functors $1 \to D$ (thinking of $1$ as a representable presheaf), which is just $D$, is an equivalence.

What do these symmetric monoidal cocontinuous functors $\widehat{S} \to D$ actually look like? For an object $d \in D$, the corresponding functor $\widehat{S} \to D$ is

$\displaystyle \widehat{S} \ni F \mapsto \bigsqcup_{n \ge 0} F(n) \otimes_{S_n} d^{\otimes n} \in D$

where $F(n) \otimes_{S_n} d^{\otimes n}$ is shorthand for taking coinvariants $(F(n) \otimes d^{\otimes n})_{S_n}$ with respect to the diagonal action of $S_n$, and $F(n) \otimes d^{\otimes n}$ is shorthand for the coproduct $\bigsqcup_{F(n)} d^{\otimes n}$ of an $F(n)$-indexed family of $d^{\otimes n}$s (see copower for some motivation behind this notation). This is an important construction: in the special case that $F$ is an operad, so that $F(n)$ describes the set of $n$-ary operations in the operad, the above construction describes the free $F$-algebra on $d$. If all of the $F(n)$ are finite sets, the above construction can also be thought of as categorifying the exponential generating function

$\displaystyle \sum_{n \ge 0} \frac{|F(n)| d^n}{n!} \in \mathbb{Q}[[d]]$

(thinking of taking coinvariants with respect to an $S_n$-action as categorifying dividing by $n!$, in accordance with the general yoga of groupoid cardinality.)

Example. Let $F$ be the associative operad. Here $F(n)$ consists of operations of the form

$\displaystyle (x_1, ..., x_n) \mapsto x_{\sigma(1)} ... x_{\sigma(n)}$

for each permutation $\sigma$ and hence, as a right $S_n$-set, is isomorphic to $S_n$. $F(n) \otimes_{S_n} d^{\otimes n}$ is then naturally isomorphic to $d^{\otimes n}$, so the free associative algebra (monoid) on an object $d$ in a symmetric monoidally cocomplete category is the infinite coproduct

$\displaystyle \bigsqcup_{n \ge 0} d^{\otimes n}$.

Regarded just as a combinatorial species, $F$ categorifies the generating function $\frac{1}{1 - d}$.

Example. Let $F$ be the commutative operad. Here $F(n)$ consists of the single operation

$\displaystyle (x_1, ..., x_n) \mapsto x_1 ... x_n$

and hence, as a right $S_n$-set, is trivial. $F(n) \otimes_{S_n} d^{\otimes n}$ is then the quotient $d^{\otimes n}/S_n$, so the free commutative algebra (commutative monoid) on an object $d$ in a symmetric monoidally cocomplete category is the infinite coproduct

$\displaystyle \bigsqcup_{n \ge 0} d^{\otimes n}/S_n$.

Regarded just as a combinatorial species, $F$ categorifies the generating function $\exp(d)$.

Recall that we are trying to show that the restriction functor

$\displaystyle Y^{\ast} : [\widehat{C}, D]_{\text{cocont}} \to [C, D]$

is an equivalence. By analogy with the corresponding statement about sets, commutative monoids, and free commutative monoids, one way to proceed with this proof is to figure out how to write every presheaf $\widehat{C}$ as a colimit of representable presheaves (the image of the Yoneda embedding $C \to \widehat{C}$), then turn this colimit into a colimit in $D$ by applying a given cocontinuous functor $F : \widehat{C} \to D$. This will show, roughly speaking, that the restriction map is “injective” (although we need to be careful about what this means because we’re dealing with categories, not sets).

To show that the restriction map is “surjective,” we need to extend a functor $C \to D$ to a cocontinuous functor $\widehat{C} \to D$. We’d like to do this “by linearity,” by choosing an expression for a presheaf as a colimit of representable presheaves and turning this colimit into a colimit in $D$ by applying our functor; however, we need to be able to make this choice functorially, and then we still need to verify that the resulting functor is actually cocontinuous.

Presheaves as colimits of representable presheaves

The following result is at least implicit in the use of the terminology “free cocompletion” and is important in getting the above proof to work, as well as being a generally useful thing to know in category theory. It is sometimes called the co-Yoneda lemma for reasons that are a little difficult to explain without more background. Previously it showed up when we discussed operations and pro-objects, but there we rushed through the proof and here we’ll take a more leisurely pace.

Theorem: Let $C$ be a (locally small) category. Then every presheaf $F : C^{op} \to \text{Set}$ is canonically a colimit of representable presheaves.

Idea #1. One relevant intuition here is to think of a presheaf as a recipe for writing down a colimit in $C$ by prescribing how many copies of each object and morphism in $C$ appear in the diagram, in the same way that one can think of a function from a set $X$ to the non-negative integers (with finite support) as a recipe for writing down an element of the free commutative monoid on $X$ by prescribing how many copies of each element of $X$ to add up. This intuition is hopefully quite clear in the case of graphs, where a presheaf on $\{ V \rightrightarrows E \}$ tells you how many edges and vertices to glue together as well as how to glue them together.

Idea #2. For the more categorically minded, a related intuition is the following. Let $F : J \to C$ be a diagram in $C$. The colimit $\text{colim}(F)$, if it exists, is defined by a universal property describing how maps out of it behave. This determines the covariant functor $\text{Hom}(\text{colim}(F), -)$ it represents uniquely, but says very little about the contravariant functor $\text{Hom}(-, \text{colim}(F))$ it represents. However, there is in some sense a “minimal” possibility for this contravariant functor. For example, if the colimit in question is the coproduct $c_1 \sqcup c_2$ of two objects, then by definition

$\displaystyle \text{Hom}(c_1 \sqcup c_2, -) \cong \text{Hom}(c_1, -) \times \text{Hom}(c_2, -)$

but the only thing we know about $\text{Hom}(-, c_1 \sqcup c_2)$ is that there are natural inclusion maps $c_1, c_2 \to c_1 \sqcup c_2$, hence we know that $\text{Hom}(-, c_1 \sqcup c_2)$ admits a natural map from $\text{Hom}(-, c_1) \sqcup \text{Hom}(-, c_2)$, but this is all we know without further information. Now, since colimits in functor categories are computed pointwise, $\text{Hom}(-, c_1) \sqcup \text{Hom}(-, c_2)$ is none other than the coproduct of $c_1, c_2$, but regarded as lying in the presheaf category. In general, the sense in which presheaves are “free colimits” of objects of $C$ is that, as contravariant functors, they describe the “minimal” contravariant functors that a colimit of objects in $C$ could represent.

Now we turn to the proof itself.

Proof. Let $F \in \widehat{C}$ by a presheaf. Since we want to describe $F$ as a colimit, let’s think about the contravariant functor $\text{Hom}_{\widehat{C}}(F, -)$ that $F$ represents. By definition, $\text{Hom}_{\widehat{C}}(F, G)$ consists of families $\eta_c : F(c) \to G(c)$ of maps satisfying the naturality condition that if $f : c \to d$ is a morphism, then the diagram

(drawn using QuickLaTex) commutes. We want to write $F$ as a colimit of representable functors, and we know that by the Yoneda lemma, if $c \in \widehat{C}$ (which we use to designate the representable functor $\text{Hom}(c, -)$) is a representable functor, then $\text{Hom}_{\widehat{C}}(c, G) \cong G(c)$. To go from elements of $G(c)$ to maps $\eta_c : F(c) \to G(c)$ we need $|F(c)|$ copies of $c$.

A clean way to obtain these copies is to write down a diagram $J \to C$ whose objects are given by pairs $(c, s_c)$ of an object $c \in C$ and an element $s_c \in F(c)$, equipped with the map to $C$ given by forgetting $s_c$. The preimage of $c \in C$ is then precisely $F(c)$, and if we don’t specify any morphisms then a cocone over this diagram in $\widehat{C}$ is precisely a family $\eta_c : F(c) \to G(c)$ of maps satisfying no naturality conditions.

To get the naturality conditions back we need to equip $J$ with morphisms. Choosing the morphisms $f : c \to d$ such that $F(f) : F(d) \to F(c)$ sends $s_d$ to $s_c$ enforces precisely the naturality condition desired on the maps $\eta_c : F(c) \to G(c)$, and furthermore the maps $(c, s_c) \mapsto s_c \in F(c)$ canonically exhibit $F$ as the colimit of the corresponding diagram in $\widehat{C}$ as desired. $\Box$

(The diagram $J$ we constructed above is the opposite of the category of elements $\text{el}(F)$ of $F$, which is a special case of the Grothendieck construction. As described in the nLab article, we can think of $\text{Set}$ as the classifying space of $\text{Set}$-bundles, and then $F$ is the classifying map of a $\text{Set}$-bundle on $C^{op}$ and $\text{el}(F)$ is the total space of the bundle. $\text{el}(F)$ admits other more sophisticated descriptions that won’t concern us at the moment.)

The actual proof

Now we return to the proof of the theorem. Let $C$ be a small category and $D$ be a (locally small) cocomplete category. Recall, again, that we are trying to show that the restriction functor

$\displaystyle Y^{\ast} : [\widehat{C}, D]_{\text{cocont}} \to [C, D]$

is an equivalence of categories. If we wanted to show that a map of sets was a bijection, we’d just have to show that it’s injective and surjective, and we sketched some intuition for why this should be the case above. But an equivalence of categories is more subtle, and instead of verifying two conditions we need to verify three: $Y^{\ast}$ needs to be full, faithful, and essentially surjective.

To show that $Y^{\ast}$ is fully faithful, let $\eta : F \to G$ be a natural transformation between two cocontinuous functors $F, G : \widehat{C} \to D$. We want to show that knowing the restriction $\eta_c : F(c) \to G(c)$ of $\eta$ to representable functors $c \in \widehat{C}$ uniquely determines $\eta_p : F(p) \to G(p)$ for all presheaves $p \in \widehat{C}$, and moreover that given such a restriction we can always extend it to a natural transformation on all presheaves. But since $F$ is cocontinuous and $p$ is a colimit of representables, $\eta_p$ is freely determined by the universal property of colimits: in particular it is determined by its restriction to every representable $c$, which is just $\eta_c$ composed with the inclusion $G(c) \to G(p)$ by naturality, and given such a compatible family of restrictions it exists.

To show that $Y^{\ast}$ is essentially surjective, let $F : C \to D$ be a functor. We want to extend $F$ to a cocontinuous functor $F_{!} : \widehat{C} \to D$, which we will do “by linearity”: if $p \in \widehat{C}$ is a presheaf, we’ll write it canonically as a colimit of representable presheaves using the diagram of shape $\text{el}(p)^{op}$ we described above (which is small since $C$ is small), then apply $F$ to this diagram to obtain a diagram in $D$, then take the colimit in $D$. In symbols,

$\displaystyle F_{!} : \widehat{C} \ni p \mapsto \text{colim}_{\text{el}(p)^{op}} F(-) \in D$.

Every step of this process, including the formation of the category of elements, is functorial, so $\widehat{F}$ really is a functor. (It is crucial that $C$ be small to ensure that $\text{el}(p)^{op}$ is a small diagram; “cocomplete” only means that all small colimits exist, and in fact the theorem of Freyd alluded to above also implies that a category with all colimits is a preorder.)

It remains to verify first that $F_{!}$ really is cocontinuous and second that it really does restrict to (a functor naturally isomorphic to) $F$. These will both be a corollary of the following.

Proposition: $F_{!}$ is the left adjoint of the functor

$\displaystyle F^{\ast} : D \ni d \mapsto \text{Hom}_D(F(-), d) \in \widehat{C}$.

(A version of this construction, the “left pro-adjoint,” appeared previously on this blog.)

(There is some mild abuse of notation going on here. $F^{\ast}$ should really denote the functor $\widehat{D} \to \widehat{C}$ given by precomposition with $F$, and $F_{!}$ should really denote the left adjoint of this functor, also known as left Kan extension. The decorations (pronounced “upper star” and “lower shriek” respectively) on these functors are by analogy with some of Grothendieck’s six operations on sheaves.)

Proof. We want to show that there is a natural bijection

$\displaystyle \text{Hom}_D(F_{!}(p), d) \cong \text{Hom}_{\widehat{C}}(p, F^{\ast}(d))$.

We know that $p \cong \text{colim}_{\text{el}(p)^{op}} (-)$, hence we can write the RHS as

$\lim_{\text{el}(p)^{op}} \text{Hom}_D(F(-), d)$

first by the universal property of colimits and second by the Yoneda lemma. On the other hand, by definition $F_{!}$ is also a colimit over $\text{el}(p)^{op}$, hence we can write the LHS as

$\lim_{\text{el}(p)^{op}} \text{Hom}_D(F(-), d)$

by the universal property of colimits. The conclusion follows. $\Box$

In particular, since $F_{!}$ is a left adjoint, it is necessarily cocontinuous, and if $p \in \widehat{C}$ above is a representable presheaf $c$ then the above adjunction gives

$\displaystyle \text{Hom}_D(F_{!}(c), d) \cong \text{Hom}_{\widehat{C}}(c, F^{\ast}(d)) \cong \text{Hom}_D(F(c), d)$

by the Yoneda lemma, so $F_{!}(c) \cong F(c)$ by a second application of the Yoneda lemma. It follows that $Y^{\ast}$ is essentially surjective, hence an equivalence as desired. $\Box$

(In fact $Y^{\ast}$ should really have denoted the functor $[\widehat{C}, D] \to [C, D]$ given by precomposition with $Y$, and what we really wrote down above is the left adjoint $Y_{!} : [C, D] \to [\widehat{C}, D]$ to this functor, which is a genuine left Kan extension along $Y$. We could’ve written the proof so as to show that $Y_{!}$ is not only a left adjoint but in fact an inverse once we restrict to cocontinuous functors.)

6 Responses

1. A slightly less well-known fact: the free cocomplete category generated by a locally small category remains locally small. (Concretely, it is the full subcategory of presheaves generated by the representables under colimits for small diagrams.) This yields a KZ-monad (= lax-idempotent pseudomonad) on the 2-category of cocomplete categories.

• Where, of course, I actually mean “2-category of locally small categories”.

• Cool. Is it easy to recognize which presheaves these are in practice?

• It depends on the base. If we start with an accessible category C, then the small presheaves on C^op are precisely the functors C → Set that preserve κ-filtered colimits for some κ (i.e. accessible functors C → Set). This is good enough to recognise small presheaves on the category of affine schemes, for example; but I don’t know of many categories whose opposite is accessible.

For the (very) general case, see Theorem 4.83 in [Kelly, _Basic concepts of enriched category theory_]. It’s somewhat confusing that Kelly refers to these functors as “accessible”.

2. Great post! Just a minor remark: In the final proof, near the end, you use the (covariant) Yoneda lemma to show F_!(c) = F(c) . Since you use the Yoneda lemma in D, you should add the assumption that D is locally small!

• Ah, you’re right; thanks for the correction!