I’m explaining why any presheaf category is an elementary topos, meaning that
• it has finite colimits;
• it has finite limits;
• it’s cartesian closed.
• it has a subboject classifier.
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.
Cartesian closed categories
The category of sets has ‘sums’, also known as coproducts: given two sets and there is a set their disjoint union, which acts like their sum in various ways; for example you get its cardinality by adding those of and
The category of sets also has products: given two sets and there is a set their cartesian product, which obeys
Both these can be understood using category theory, and I’m assuming you know how—if not, click the links. But after addition and multiplication comes exponentiation, and this too can be understood categorically. Even before you learn category theory, you should learn that the set of all functions from to is called and it has
But we can generalize this idea of ‘the set of functions from one set to another’ to ‘the object of morphisms from one object to another’ using category theory.
Here’s how. In the category of sets, something nice is true: there’s a natural one-to-one correspondence between functions from to and functions from to A function
eats a pair and spits out an element We can turn this into a function
that eats an element and spits out a function from to as follows:
It’s like ‘delayed gratification’: instead of eating your dinner and dessert at once, you eat your dinner and turn into someone who is ready to eat dessert. Computer scientists call the map sending to currying… perhaps because they always eat curry for dinner? No, actually it’s named after Haskell Curry, who also has a computer language named after him.
This currying process is natural, meaning there’s a natural isomorphism
More precisely, for any set there’s a natural isomorphism
Here both sides are functors waiting to eat two sets (which I’d called and a moment ago) and spit out a set. The blank spots and are places where you can stick sets.
Note that this natural isomorphism says the functor sending any set to the set has a right adjoint, namely the functor sending any set to the set In the usual way of category theorists we can abbreviate this by saying
has a right adjoint,
We can generalize this idea to any category that has finite products. But first, a spiffy new name:
Definition. A category is cartesian if it has finite products, or equivalently if it has binary products and a terminal object.
Definition. A category is cartesian closed if it is cartesian and for any object the functor
has a right adjoint.
Of course in this situation we call the right adjoint
so for any objects there’s a natural one-to-one correspondence between morphisms
It’s no surprise that taking gives an example of a cartesian closed category—that’s the example we were generalizing in the first place. But this example is actually a bit confusing, because in this example and only in this example there’s no difference between which is a set, and which is an object of
(Well, pedants may argue that the category of finite sets, gives another example. But ultra-pedants may argue that a finite set is not exactly the same as a set. Let’s leave them to fight it out, and move on.)
In a cartesian closed category it’s very important to distinguish between and We call the external hom and the internal hom or exponential. The idea is that the internal hom lives ‘inside’ the category while lives ‘outside’ in the category of sets.
The philosophy here is that while category theory is traditionally based on set theory—for example any two objects of a category have a set of morphisms between them—it is nice to move away from this, and try to work with categories in a more free-standing way.
A first step is to consider categories where there’s an object of morphisms between two objects. Of course as long as they’re still categories, they also have sets of morphisms between objects, and also a set (or class) of objects. So we have not completely lifted ourselves up by our bootstraps and floated away from the set-theoretic foundations of mathematics. Not yet, anyway. But this is just the first stage! Eventually we can base set theory on topos theory, which in turn is based on first-order logic.
More to the point right now, the internal hom contains more information than the external hom. To see this, first note that in any category with a terminal object we can define an element of an object to be a morphism
where is the terminal object (that is, our chosen terminal object: they’re all isomorphic). Any object has a set of elements. Furthermore any morphism
lets us turn elements of into elements of as follows: given an element
we get an element
Puzzle. Prove that if has a terminal object, there is a functor
sending each object to its set of elements and each morphism to the function sending elements
Puzzle. Prove that if is cartesian, the functor preserves finite products.
In particular, this means that the terminal object has just one element, and the god-given function
is a bijection. (If you don’t see what this god-given function is, ask me; this function is part of the definition of ‘preserves finite product’.)
What more can we say if is cartesian closed? First, any morphism
can be turned into a morphism from to since there’s a god-given isomorphism Abusing language we’ll call this morphism
Then we can curry it, getting
This is an element of called the name of
So, any morphism gives an element This gives a nice link between the external hom and the internal hom: namely, the map
sending any morphism to its name! Moreover this map is a bijection, because currying is a bijection and so is the process that turns morphisms into morphisms
This may make it seem that the internal hom is exactly the same as the external hom. But no! We’ve just shown that elements of the internal hom (in the category-theoretic sense of ‘elements’) are in one-to-one correspondence with elements of the external hom (in the usual sense of ‘elements of a set’). But there’s more to an object than its elements!
To see this, it’s best to look at an example from last time.
The cartesian closed category of graphs
There’s a category that has two objects and , and just two morphisms
besides the identity morphisms. Last time we saw a presheaf on is just what category theorists call a graph: it consists of a set called the set of vertices and a set called the set of edges, along with functions
assigning to each edge its source and target.
The category of graphs, is a nice example of a cartesian closed category. It’s cartesian because every presheaf category has limits, including products. Furthermore, we know that products are computed ‘pointwise’. This means that the terminal object is the graph with one vertex and one edge: in general, terminal objects in presheaf categories have ‘one of each thing’. The product of two graphs and is a graph with
and similarly for the source and target functions. So a vertex in the product graph is just a pair of vertices, one in and one in , and similarly for edges.
Puzzle. Draw two graphs and draw their product.
We can figure out what morphisms of graphs are like, again using the fact that is a presheaf category. A morphism from the graph to the graph is just a natural transformation So, it consists of a function
sending each vertex of to a vertex of and a function
sending each edge of to an edge of But the naturality condition requires that some squares commute, one for each morphism in One of these commuting squares says that taking the source of an edge of and then mapping the result to is the same as first mapping that edge to and then taking its source:
The other commuting square says the same thing for targets:
So, a morphism of graphs is just what you’d hope it would be!
This lets us see why is cartesian closed, and what its exponentials are like. Say we have three graphs What is like? We use the fact that morphisms
must correspond naturally to morphisms
To get the most mileage out of this it’s best to take to be a very simple sort of graph, like the ‘walking vertex’ or the ‘walking edge’ (explained at the end of my last post). The walking vertex is a graph with just one vertex and no edges. If we take to be this, morphisms
are just vertices of We’d like to know what those vertices are! But by currying, we know they correspond in a one-to-one way with morphisms
Furthermore, we know is a graph with vertices corresponding to those of but no edges. (See why?) So, amounts to an arbitrary function sending vertices of to vertices of
So, a vertex of is a function sending vertices of to vertices of And we figured this out just by currying! This is a general trick.
Puzzle. Use a similar argument to show that an edge of is a map sending edges of to edges of together with two maps sending vertices to vertices, obeying a compatibility condition. For this it will help to use currying and take to be the ‘walking edge’: the graph with one edge and two vertices, namely its source and its target.
Puzzle. Figure out the source and target of any edge of
So, you can figure out what is like. Then you can do this:
Puzzle. Work out the set of elements of that is, the set of morphisms from the terminal graph to
Of course, we’ve already seen by a much more general argument that the elements of must correspond to graph morphisms from to But if you worked out what is like as a graph, you can solve the puzzle that way too and check that the answers agree!
Anyway, my main point here is that the internal hom knows more than the external hom The elements of are the same as elements of the set : they’re just graph morphisms from to But contains other information: for example, its vertices are arbitrary functions from the set of vertices of to the set of vertices of
Puzzle. Suppose is the walking vertex and is the graph with one vertex and one edge from that vertex to itself. Show that is the empty set, but is a nonempty graph.
Presheaf categories are cartesian closed
We can generalize some of these lessons to any presheaf category.
Theorem. Let be any small category. Then the presheaf category is cartesian closed.
This is Proposition 1 of Section I.6 in Mac Lane and Moerdijk’s book. The most interesting step is to determine for any two presheaves
what the internal hom should be. We’ve already gotten some practice doing this in the case of graphs, and the general case works similarly.
In the case of graphs the key was to use the bijection between morphisms
We focused on two particular choices of the walking vertex and the walking edge. These are fundamental because they are ‘representable’. Each object gives a presheaf called defined by
Presheaves isomorphic to these are called representable. Every object in a presheaf category is a colimit of representable presheaves—see Corollary 3 of Section I.5 for a proof. For example, the puzzle at the end last time asked you to show that every graph is a colimit of copies of the walking vertex and the walking edge. This is just a fancy way of saying that every graph is made of vertices and edges. But the point is that this idea generalizes! In any presheaf category, all objects are built from representables, and it’s always good to focus on the representables.
In general, to figure out we need to know its value on every object (We also need to know its value on every morphism, but hold your horses.) How do we do this? The Yoneda lemma gives an isomorphism
but the definition of ‘cartesian closed’ requires that
So, you might as well try defining on objects by
And this definition works just as well for morphisms: the Yoneda embedding gives a functor
so you can try defining
where you can now stick either an object or a morphism in the blank. (You can now release your horses.) It’s easy to see that defined this way, is a functor. So, the only thing we need to do is check that we really have a natural bijection between morphisms
You can try it yourself, or you can read Mac Lane and Moerdijk!
The series so far:
• Part 1: sheaves, elementary topoi, Grothendieck topoi and geometric morphisms.
• Part 2: turning presheaves into bundles and vice versa; turning sheaves into etale spaces and vice versa.
• Part 3: sheafification; the adjunction between presheaves and bundles.
• Part 4: direct and inverse images of sheaves.
• Part 5: why presheaf categories are elementary topoi: colimits and limits in presheaf categories.
• Part 6: why presheaf categories are elementary topoi: cartesian closed categories and why presheaf categories are cartesian closed.