Topos Theory (Part 8)

Let’s look at an example of a presheaf topos, to see what various things I’ve been talking about actually look like—especially the subobject classifier.

Our example will illustrate the connection between topos theory and intuitionistic logic: that is, logic where the law of excluded middle, “p or not p”, fails. Intuitionistic logic goes back to Brouwer, who happens to have been born this very day in 1881. Topos theory formalizes intuitionistic logic in a way he might not have liked. But it does roughly capture some of his thoughts about how mathematics is an activity that happens in time.

The subobject classifier in the category of sets is the 2-element set

\{\mathrm{true}, \mathrm{false}\}

and it’s a Boolean algebra with the usual operations of logic. But the subobject classifier in a topos is usually more complicated. It can have more than 2 elements. Of course, it’s not just a set, it’s an object in a topos—but remember, an object of a topos still has a set of ‘elements’. The subobject classifier is usually not a Boolean algebra: it’s something more general called an internal Heyting algebra, where the law of excluded middle may not hold. When that happens, logic inside the topos is intuitionistic.

We’re not really ready to talk about internal Heyting algebras, but we are ready to see a topos with an interesting subobject classifier.

Time-dependent sets

Let’s imagine a world where sets are ‘time-dependent’, but in the following special way. As time passes, a set can get new elements as we learn more about it. We can also learn new equations between elements, so elements that were previously distinct can merge. But we never think an element is in a set and then discover it’s not, and we never think two elements are equal and then discover they’re not.

You can think of this as a naive model of an infallible mathematician proving more and more as time goes by.

To keep things simple, let’s suppose that time starts at zero and proceeds in steps. So, our set of times will be the natural numbers. Let’s think of the the natural numbers with their usual ordering as a category. We get a category \mathsf{N} where the objects are natural numbers and there’s one morphism from n to m if n \le m, and none otherwise. We’ll write

i_{n,m} \colon n \to m

for the unique morphism from n to m when n \le m. Note that all these morphisms are composites of those of the form i_{n,n+1}.

Our topos will consist of presheaves on \mathsf{N}^{\mathrm{op}}. Of course the definition of presheaf also also involves an ‘op’, so the two ops cancel and our topos is


The double ‘op’ is somewhat annoying when you’re first trying to find your footing, but such is life.

What’s an object of \mathsf{Set}^{\mathsf{N}} like? It consists of a set X(n) and a map

X(i_{n,n+1}) \colon X(n) \to X(n+1)

for each natural number n. As time passes, new elements can appear. That is, X(n+1) can have elements that aren’t in the image of f_n. Elements can merge. That is, X(i_{n,n+1}) can map two elements of X(n) to the same element of X_{n+1}. But elements can’t ‘disappear’ or ‘split’.

You should draw such a thing. In class I drew it as something like an ‘infinitely deep tree’ where we move down the tree as time passes. Newly appearing elements are leaves, and branches can merge as we move down the tree. It doesn’t have a root—it keeps going down forever! Also, it’s not necessarily connected. So, we could call it an ‘infinitely deep forest’: a disjoint union of infinitely deep trees. You can imagine a surreal sort of rainforest that keeps going down forever.


What’s a representable object of \mathsf{Set}^{\mathsf{N}} like? Thanks to the annoying ‘op’ business, a representable object is a functor of the form

\mathrm{hom}(n, -) \colon \mathsf{N} \to\ \mathsf{Set}

So, \mathrm{hom}(n, m) is empty for m < n and it has one element for m \ge n. We can say it's a time-dependent set with a single element, `discovered at time n’. In terms of our rainforest imagery, it looks like a very skinny infinitely deep tree with no branches—sort of like a telephone pole.

The Yoneda lemma, or one of its offshoots, says that every object in \mathsf{Set}^{\mathsf{N}} is a colimit of representables. See Proposition 1 in Section I.5 for details. In terms of our pictures, this means that any rainforest can be built from telephone poles.

