Topos Theory (Part 6)

Persiflage 2020-02-10

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 $X$ and $Y$ there is a set $X + Y,$ their disjoint union, which acts like their sum in various ways; for example you get its cardinality by adding those of $X$ and $Y:$

$|X + Y| = |X + Y|$

The category of sets also has products: given two sets $X$ and $Y$ there is a set $X \times Y,$ their cartesian product, which obeys

$|X \times Y| = |X| \times |Y|$

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 $X$ to $Y$ is called $X^Y,$ and it has

$|X^Y| = |X|^{|Y|}$

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 $X \times Y$ to $Z$ and functions from $X$ to $Z^Y.$ A function

$f \colon X \times Y \to Z$

eats a pair $(x,y) \in X \times Y$ and spits out an element $f(x,y) \in Z.$ We can turn this into a function

$\tilde{f} \colon X \to Z^Y$

that eats an element $x$ and spits out a function from $Y$ to $Z,$ as follows:

$\tilde{f}(x)(y) = f(x,y)$

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 $f$ to $\tilde{f}$ 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

$\mathrm{hom}(X \times Y, Z) \cong \mathrm{hom}(X, Z^Y)$

More precisely, for any set $Y$ there’s a natural isomorphism

$\alpha \colon \mathrm{hom}(- \times Y, --) \stackrel{\sim}{\longrightarrow} \mathrm{hom}(-, {--}^Y)$

