It’s time to understand why the category of sheaves on a topological space acts like the category of sets in the following ways:

• It has finite colimits.

• It has finite limits.

• It is cartesian closed.

• It has a subboject classifier.

We summarize these four properties by saying the category of sheaves is an **elementary topos**. (In fact it’s better, since it has *all* limits and colimits.)

As a warmup, first let’s see why the category of *presheaves* on a topological space is an elementary topos!

It’s actually just as easy to see something more general, which will come in handy later: the category of presheaves on *any* category is an elementary topos. Remember, given a category a **presheaf** on is a functor

A **morphism of presheaves** from to another presheaf

is a natural transformation

Presheaves on and morphisms between them form a **presheaf category**, which we call

or for short.

Presheaves on a topological space are just the special case where we take to be the poset of open subsets of So if you want a ‘geometrical’ intuition for presheaves on a category, you should imagine the objects of the category as being like open sets. This will come in handy later, when we talk about *sheaves* on a category.

But there is also another important intuition regarding presheaves. This is more of an ‘algebraic’ intuition. Starting from a category and building the presheaf category

is analogous to taking a set and building the set

of all functions from to the integers. is a commutative ring if we use pointwise addition and multiplication of functions as our ring operations. is an elementary topos—but this means we should think of an elementary topos as being a bit like a commutative ring. More precisely, it’s like a ‘categorified’ commutative ring, since it’s a category rather than merely a set.

There’s a one-to-one function

sending any element of to the characteristic function of that element. Similarly, there’s a full and faithful functor

sending any object to the presheaf This is called the **Yoneda embedding**. So, presheaf categories are a trick for embedding categories into elementary topoi!

In fact presheaf categories have *all* limits and colimits, so they are better than just elementary topoi: we will someday see they are examples of ‘Grothendieck topoi’. There are also other ways in which my story just now could be polished, but it would be a bit distracting to do so. Let’s get to work and study presheaf categories!

Today I’ll just talk about colimits and limits.

** Colimits in presheaf categories **

Presheaf categories have all colimits, and these colimits can be ‘computed pointwise’. What does this mean? Colimits are a lot like addition, and taking colimits of presheaves is a lot like how we add functions from a set to We just add their values at each point.

More precisely, say we have a diagram of presheaves on This is a functor

where is any small category, the ‘shape’ of our diagram. The colimit of should be a presheaf, and I’ll call this

How do we compute it? Well, notice that is a functor from to the category of functors from to So, we can change our viewpoint and think of it as a functor

I’m using the same name for this because I’m lazy! Note that for each object we get a functor

Since has colimits, we can take the colimit of this functor and get a set

But you can check that this set depends functorially on so it defines a functor from to which is our desired functor

Of course, you also have to check that this really *is* the colimit of our diagram of presheaves on

Mac Lane and Moerdijk refer the reader to Section V.3 of *Categories for the Working Mathematician* for a proof of this result, but I think it’s better to prove it yourself. That is, it seems less painful to follow your nose and do the obvious thing at each step than to wrap your brain around someone else’s notation. I guess this is only true if you’ve go the hang of the subject, but anyway:

**Puzzle.** Show in the above situation that depends functorially on and that the resulting functor is the colimit of the diagram

By the way, I can’t resist mentioning an important fact here: the category of presheaves on is the free category with all colimits on In other words, it not only has all colimits, it’s precisely what you’d get by taking and ‘freely’ throwing in all colimits. This is why I mentioned colimits first.

This fact is analogous to the fact that when is a finite set, is the free abelian group on The fact that we don’t need a finiteness condition when working with presheaves is one of those ways in which categories are nicer than sets.

### Limits in presheaf categories

Just as colimits generalize addition, limits generalize multiplication. Presheaf categories also have all limits, and these too can be ‘computed pointwise’. The argument is just like that for colimits, but now we use the fact that has all limits.

**Puzzle.** Given a diagram of presheaves on

show that depends functorially on and that the resulting functor is the limit of the diagram

### The category of graphs

It helps to understand some examples of what we’re doing here, and a nice example is the category of graphs. There’s a category that has two objects and , and just two morphisms

besides the identity morphisms. A presheaf on is what category theorists call a graph.

Why? Well, say we have such a presheaf

It consists of a set called the **set of vertices** and a set called the **set of edges**, along with two functions

assigning to each edge its **source** and **target**. This is just what category theorists call a **graph**; graph theorists might call it a ‘directed multigraph’, and some other mathematicians would call it a ‘quiver’.

We will use to mean the **category of graphs**, namely the presheaf category

Note how the ‘op’ in the definition of presheaf turned the morphisms into functions The ‘op’ is more of a nuisance than a help in this example (at least so far): we had to make and go from to precisely to counteract the effect of this ‘op’.

