Topos Theory (Part 8)

Persiflage 2020-02-28

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

$\mathsf{Set}^{\mathsf{N}}$

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.

Representables

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.

Subobjects

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.