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

enter image description here

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


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.

  • $\begingroup$ 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 :/ $\endgroup$ – Shaun Dec 10 '13 at 11:07
  • 1
    $\begingroup$ $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). $\endgroup$ – 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$.)

  • 1
    $\begingroup$ Thanks a lot for this addition. I already planned to write something like that. $\endgroup$ – Martin Brandenburg Dec 9 '13 at 21:28
  • $\begingroup$ 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 :) $\endgroup$ – Shaun Dec 10 '13 at 9:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.