How does that work, exactly? The colimit of any diagram can be built by first taking the coproduct of every object in the diagram and then taking a coequalizer that forces all the necessary triangles to commute. So, we should think about first taking a coproduct of representables, and then a coequalizer.

A coproduct acts like a 'disjoint union'. So, a coproduct of representables can be visualized as a disjoint union of telephone poles of various heights. Note that in this sort of time-dependent set elements can appear but never merge.

Puzzle. Show that X \in \mathsf{Set}^{\mathsf{N}} is a coproduct of representables if and only if all the maps

X(i_{n,n+1}) \colon X(n) \to X(n+1)

are injections.

We can take a coequalizer to ‘glue together’ telephone poles and get more interesting infinitely deep trees… or indeed, infinitely deep forests.

Puzzle. Let X \in \mathsf{Set}^{\mathsf{N}} be a time-dependent set with 2 elements at time 0 and 1 element at all later times. Show how to build X by taking a coproduct of two representables and then taking a coequalizer.

In terms of pictures, we are taking two telephone poles and gluing them together except at the very top, getting an infinitely deep tree that branches at the top.


What’s a subobject of an object X \in \mathsf{Set}^{\mathsf{N}} like? By definition it’s an equivalence class of monomorphisms into X. I explained the equivalence relation last time. But we can work out what all this amounts to:

Puzzle. Show that a subobject of X \in \mathsf{Set}^{\mathsf{N}} is the same as a subset S(n) \subseteq X(n) for each natural number n such that S(n) is mapped into S(n+1) by the map

X(i_{n,n+1}) \colon X(n) \to X(n+1).

Puzzle. Draw an object of \mathsf{Set}^{\mathsf{N}} together with a subobject.

I would draw an ‘infinitely deep forest’ in green and then draw a ‘subforest’, maybe shading it in brown. As we follow any branch down, it can enter the subforest and change from green to brown. It can then never turn green again as you go further down.

In other words: at any time you can learn that an element of your time-dependent set \mathsf{S} is in some time-dependent subset \mathsf{T}. But once you learn it’s in, you know this for the rest of time!

This suggests that in this topos, the truth values are not merely ‘true’ and ‘false’. For each n there should be a truth value ‘becomes true at time n‘. And there should be a truth value ‘never becomes true’—or in other words, ‘false’.

The subobject classifier

Now let’s systematically study the subobject classifier of \mathsf{Set}^{\mathsf{N}}. We saw last time how to determine the subobject classifier in any presheaf category, though I didn’t explain why this procedure actually works. Let’s apply the procedure in our example here to get some intuition for it.

Last time I claimed that the subobject classifier in a presheaf topos \mathsf{Set}^{\mathsf{C}^{\textrm{op}}} is a presheaf

\Omega \colon \mathsf{C}^{\textrm{op}} \to \mathsf{Set}

that sends any object c to the set of all sieves on c. Remember, a sieve on c is a collection of morphisms with target c that’s closed under precomposition.

So, let’s start by seeing what this means in our example. The annoying ‘op’ comes in now, because our category \mathsf{Set}^{\mathsf{N}} is the category of presheaves on \mathsf{N}^{\mathrm{op}}. By definition, a sieve on n is a collection of morphisms in \mathsf{N}^{\mathrm{op}} with target n that is closed under precomposition. So, in terms of the category\mathsf{N}, a sieve is a collection of morphisms with source n that’s closed under postcomposition.

For each natural number i there’s a sieve on n consisting of all the morphisms from n to the objects n+i, n+i+1, n+i+2, \dots. Clearly this is closed under postcomposition. Let’s call this sieve t_i.

There’s also another sieve on n, namely the empty sieve: the sieve with no morphisms at all. Let’s call this sieve t_\infty.

Puzzle. Show that all the sieves on n are those of the form t_0, t_1, t_2, \dots together with t_\infty.

Thus, we know this about the subobject classifier:

\Omega(n) = \{t_0, t_1, t_2, \dots, t_\infty\}

We’ll see that t_0 means ‘true now’, t_1 means ‘true tomorrow’, t_2 means ‘true the next day’, and so on… while t_\infty means ‘never true’— or in other words, false. Mac Lane and Moerdijk call the subscript i in t_i the ‘time to truth’. It’s how long you have to wait for something to become true.

So we’ve seen what \Omega does to objects of \mathsf{N}. But what does it do to morphisms?

We can guess: if something is true in i days now, tomorrow it will be true in i - 1 days, or in 0 days if i - 1 = -1. And of course if it’s never true now, it will never be true tomorrow.

Let’s check this.

Suppose S is any sieve on n. Then \Omega(i_{n,m})S is a sieve on m, and a morphism is in this sieve iff its composite with i_{n,m} is in S. This follows from the general description I gave last time.

Puzzle. Show that

\Omega(i_{n,n+1}) \colon \Omega(n) \to \Omega(n+1)

maps t_i to t_{i-1} if i - 1 \ge 0, and to t_0 otherwise. (Here we say that infinity minus any natural number is still infinity.)

So, our idea is working!

Now you know enough to draw the subobject classifier. If you draw it as an infinitely deep forest, it has infinitely many leaves on top, where n = 0. These are t_0, t_1, t_2, \dots, t_\infty. As we follow these down to n = 1, the t_1 branch merges with the t_0 branch, while the other branches get renamed: t_2 gets renamed t_1, t_3 gets renamed t_2, and so on. But not all the branches get renamed! The t_\infty branch is still called t_\infty.

As we continue to go down, the same thing keeps happening forever.

Puzzle. How many connected components does this infinitely deep forest have?

Next: a subobject classifier \Omega in a topos needs to be equipped with an element

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

What is this in our example? We can guess. ‘True’ should mean true now. The terminal time-dependent set 1 has one element for each time n. So, \mathrm{true} should map this one element to t_0 \in \Omega(n).

Now you can check this guess:

Puzzle. Show that for any time-dependent set X, morphisms

\chi \colon X \to \Omega

correspond in a one-to-one way with subobjects of X.

One nice way to start tackling this problem is to draw a time-dependent set X and a subobject of it, say S. Next to these draw \Omega. Then figure out which choice of \chi \colon X \to \Omega sends precisely the elements of S to t_0.

That will help you see how subobjects determine morphisms to \Omega. But morphisms to \Omega should also determine subobjects! For this, draw a time-dependent set and a morphism from it to \Omega. Show that the elements that get mapped to t_0 form a subobject of X.

Once you’ve done this, you’ll be ready to give a more formal argument:

Puzzle. Show that for any X \in \mathsf{Set}^{\mathsf{N}} 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.

When you do this, it means you understand the subobject classifier in the topos of time-dependent sets! You may understand it now… but if not, maybe you’ll understand it tomorrow, or the next day.

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.

4 Responses to Topos Theory (Part 8)

  1. Christopher Upshaw says:

    Just wanted to say I am super enjoying this series of posts!

  2. John Baez says:

    Thanks! I didn’t quite get to my goal.

  3. Luke Sciarappa says:

    The subobject classifier of the category of quivers (already discussed in this series) is another good one to work through when learning about this stuff. You can use the characterization by sieves, but you can also think about it as subobjects of representables directly—remembering that it all works because of the isomorphisms

    \Omega(X) \cong \mathrm{Hom}(y(X), \Omega) \cong \mathrm{Sub}(y(X)),

    where X is e, v, s, or t to figure out the corresponding aspect of \Omega. arXiv:math/0306394 walks through it all, though you might consider that to be a “spoiler” relative to figuring things out yourself.

  4. John Baez says:

    This is another spoiler, maybe:

    I forget where I got this image!

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: Logo

You are commenting using your 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 )

Connecting to %s

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