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 🙂
Best Answer
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:
$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$.
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$.
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.