Since colimits and limits are computed pointwise in a presheaf category, we can compute the colimit or limit of a diagram of graphs quite easily: we just take the colimit of the sets of vertices and the sets of edges separately, and the rest goes along for the ride.

**Puzzle.** Let the graph be the **walking vertex**: that is, the graph with just one vertex and no edges. Let be the **walking edge**: that is, the graph with one edge and two vertices, the source and target of that edge. Show that there are exactly two different morphisms

Compute the equalizer and coequalizer of

**Puzzle.** Show explicitly how to build any graph as a colimit of copies of the walking vertex and the walking edge. That is, show any graph is isomorphic to the colimit of some diagram in where the objects in this diagram are all copies of and/or

Hi John, I love the story about the category of presheaves being analogous to the free abelian group on a finite set S. It seems the latter isn’t literally “the free cocompletion of S,” which bugs me. (I might’ve asked you about this a while ago.) But it looks like they are connected in a broader way.

They both seem to be part of a special kind of free-forgetful adjunction F ⊣ U. It’s special in that there exists a fixed, special object [blah] (say, the integers or the category Set) such that free object FX on an object X has the property that UFX can be identified with all morphisms X –> U[blah].

In one case, the adjunction is between abelian groups and finite sets, and [blah] is the group of integers Z. The free abelian group FS on S can be identified with the set of functions S –> UZ, so that UFS = UZ^S. (I think the U is pretty revealing here. It fixes the [nit-picky] problem that the types of S and Z don’t match in the phrase “a morphism S –> Z,” or in the notation Z^S.)

In the other case, the adjunction must be, I imagine, between cocomplete categories and plain categories, and [blah] is Set (or any other cocomplete enriching category). The units of these adjunctions are the usual S –> UZ^S and the (enriched) Yoneda embedding, and they fit into the nice, familiar universal properties.

I’ve fleshed out a bit on my own. It seems fine for a while, but things become murky when I want to do other things down the road. But this is all pretty elementary—adjunctions are bread and butter!—so I’m sure category theorists already know exactly what’s going on.

Do you know if a particular kind of “free forgetful adjunction with a special object [blah]” has been investigated by anyone? Perhaps even on the nLab, nCafe, or in a paper somewhere? It’s hard to believe a story as great as this has gone untouched.

Hi! There’s a lot to say about this, probably more than I know, but here’s something to get the ball rolling.

First, some technical crud that I feel obliged to mention. There’s an adjunction between sets and abelian groups. There’s also something like an adjunction between categories and cocomplete categories, though this is a bit slippery due to size issues: the category of presheaves on a small category is usually a large cocomplete category, but the underlying category of such a cocomplete category is usually not small! And in fact a miniature version of these ‘size issues’ afflicts what you wrote too: you mentioned an adjunction between abelian groups and finite sets, but that doesn’t really exist: the free abelian group on a finite set is usually infinite, but the underlying set of such an abelian group is usually not finite.

You can read more about the first problem here. Briefly, the free cocompletion of a small category C is the category of functors from C

^{op}to Set. A large category C also has a free cocompletion, but we don’t get it by takingallfunctors from C^{op}to Set, just those that are ‘small’ in some sense.The second problem is much more familiar but similar. The free abelian group on a finite set S is the set of all functions from S to . An infinite set also has a free abelian group on it, but we don’t get it by taking

allfunctions from S to , just those that are zero except at finitely many points of S. This is again a kind of ‘smallness’ condition.(And yes, I should have said

the underlying category ofthe free cocompletion of a small category C is the category of functors from C^{op}to theunderlying categoryof the cocomplete category Set, andthe underlying set ofthe free abelian group on a finite set S is the set of all functions from S tothe underlying set ofthe abelian group )All this is less interesting than what I really wanted to say, but I felt I needed to put these technicalities on the record before going ahead! It’s late now; I’ll say more later. See you!

Ah yes, thanks for bringing attention to this. Looking forward to the rest!

A second comment, more to the point of your question. The group shows up in this game because it’s the free abelian group on the terminal set, 1. Since the functor

F: Set → AbGp

is a left adjoint, it preserves colimits. Every set S is a coproduct of S copies of 1. So, for every set S, FS is a coproduct of S copies of When S is

finite, this givesFS ≅

But what’s true in general is that FS is isomorphic to what I call : the set of all finite -linear combinations of elements of S.

All this has a partial analogue in the categorified case, because Set is the free cocomplete category on the terminal category, which I’ll also call 1. Alas, it’s not true that every category C is a coproduct or even colimit of copies of 1. But it’s a colimit of copies of 2, the ‘walking arrow’, the category with two objects and just one non-identity morphism, which goes from the first object to the second. I’m not sure if the functor

