Topos Theory (Part 7)

Azimuth 2020-02-18

I’m almost done 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 explained why such categories are cartesian closed; now let’s talk about the subobject classifier!

Subobject classifiers

In the category of sets, 0-element and 1-element sets play special roles. The 0-element set is the initial object, and any 1-element set is a terminal object. But 2-element sets are also special! They let us talk about ‘truth values’.

We can take any such set, call it 2, and call its elements ‘true’ and ‘false’. Then subsets of any set $X$ correspond in a one-to-one way with functions

$\chi \colon X \to 2$

by associating to any subset $S \subseteq X$ the function taking the value ‘true’ on $S$ and ‘false’ elsewhere: its characteristic function.

The idea of a subobject classifier is simply to copy this idea in other categories. A subobject classifier, which we’ll call $\Omega,$ will serve as an ‘object of truth values’ in the category at hand. To make this precise, we’ll demand that subobjects of any object $X$ correspond bijectively to morphisms $\chi \colon X \to \Omega.$

That’s the idea. But to make the idea useful we need to say how subobjects of $X$ correspond to morphisms $\chi \colon X \to \Omega.$ And of course before that we’ll need to say exactly what a subobject is!

In $\mathsf{Set}$ we can pick out a subset of $X$ using a monomorphism $i \colon S \rightarrowtail X,$ where I use the funny arrow to denote a monomorphism (affectionately known as a ‘mono’). The idea is that the image of $i$ is the subset of $X$ we care about. But two different monos can have the same image, so we have to be careful!

Suppose we have two different monos

$i \colon S \rightarrowtail X$

and

$i' \colon S' \rightarrowtail X$

in $\mathsf{Set}.$ When do they have the same image? The answer is: precisely when there’s an isomorphism

$f \colon S \to S'$

such that

$i = i' \circ f.$

Puzzle. Prove this.

So, more generally, in any category, we shall say that two monos $i \colon S \rightarrowtail X$ and $i' \colon S' \rightarrowtail X$ are isomorphic iff there’s an isomorphism $f \colon S \to S'$ such that $i = i' \circ f.$

Definition. A subobject of an object $X$ in a category $C$ is an isomorphism class of monos into $X,$

We will eventually study subobjects to see how much they behave like subsets—there’s a lot to say about that! But first let’s see what a subobject classifier is.

Again we return to the category $\mathsf{Set}$ to see how this should work. We need to know how subobjects of $X \in \mathsf{Set}$ arise from functions $\chi \colon X \to 2.$ For this we need to know which elements of $X$ get mapped by $\chi$ to ‘true’, so we need to specify which element of the set $2$ counts as ‘true’. We do this using a function

$\mathrm{true} \colon 1 \rightarrowtail 2$

which of course is a mono. Then, given any function

$\chi \colon X \to 2$

we can take the pullback of $f$ along $\mathrm{true}$ and get a mono

$i \colon S \rightarrowtail X$

Please see diagram (2) in Section I.3 of Mac Lane and Moerdijk to see this pullback in all its glory.

The usual description of pullbacks in $\mathsf{Set}$ assures us that

$S \cong \{x \in X : \; \chi(x) = \mathrm{true} \}$

and the map $i \colon S \rightarrowtail X$ is the obvious inclusion.

We can copy this procedure in any category with pullbacks, leading to the definition we seek:

Definition. Let $\mathsf{C}$ be a category with pullbacks. A subobject classifier is an object $\Omega \in \mathsf{C}$ equipped with a mono

$\mathrm{true} \colon 1 \rightarrowtail \Omega$

such that for any object $X \in \mathsf{C}$ there is a bijection between morphisms

$\chi \colon X \to \Omega$

and subobjects of $X,$ given as follows: for any such morphism $\chi$ , we pull back $\mathrm{true}$ along $\chi$ obtaining a mono

$i \colon S \rightarrowtail X$

and then take the subobject of $X$ corresponding to this.

Here we are using a fact:

Puzzle. Show that the pullback of any mono is a mono.

Thus, $i$ is automatically a mono, because we are assuming $\mathrm{true}$ is.

Subobjects in presheaf categories

Let’s see what subobjects and subobject classifiers look like in presheaf categories. So now let $\mathsf{C}$ be any category and let

$\widehat{\mathsf{C}} = \mathsf{Set}^{\mathsf{C}^{\mathrm{op}}}$

be the category of presheaves on $\mathsf{C}.$

To get started: what are monos in $\widehat{\mathsf{C}}$ like? Remember from Part 5 pullbacks are computed pointwise in presheaf categories. Furthermore, monos can be defined in terms of pullbacks:

Puzzle. Show that a morphism $f \colon X \to Y$ is a mono iff its pullback along itself is the identity $1 \colon X \to X.$

