# Understanding an example of a subobject classifier.

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?]

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.

• I'm not sure on where the compatible injections come from to be honest. Are they the result of the "components" of $S$ and $\mathbf{X}$ together with the definition of a subobject (i.e., that $S$ is an equivalence class of monic arrows into $\mathbf{X}$)? I still don't understand the term "sets over time" either. I'm sorry to bother you like this :/ – Shaun Dec 10 '13 at 11:07
• $S \to X$ is a monomorphism, hence every component $S_i \to X_i$ is a monomorphism (use the pullback-characterization of monomorphisms and the degree-wise-computation of pullbacks in order to see this). – Martin Brandenburg Dec 10 '13 at 23:17

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$.)

• Thanks a lot for this addition. I already planned to write something like that. – Martin Brandenburg Dec 9 '13 at 21:28
• Thank you. I'm not familiar with Grothendieck topoi nor with sieves, unfortunately, but from what I've seen so far, this does make some sense :) – Shaun Dec 10 '13 at 9:42