Understanding an example of a subobject classifier.

Question

In Turi's Category Theory Lecture Notes the following definition is given.

Definition: A subobject classifier for a category $\mathbb{C}$ with finite limits consists of an object $\Omega$ (of $\mathbb{C}$) and a monic arrow $\operatorname{true}:1\rightarrowtail\Omega$ universal is the sense that for every monic $S\rightarrowtail X$ there exists a unique arrow $\phi_{S}:X\to\Omega$ such that

is a pullback square.

That's all well and good: I've worked through an exercise for the two element set in Set just fine.

My problem is with understanding the example given soon after the above. I can't find it anywhere online.

[S]ets over time $\mathbf{X: \omega}\to$ Set have a subobject classifier which gives "time till truth": it is the constant presheaf $$\mathbb{N}_{\infty}\stackrel{p}{\to}\mathbb{N}_{\infty}\stackrel{p}{\to}\mathbb{N}_{\infty}\stackrel{p}{\to}\dots$$ where $\mathbb{N}_{\infty}$ is the set of natural numbers with infinity and $p$ is the predecessor function (mapping $n+1$ to $n$, while leaving $0$ and $\infty$ unchanged). Then $0$ is $\operatorname{true}$, $n$ is '$n$ steps till truth', and $\infty$ is 'never true'.

Thoughts: Yeah, I'm completely lost here. (I think) I know what a presheaf is but I don't understand the "sets over time" part nor how that "constant presheaf" is an example of a subobject classifier. [Is $\Omega =\mathbb{N}_{\infty}$ in this case?]

Please help :)

Answer 1

Let $\Omega = (\mathbb{N}_{\infty} \xrightarrow{p} \mathbb{N}_{\infty} \xrightarrow{p} \dotsc)$ be as described.

Let $S \subseteq X$ be a subobject, thus we have a bunch of compatible injections $S_i \to X_i$. Compatibility means that the diagrams $$\begin{array}{c} X_i & \rightarrow & X_{i+1} \\ \downarrow && \downarrow \\ S_i & \rightarrow & S_{i+1} \end{array}$$ commute.

Define $\phi : X \to \Omega$ as follows: If $i \in \mathbb{N}$, we want to define $\phi_i : X_i \to \Omega_i = \mathbb{N}_{\infty}$. Well, if $x \in X_i$, then there are three cases:

1. $x \in S_i$ (by which I mean that $x$ lies in the image of $S_i \to X_i$). Then $\phi_i(x):=0$.

2. More generally, assume that the image of $x$ in $X_{i+n}$ lies in $S_{i+n}$ for some $n \geq 0$. Choose $n$ minimal. Then $\phi_i(x) := n$.

3. Otherwise, we define $\phi_i(x) := \infty$.

By the very construction, the diagram

$$\begin{array}{c} X_i & \rightarrow & X_{i+1} \\ \phi_i \downarrow ~~~~ && ~~~~ \downarrow \phi_{i+1} \\ \mathbb{N}_\infty & \xrightarrow{p} & \mathbb{N}_\infty \end{array}$$

commutes, i.e. $\phi : X \to \Omega$ is a morphism. One can also check that we have a pullback diagram, as desired.

Answer 2

I don't know how much you know about Grothendieck toposes, but here is a way to see it.

For a (small) category $\mathbf C$, the presheaf category $\hat{\mathbf C}$ is a Grothendieck topos for the trivial topology on $\mathbf C$ (that is the topology where every object has only one covering, the maximal one). For it is a Grothendieck topos, it has then a suboject classifier $$ \Omega \colon X \mapsto \{\text{closed sieves on $X$}\}. $$ For the trivial topology, every sieve is closed, so the subobject classifier is the presheaf mapping all object to its set of sieves.

Here, take $\mathbf C$ to be the category $\omega^{\mathrm{op}}$, that is the linear order $$ \dots \to n \to \dots \to 2 \to 1 \to 0\ .$$ Then, a set through times is a presheaf on $\mathbf C$. So by what is above, the subobject classifier is $\Omega \colon n \mapsto \{\text{sieves on $n$}\}$. But taking a sieve on $n$ in this category $\mathbf C$ is the choice of an element $n+k \geq n$ for $k\geq 0$ or $\infty$ for the empty sieve. That is there is a bijection $$ \Omega(n) \simeq \mathbb N_\infty\ . $$ It remains to describe the image by $\Omega$ of the arrows $n+1 \to n$ : this is the map $\Omega(n) \to \Omega(n+1)$ pulling back the sieves on $n$ along $n+1 \to n$. With our new description of $\Omega(n)$ as $\mathbb N_\infty$, it is easily shown that $\Omega(n) \to \Omega(n+1)$ is precisely $p$ : $$ \begin{aligned} \infty &\mapsto \infty \\ k &\mapsto k-1 \quad\text{for $k>0$} \\ 0 &\mapsto 0\ . \end{aligned} $$ (To see it, consider $m \geq n$ and try to describe the pulling back on $m$ of the sieve on $n$ generated by $k \to n$ : you will find that it is the sieve on $m$ generating by $\max(m,k) \to n$.)