This implies that determining whether a morphism in $\widehat{\mathsf{C}}$ is a mono must also be a ‘pointwise’ matter: that is, one that you can check by looking at one object $c \in \mathsf{C}$ at a time. But you can prove this directly:

Puzzle. Let $i \colon F \Rightarrow G$ be a morphism between presheaves $F , G \in \widehat{\mathsf{C}},$ that is, a natural transformation between functors $F, G \colon \mathsf{C}^{\mathrm{op}} \to \mathsf{Set}.$ Show that $i$ is a mono iff for each $c \in \mathsf{C},$

$i_c \colon F(c) \to G(c)$

is a mono in $\mathsf{Set},$ that is, a one-to-one function.

Thus, people say a morphism of presheaves $i \colon F \to G$ makes $F$ into a subpresheaf of $G$ when each function $i_c \colon F(c) \to G(c)$ is one-to-one, so $F(c)$ corresponds to a subset of $G(c).$ It’s good to look at this in examples, like the case of graphs, where we get the concept of ‘subgraph’: one graph included in another.

Of course, we should remember that a subobject of $G$ really an equivalence class of monos. Two different monos $i \colon F \rightarrowtail G$ and $i \colon F' \rightarrowtail G$ give the same subobject of $G$ if there’s an isomorphism between $F$ and $G$ that makes the obvious triangle commute. But sometimes people slack off and say $F$ is a subobject of $G$ if it’s equipped with a mono $i \colon F \rightarrowtail G.$ I was coming close to doing that in the last paragraph.

Subobject classifiers in presheaf categories

Now we’re ready to understand the subobject classifier in a presheaf category. I’ll just tell you what it is. The subobject classifier in the presheaf category $\widehat{\mathsf{C}}$ assigns to each object $c \in \mathsf{C}$ the set of ‘sieves’ on $c.$ So what’s a sieve?

Definition. Given a category $\mathsf{C},$ , a sieve on an object $c \in \mathsf{C}$ is a collection of morphisms to $c$ such that if $f \colon d \to c$ is in the sieve and $g \colon d' \to d$ is any morphism, then $f \circ g \colon d'\to c$ is in the sieve.

In other words, a sieve is a collection of morphisms with a fixed target that’s closed under precomposition. The name ‘sieve’ should remind you that if a piece of grain can get through a sieve, any smaller piece of grain can also get through. You can think of $f \circ g$ as ‘smaller’ than $f$ in some sense.

Here’s a slick way to think about sieves. Remember that the Yoneda embedding

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

sends any object $c \in \mathsf{C}$ to a presheaf

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

called a representable presheaf.

Here’s the cool fact: a sieve on $c$ is just the same as a subobject of $y(c)!$ For each object $d$ it gives a subset of $\mathsf{hom}(d,c),$ and for each morphism $g \colon d' \to d$ it gives a map from $\mathsf{hom}(d,c)$ to $\mathsf{hom}(d',c),$ namely the map sending each $f$ to $f \circ g.$

The subobject classifier $\Omega$ in $\widehat{\mathsf{C}}$ is a beautiful thing: it assigns to each object the set of all sieves on that object!

That is, for each object $c \in \mathsf{C},$ the set $\Omega(c)$ is the set of all sieves on $c.$ But we also need to say what $\Omega$ does to morphisms. Given a morphism $f \colon c' \to c,$ the map

$\Omega(f) \colon \Omega(c) \to \Omega(c')$

sends sieves on $c$ to sieves on $c'$ as follows. For any sieve $S$ on $c,$ we say a morphism is in $\Omega(f)(S)$ if its composite with $f$ is in $S.$

We also need to describe

$\mathrm{true} \colon 1 \to \Omega$

A terminal presheaf $1$ sends each object of $\mathsf{C}$ to a one-element set, so $\mathrm{true}$ must pick out an element of $\Omega(c)$ for each object $c \in \mathsf{C}$ in a natural way (it’s a natural transformation.)

In other words, $\mathrm{true}$ must choose a sieve on $c$ for each $c \in \mathsf{C}$ in a natural way. The naturality condition here says that if $g \colon c' \to c,$ a morphism is in the chosen sieve on $c'$ iff its composite with $g$ is in the chosen sieve on $c.$

How does $\mathrm{true}$ do this wonderful thing? Simple: for each object $c$ it chooses the sieve containing all morphisms to $c.$ Then the naturality condition holds trivially.

Of course, we have to check that

$\mathrm{true} \colon 1 \to \Omega$

really is a subobject classifier for $\widehat{\mathsf{C}}.$ Only this will let us really understand what we’ve done here.

I’ll talk about this more next time, perhaps focusing on examples to build up intuition. For now I recommend that you read Section I.4 of Mac Lane and Moerdijk’s book for a general proof—and also a look at some examples!