Topos Theory (Part 6)

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 Y^X, and it has

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

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!

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.

This entry was posted on Tuesday, February 11th, 2020 at 12:03 am and is filed under mathematics. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

13 Responses to Topos Theory (Part 6)

  1. Toby Bartels says:
    11 February, 2020 at 1:20 am

    |X + Y| = |X + Y|

    This should be |X + Y| = |X| + |Y|.

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

    Reply
  2. Avi Levy says:
    11 February, 2020 at 4:59 am

    “the set of all functions from X to Y is called X^Y” should be “the set of all functions from Y to X is called X^Y“, for instance \mathbb R^{\mathbb N} is the set of functions from \mathbb N to \mathbb R and not the other way around.

    Reply
  3. Peter Morgan says:
    11 February, 2020 at 4:39 pm

    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.

    Reply
  4. Keith Harbaugh says:
    12 February, 2020 at 4:35 pm

    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. [X,Y], rather than using the exponential notation ? (Hope I got that latex right :-)

    Reply
    • Todd Trimble says:
      13 February, 2020 at 1:23 am

      I would agree with using [X, Y] for general closed monoidal categories. But I’d say Y^X captures the right intuitions to have for cartesian closed categories. Indeed, the canonical isomorphisms (Y \times Z)^X \cong Y^X \times Z^X and Z^{X + Y} \cong Z^X \times Z^Y (in cases where coproducts exist) and Z^{Y \times X} \cong (Z^Y)^X are the correct categorifications of the familiar exponential laws.

      Reply
    • John Baez says:
      13 February, 2020 at 6:47 pm

      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

      X \Rightarrow Y

      (perhaps with some other kind of arrow) to mean the object of maps from X to Y. 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 Y^X to mean the object of maps from X to Y.

      Reply
      • Toby Bartels says:
        13 February, 2020 at 10:05 pm

        The arrow notation is good for any closed category; it emphasizes that X \to Y consists of maps from X to Y. Although it might be good to decorate the arrow whenever the closed category is non-cartesian. For example, in a category of vector spaces, X \to Y consists of the linear transformations from X to Y, so maybe the notation should reflect that.

        Reply
      • Keith Harbaugh says:
        14 February, 2020 at 4:25 pm

        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., f:X \to Y 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.

        Reply
        • Toby Bartels says:
          14 February, 2020 at 8:21 pm

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

          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 g \circ f, then you can write it as g ( f ) instead when f is being thought of as an element. Then if you have f \colon X \to Y and later write g \circ f, then g must be a morphism with domain Y and this is ordinary composition; while if you write g ( f ), then g must be a morphism with domain X \to Y and this is really the composite of g with the name \tilde f of f.

          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 A of a closed category and the underlying set of A (the set of elements of A, or the hom-set from 1 to A). And more generally, we don't distinguish between an internal hom-set and an external hom-set. This means that \mathrm {hom} ( X , Y ) is conflated with [ X , Y ], which is conflated with \mathrm { hom } ( 1 , [ X , Y ] ); all of these are called the object of morphisms from X to Y (say, the vector space of linear transformations from X to Y, to be concrete). So the complicated notation of the previous paragraph recreates ordinary mathematical practice.

  5. Keith Harbaugh says:
    12 February, 2020 at 4:43 pm

    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

    Reply

You can use Markdown or HTML in your comments. You can also use LaTeX, like this: $latex E = m c^2 $. The word 'latex' comes right after the first dollar sign, with a space after it.

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out /  Change )

Google photo

You are commenting using your Google account. ( Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. ( Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. ( Log Out /  Change )

Cancel

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.