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 cartesian closed 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 decorate the arrow whenever the closed category is non-cartesian. For example, in a category of vector spaces,
consists of the linear transformations from
to
, so maybe the notation should reflect that.
To both John and Toby:
for a specific, named, arrow versus the same without the label?
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.,
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 any object
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!