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

and 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

to 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

and 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

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

• Part 7: why presheaf categories are elementary topoi: subobjects and subobject classifiers, and why presheaf categories have a subobject classifier.

• Part 8: an example: the topos of time-dependent sets, and its subobject classifier.

This should be .

Readers unfamiliar with the disjoint union can think of as , although it may be better to think of it as its own independent concept: a copy of and a completely separate copy of . This is especially important to grasp when and are the same set; may be , but (which you may think of as ) consists of two separate copies of .

Thanks, I’ll fix that typo.

“the set of all functions from to is called ” should be “the set of all functions from to is called “, for instance is the set of functions from to and not the other way around.

Yes, I’ll fix it.

Thank you for explaining the “currying” operation so clearly. Now I know that’s what I do with the multiplication and Poisson bracket operations to construct a noncommutative algebra of unary operators acting on phase space functions in my “An Algebraic Approach to Koopman Classical Mechanics”. Of course I just did it without knowing it has a name.

I know you’re trying to keep this streamlined, but even so would it not be a good idea to observe, somewhere in the document, that it is common, notably in Max Kelly’s work on enriched cat theory, to denote the internal hom with square brackets, e.g. , rather than using the exponential notation ? (Hope I got that latex right :-)

I would agree with using for general closed monoidal categories. But I’d say captures the right intuitions to have for

cartesianclosed categories. Indeed, the canonical isomorphisms and (in cases where coproducts exist) and are the correct categorifications of the familiar exponential laws.In my post I’m sticking tightly to Mac Lane and Moerdijk’s notation and not discussing anything else. But it’s great to talk about stuff in comments!

Another notation for exponentials in the cartesian closed case is

(perhaps with some other kind of arrow) to mean the object of maps from to . This seems to be especially popular in computer science. It’s good when you have exponentials of exponentials of exponentials… so the notation doesn’t climb up the page. It’s also nice how it avoids the ‘backwards’ quality of using to mean the object of maps from to

The arrow notation is good for any closed category; it emphasizes that consists of maps from to . Although it might be good to

decoratethe arrow whenever the closed category is non-cartesian. For example, in a category of vector spaces, consists of thelineartransformations from to , so maybe the notation should reflect that.To both John and Toby:

How do people using the arrow notation for the internal hom distinguish that from

a specific arrow between the designated pair of objects,

i.e., an element of the external hom?

The lack of a label, e.g., for a specific, named, arrow versus the same without the label?

In general, I find Kelly’s treatment of all this in Chapter 1 of BCECT the best approach for me.

You can use different styles of arrows; for example, you wrote , while John wrote . You can also tell by context; if there's a colon before , then this means that the symbol in front of the colon is a morphism from to , while otherwise is the internal hom object. Or you can embrace the ambiguity, and say that is allowed for

anyobject and means that is an element of .This last option conflates a morphism with its name, so that kicks the ambiguity down the road. You could resolve this by having different notation for a morphism generally than for a morphism thought of as an element. For example, if you normally write composition as , then you can write it as instead when is being thought of as an element. Then if you have and later write , then must be a morphism with domain and this is ordinary composition; while if you write , then must be a morphism with domain and this is really the composite of with the name of .

This may seem more trouble than it's worth, but it's actually extremely common! In ordinary mathematics, we often fail to distinguish between an object of a closed category and the underlying set of (the set of elements of , or the hom-set from to ). And more generally, we don't distinguish between an internal hom-set and an external hom-set. This means that is conflated with , which is conflated with ; all of these are called the object of morphisms from to (say, the vector space of linear transformations from to , to be concrete). So the complicated notation of the previous paragraph recreates ordinary mathematical practice.

Also, BTW, nLab has a very nice page on the cart. closed structure on presheaves:

https://ncatlab.org/nlab/show/closed+monoidal+structure+on+presheaves

Thanks, that’s a nice page!