F: Cat → CocompleteCat

is a left adjoint; as mentioned in my last comment this can only work if “Cat” means the category of

largecategories, since the cocompletion even of a small category is typically large, and if F is a left adjoint we’ll need a right adjointU: CocompleteCat → Cat

However, I believe the “free cococomplete category” functor

F: Cat → CocompleteCat

preserve colimits regardless of whether Cat stands for the category of small categories or the category of large categories. So, for any category C, FC will be a colimit of copies of F2, and we can check by hand that

I guess that if I were smart enough I could easily go from this to showing

whenever C is a small category. As mentioned in my last comment, this formula isn’t true when C is a large category. But again, there’s a modification of this formula that is true.

So the case of

F: Set → AbGp

is clean, while the other case is less so. Luckily, the “free vector space on a set”, the “free group on a set”, and so on, all work just as cleanly as the free abelian group on a set!

I see. So this explains why it’s not too surprising to find my “UFS = U[blah]^S” in the wild.

It brings to mind another easy example: Take the free meet semilattice FS on a set S. The underlying set UFS can be identified with the set of all functions S –> {0,1}, i.e. the power set of S.

Interestingly, though, this example seems genuinely different than the abelian group example, in that there’s a way to first equip S and {0,1} with common structure before applying the free functor to S. This is a familiar story, but I’ll share it here. I think it goes like this:

Start with the walking arrow 2 = {0 ≤ 1} or, perhaps more fitting in this context, “the cocomplete category of truth values.” So 2 is a poset-with-all-meets. What’s nice is that any set S can also be viewed as a poset—which I’ll also denote by S—with s ≤ s’ iff s = s’, in which case S = S^op. So, I believe, we can quite literally ask for its free cocompletion (where 2 now takes the place of Set, as in the previous comment) to get the power set FS = 2^S with subset inclusion as the partial order.

I hope I’ve gotten this right. If so, it seems pretty crucial to this example that “any set S can be viewed a poset.” (I realize there is a [en]rich[ed] theory behind this:

Categories enriched over 2 are posets!)The abelian group example appears to be lacking a statement analogous to this.

This disconnect—if I’m assessing correctly—is puzzling to me. It’s like an obvious mystery waiting to be solved! (“Let’s find a way to treat the integers Z as a category so that Z^S is literally the free cocompletion of S!”) And yet I haven’t found much discussion in this area. Or maybe I’m not looking in the right places.

But

now,actually, I’m starting to wonder whether that quest isn’t too interesting from a categorical perspective—and perhaps there’s no real mystery—because it’s theadjunctionthat’s at the heart of everything, lying there in plain sight!Tai-Danae wrote:

I don’t know how to do that. I think of cocomplete categories and abelian groups as two not-very-close cousins in the family of “gadgets with addition”.

1) I think of abelian groups as a special case of commutative monoids.

2) I think of commutative monoids as a special case of symmetric monoidal categories.

3) I think of cocartesian categories as another special case of symmetric monoidal categories. These are categories with finite coproducts, and I think of coproduct as “addition”.

4) I think of cocomplete categories as a special case of cocartesian categories. These are categories where we can take the colimit of any diagram, not just diagrams that consist of a finite set of objects and no morphisms. This is a remarkable enhancement of the concept of addition.

For each of these “gadgets with addition” it’s important to understand the “free gadget on 1, the terminal set”.

1) The free abelian group on 1 is .

2) The free commutative monoid on 1 is .

3) The free symmetric monoidal category on 1 is what I call , the groupoid of finite sets and bijections.

4) The free category with finite coproducts on 1 is , the category of finite sets and functions.

5) The free cocomplete category on 1 is .

All 5 of these things are fundamental in mathematics! They’re different variants of the same idea. Each of them, being a free gadget with addition on 1, automatically gets a multiplication that distributes over addition. (I leave it as a puzzle to see why.)

Note that I climbed a ladder of generality from 1) to 3) and then back down a different ladder from 3) to 5). As a result, we have maps

The gadgets here are all symmetric monoidal categories (where we think of commutative monoids as symmetric monoidal categories with only identity morphisms). The maps are all symmetric monoidal functors, meaning they preserve addition. But in fact all the gadgets are ‘symmetric rig categories’, meaning they also have a multiplication that distributes over addition. And all the maps are maps of symmetric rig categories!

This is part of what I call the ‘backbone’ of mathematics: the most important structures, and their most important relationships.

Math is great!

This is excellent, and really helpful, especially the point that “This is a remarkable enhancement of the concept of addition.”

Thank you!

[…] Last time I tackled the first two bullet points; now let’s do the third. For starters, what’s a cartesian closed category, and why are they so nice? Answering this question will get us into some more ‘philosophical’ aspects of topos theory. […]