Here both sides are functors waiting to eat two sets (which I’d called $X$ and $Z$ 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 $X$ to the set $X \times Y$ has a right adjoint, namely the functor sending any set $Z$ to the set $Z^Y.$ In the usual way of category theorists we can abbreviate this by saying

$- \times Y \colon \mathsf{Set} \to \mathsf{Set}$

has a right adjoint,

$-^{Y} \colon \mathsf{Set} \to \mathsf{Set}$

We can generalize this idea to any category that has finite products. But first, a spiffy new name:

Definition. A category $\mathsf{C}$ is cartesian if it has finite products, or equivalently if it has binary products and a terminal object.

Definition. A category $\mathsf{C}$ is cartesian closed if it is cartesian and for any object $Y$ the functor

$- \times Y \colon \mathsf{C} \to \mathsf{C}$

has a right adjoint.

Of course in this situation we call the right adjoint

$-^{Y} \colon \mathsf{C} \to \mathsf{C}$

so for any objects $X,Y,Z \in \mathsf{C}$ there’s a natural one-to-one correspondence between morphisms

$f \colon X \times Y \to Z$

and morphisms

$\tilde{f} \colon X \to Z^Y$

It’s no surprise that taking $\mathsf{C} = \mathsf{Set}$ 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 $\mathrm{hom}(X,Y),$ which is a set, and $Y^X,$ which is an object of $\mathsf{C}.$

(Well, pedants may argue that $\mathsf{FinSet},$ 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 $\mathrm{hom}(X,Y)$ and $Y^X.$ We call $\mathrm{hom}(X,Y)$ the external hom and $Y^X$ the internal hom (or exponential). The idea is that the internal hom lives ‘inside’ the category $\mathsf{C},$ while $\mathrm{hom}(X,Y)$ lives ‘outside’ $\mathsf{C},$ 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 $X$ to be a morphism

$p \colon 1 \to X$

where $1$ is the terminal object (that is, our chosen terminal object: they’re all isomorphic). Any object has a set of elements. Furthermore any morphism

$f \colon X \to Y$

lets us turn elements of $X$ into elements of $Y,$ as follows: given an element

$p \colon 1 \to X$

we get an element

$f \circ p \colon 1 \to Y$

Puzzle. Prove that if $\mathsf{C}$ has a terminal object, there is a functor

$\mathrm{elt} \colon \mathsf{C} \to \mathsf{Set}$

sending each object to its set of elements and each morphism $f \colon X \to Y$ to the function sending elements

$p \colon 1 \to X$

to elements

$f \circ p \colon 1 \to Y.$

Puzzle. Prove that if $\mathsf{C}$ is cartesian, the functor $\mathrm{elt} \colon \mathsf{C} \to \mathsf{Set}$ preserves finite products.

In particular, this means that the terminal object $1 \in \mathsf{C}$ has just one element, and the god-given function

$\mathrm{elt}(X \times Y) \to \mathrm{elt}(X) \times \mathrm{elt}(Y)$

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 $\mathsf{C}$ is cartesian closed? First, any morphism

$f \colon X \to Y$

can be turned into a morphism from $1 \times X$ to $Y,$ since there’s a god-given isomorphism $1 \times X \cong X.$ Abusing language we’ll call this morphism

$f \colon X \times 1 \to Y$

Then we can curry it, getting

$\tilde{f} \colon 1 \to Y^X$

This is an element of $Y^X,$ called the name of $f.$

So, any morphism $f \in \mathrm{hom}(X,Y)$ gives an element $\widetilde{f} \in \mathrm{elt}(Y^X).$ This gives a nice link between the external hom and the internal hom: namely, the map

$\begin{array}{ccc} \mathrm{hom}(X,Y) &\to& \mathrm{elt}(Y^X) \\ f &\to& \tilde{f} \end{array}$

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 $X \to Y$ into morphisms $X \times 1 \to Y.$

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 $\mathsf{G}$ that has two objects $v$ and $e$ , and just two morphisms

$s, t \colon v \to e$

besides the identity morphisms. Last time we saw a presheaf on $\mathsf{G}$ is just what category theorists call a graph: it consists of a set $V = F(v)$ called the set of vertices and a set $E = F(e)$ called the set of edges, along with functions

$F(s) \colon E \to V$

$F(t) \colon E \to V$

assigning to each edge its source and target.

The category of graphs, $\widehat{\mathsf{G}},$ 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 $F$ and $G$ is a graph with

$(F \times G)(v) = F(v) \times G(v)$

$(F \times G)(e) = F(e) \times G(e)$

and similarly for the source and target functions. So a vertex in the product graph is just a pair of vertices, one in $F$ and one in $G$ , 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 $\widehat{\mathsf{G}}$ is a presheaf category. A morphism from the graph $F$ to the graph $G$ is just a natural transformation $\alpha \colon F \Rightarrow G.$ So, it consists of a function

$\alpha_v \colon F(v) \to G(v)$

sending each vertex of $F$ to a vertex of $G,$ and a function

$\alpha_e \colon F(e) \to G(e)$

sending each edge of $F$ to an edge of $G.$ But the naturality condition requires that some squares commute, one for each morphism in $\mathsf{G}.$ One of these commuting squares says that taking the source of an edge of $F$ and then mapping the result to $G$ is the same as first mapping that edge to $G$ and then taking its source:

$\alpha_v \circ F(s) = G(s) \circ \alpha_e$

The other commuting square says the same thing for targets:

$\alpha_v \circ F(t) = G(t) \circ \alpha_e$

So, a morphism of graphs is just what you’d hope it would be!

This lets us see why $\mathsf{G}$ is cartesian closed, and what its exponentials are like. Say we have three graphs $F,G,H.$ What is $H^G$ like? We use the fact that morphisms

$\alpha \colon F \to H^G$

must correspond naturally to morphisms

$\tilde{\alpha} \colon F \times G \to H$

To get the most mileage out of this it’s best to take $F$ 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 $F$ to be this, morphisms

$\alpha \colon F \to H^G$

are just vertices of $H^G.$ We’d like to know what those vertices are! But by currying, we know they correspond in a one-to-one way with morphisms

$\tilde{\alpha} \colon F \times G \to H$

Furthermore, we know $F \times G$ is a graph with vertices corresponding to those of $G,$ but no edges. (See why?) So, $\widetilde{\alpha}$ amounts to an arbitrary function sending vertices of $G$ to vertices of $H.$

So, a vertex of $H^G$ is a function sending vertices of $G$ to vertices of $H.$ And we figured this out just by currying! This is a general trick.

Puzzle. Use a similar argument to show that an edge of $H^G$ is a map sending edges of $G$ to edges of $H,$ together with two maps sending vertices to vertices, obeying a compatibility condition. For this it will help to use currying and take $F$ 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 $H^G.$

So, you can figure out what $H^G$ is like. Then you can do this:

Puzzle. Work out the set of elements of $H^G,$ that is, the set of morphisms from the terminal graph to $H^G.$

Of course, we’ve already seen by a much more general argument that the elements of $H^G$ must correspond to graph morphisms from $G$ to $H.$ But if you worked out what $H^G$ 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 $H^G$ knows more than the external hom $\mathrm{hom}(G,H).$ The elements of $H^G$ are the same as elements of the set $\mathrm{hom}(G,H)$ : they’re just graph morphisms from $G$ to $H.$ But $H^G$ contains other information: for example, its vertices are arbitrary functions from the set of vertices of $G$ to the set of vertices of $H.$

Puzzle. Suppose $H$ is the walking vertex and $G$ is the graph with one vertex and one edge from that vertex to itself. Show that $\mathrm{hom}(G,H)$ is the empty set, but $H^G$ is a nonempty graph.

Presheaf categories are cartesian closed

We can generalize some of these lessons to any presheaf category.

Theorem. Let $\mathsf{C}$ be any small category. Then the presheaf category $\widehat{\mathsf{C}}$ 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

$G, H \colon \mathsf{C} \to \mathrm{Set}$

what the internal hom $H^G$ 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

$\alpha \colon F \to H^G$

and morphisms

$\tilde{\alpha} \colon F \times G \to H$

We focused on two particular choices of $F,$ the walking vertex and the walking edge. These are fundamental because they are ‘representable’. Each object $X \in \mathsf{C}$ gives a presheaf called $y(X),$ defined by

$y(X)(-) = \mathrm{hom}(-,X)$

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 $H^G$ we need to know its value $H^G(X)$ on every object $X \in \mathsf{C}.$ (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

$H^G(X) \cong \mathrm{hom}(y(X),H^G)$

but the definition of ‘cartesian closed’ requires that

$\mathrm{hom}(y(X),H^G) \cong \mathrm{hom}(y(X) \times G, H)$

So, you might as well try defining $H^G$ on objects by

$H^G(X) = \mathrm{hom}(y(X) \times G, H)$

And this definition works just as well for morphisms: the Yoneda embedding gives a functor

$y \colon \mathsf{C} \to \widehat{\mathsf{C}}$

so you can try defining

$H^G(-) = \mathrm{hom}(y(-) \times G, H)$

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 $H^G,$ 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

$\alpha \colon F \to H^G$

and morphisms

$\tilde{\alpha} \colon F \times G \to H$

You can try it yourself, or you can read Mac Lane and Moerdijk!