The free cocompletion I

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

into its presheaf category (where we use to denote the category of functors ). The Yoneda lemma asserts in particular that is full and faithful, which justifies calling it an embedding.

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

Theorem: The Yoneda embedding exhibits as the free cocompletion of in the sense that for any cocomplete category , the restriction functor

from the category of cocontinuous functors to the category of functors is an equivalence. In particular, any functor extends (uniquely, up to natural isomorphism) to a cocontinuous functor , and all cocontinuous functors 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 is the category obtained by “freely gluing together” the objects of 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 be a set and let be the set of functions which vanish except at finitely many points in . There is an inclusion sending a point in to the indicator function which is equal to at that point and elsewhere.

Theorem: The natural inclusion exhibits as the the free commutative monoid on in the sense that for any commutative monoid , the restriction map

from the set of monoid homomorphisms to the set of functions 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 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: 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 to be the terminal category. Then is just the category of sets. This example already says something interesting: the universal property implies that is the free cocomplete category on an object in the sense that if is a cocomplete category, then the category of cocontinuous functors is equivalent to itself. The inverse of this equivalence sends an object to the functor

which, given a set , returns the coproduct of copies of , and conversely every cocontinuous functor has this form. This statement should be thought of as analogous to the statement that is the free commutative monoid on a point.

Graphs

Take 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 as a vertex, as an edge, and the two morphisms as the two inclusions of the endpoints of the edge. A presheaf is then precisely a pair of sets together with a pair of functions

.

The two maps have been named because we can think of them as source and target maps: in fact, is precisely a (directed multi)graph with vertex set and edge set . 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: is a cocomplete category, and there is a functor sending to a point, to an interval , and the two arrows to the two inclusions of the endpoints of the interval. By the universal property, this functor extends to a cocontinuous functor 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 , the category of affine schemes over is cocontinuous, and there is a functor sending to a point , to , and the two maps to the inclusions of the two points into (for example). By the universal property we obtain a geometric realization functor 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

.

This affine scheme is precisely the nodal cubic. To see this, write the loop as the coequalizer of the two maps , 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 given by evaluation at and respectively.

Species

Write for the category (really groupoid) of finite sets and bijections. This is equivalently the core of the category of finite sets and functions. It is equivalent, as a category, to the disjoint union

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

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 -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 from to a cocomplete category to a cocontinuous functor . An important source of functors is given by taking to be a symmetric monoidal category, to be an object, and considering the functor

.

This observation can be codified as the following universal property.

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

If 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 , we get not only a symmetric monoidal functor but even a functor , which turns out to be symmetric monoidal if 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: , equipped with Day convolution, is the free symmetric monoidally cocomplete category on an object in the sense that for any symmetric monoidally cocomplete category , the restriction functor from the category of symmetric monoidal cocontinuous functors to the category of functors (thinking of as a representable presheaf), which is just , is an equivalence.

What do these symmetric monoidal cocontinuous functors actually look like? For an object , the corresponding functor is

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

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

Example. Let be the associative operad. Here consists of operations of the form

for each permutation and hence, as a right -set, is isomorphic to . is then naturally isomorphic to , so the free associative algebra (monoid) on an object in a symmetric monoidally cocomplete category is the infinite coproduct

.

Regarded just as a combinatorial species, categorifies the generating function .

Example. Let be the commutative operad. Here consists of the single operation

and hence, as a right -set, is trivial. is then the quotient , so the free commutative algebra (commutative monoid) on an object in a symmetric monoidally cocomplete category is the infinite coproduct

.

Regarded just as a combinatorial species, categorifies the generating function .

Intuitions about the proof

Recall that we are trying to show that the restriction functor

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 as a colimit of representable presheaves (the image of the Yoneda embedding ), then turn this colimit into a colimit in by applying a given cocontinuous functor . 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 to a cocontinuous functor . 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 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 be a (locally small) category. Then every presheaf 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 by prescribing how many copies of each object and morphism in appear in the diagram, in the same way that one can think of a function from a set to the non-negative integers (with finite support) as a recipe for writing down an element of the free commutative monoid on by prescribing how many copies of each element of to add up. This intuition is hopefully quite clear in the case of graphs, where a presheaf on 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 be a diagram in . The colimit , if it exists, is defined by a universal property describing how maps out of it behave. This determines the covariant functor it represents uniquely, but says very little about the contravariant functor 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 of two objects, then by definition

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

Now we turn to the proof itself.

Proof. Let by a presheaf. Since we want to describe as a colimit, let’s think about the contravariant functor that represents. By definition, consists of families of maps satisfying the naturality condition that if is a morphism, then the diagram

(drawn using QuickLaTex) commutes. We want to write as a colimit of representable functors, and we know that by the Yoneda lemma, if (which we use to designate the representable functor ) is a representable functor, then . To go from elements of to maps we need copies of .

A clean way to obtain these copies is to write down a diagram whose objects are given by pairs of an object and an element , equipped with the map to given by forgetting . The preimage of is then precisely , and if we don’t specify any morphisms then a cocone over this diagram in is precisely a family of maps satisfying no naturality conditions.

To get the naturality conditions back we need to equip with morphisms. Choosing the morphisms such that sends to enforces precisely the naturality condition desired on the maps , and furthermore the maps canonically exhibit as the colimit of the corresponding diagram in as desired.

(The diagram we constructed above is the opposite of the category of elements of , which is a special case of the Grothendieck construction. As described in the nLab article, we can think of as the classifying space of -bundles, and then is the classifying map of a -bundle on and is the total space of the bundle. 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 be a small category and be a (locally small) cocomplete category. Recall, again, that we are trying to show that the restriction functor

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: needs to be full, faithful, and essentially surjective.

To show that is fully faithful, let be a natural transformation between two cocontinuous functors . We want to show that knowing the restriction of to representable functors uniquely determines for all presheaves , and moreover that given such a restriction we can always extend it to a natural transformation on all presheaves. But since is cocontinuous and is a colimit of representables, is freely determined by the universal property of colimits: in particular it is determined by its restriction to every representable , which is just composed with the inclusion by naturality, and given such a compatible family of restrictions it exists.

To show that is essentially surjective, let be a functor. We want to extend to a cocontinuous functor , which we will do “by linearity”: if is a presheaf, we’ll write it canonically as a colimit of representable presheaves using the diagram of shape we described above (which is small since is small), then apply to this diagram to obtain a diagram in , then take the colimit in . In symbols,

.

Every step of this process, including the formation of the category of elements, is functorial, so really is a functor. (It is crucial that be small to ensure that 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 really is cocontinuous and second that it really does restrict to (a functor naturally isomorphic to) . These will both be a corollary of the following.

Proposition: is the left adjoint of the functor

.

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

(There is some mild abuse of notation going on here. should really denote the functor given by precomposition with , and 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

.

We know that , hence we can write the RHS as

first by the universal property of colimits and second by the Yoneda lemma. On the other hand, by definition is also a colimit over , hence we can write the LHS as

by the universal property of colimits. The conclusion follows.

In particular, since is a left adjoint, it is necessarily cocontinuous, and if above is a representable presheaf then the above adjunction gives

by the Yoneda lemma, so by a second application of the Yoneda lemma. It follows that is essentially surjective, hence an equivalence as desired.

(In fact should really have denoted the functor given by precomposition with , and what we really wrote down above is the left adjoint to this functor, which is a genuine left Kan extension along . We could’ve written the proof so as to show that is not only a left adjoint but in fact an inverse once we restrict to cocontinuous functors.)