**Subobject classifer in presheaf category**

We wish to characterize the subobject classiﬁer in $\hat{A}=\left[{A}^{op},Set\right]$.

Deﬁnition. A sieve on $A\in A$ is a set of arrows with codomain $A$ such that $f\in S$ implies $f\circ g\in S$ for any $g$ right-composable with $f$.

We deﬁne $\Omega \in \hat{A}$ as follows. For $A\in A$, $\Omega \left(A\right)$ is the set of sieves on $A$. For a map $f:A\to {A}^{\prime}$, $\Omega \left(f\right):\Omega \left({A}^{\prime}\right)\to \Omega \left(A\right)$ is the map sending $S$, a sieve on ${A}^{\prime}$, to $\left\{g:f\circ g\in S\right\}$, a sieve on $A$.

Theorem. $\Omega $ is the subobject classiﬁer in $\hat{A}$.

Proof. Denote by $\Delta T$ the constant presheaf with value $\left\{T\right\}$ (this is the terminal presheaf). Let $\text{true}:\Delta T\to \Omega $ be deﬁned with components ${\text{true}}_{A}:\left\{T\right\}\to \Omega \left(A\right)$ sending $T$ to the maximal sieve on $A$ (all arrows with codomain $A$). We deﬁne the characteristic function $\chi $ and show that every subobject (subfunctor) in $\hat{A}$ is the pullback of $\text{true}$ along $\chi $ (and $\chi $ is unique with this property).

Take some monic $Q\to P$ in $\hat{A}$. Note that an arrow is monic in $\hat{A}$ if and only if its components are monic (thus injective) arrows in $Set$. Deﬁne $\chi :P\to \Omega $ with components ${\chi}_{A}:P\left(A\right)\to \Omega \left(A\right)$ as follows: Let ${\chi}_{A}\left(x\right)$ be the sieve consisting of arrows $f:Z\to A$ for some $Z$ such that $P\left(f\right)\left(x\right)\in \mathrm{im}{i}_{Z}$. We now claim that:

commutes and is a pullback square. Take $x\in P\left(A\right)$ and suppose $x\in \mathrm{im}{i}_{A}$, so that $x={i}_{A}\left(y\right)$. Then ${\chi}_{A}\left(x\right)={\chi}_{A}\left({i}_{A}\left(y\right)\right)$ is the sieve on $A$ consisting of arrows $f:Z\to A$ such that $P\left(f\right)\left({i}_{A}\left(y\right)\right)\in \mathrm{im}{i}_{Z}$. But, as $i$ is a natural transformation, $P\left(f\right)\left({i}_{A}\left(y\right)\right)={i}_{Z}\left(Q\left(f\right)\left(y\right)\right)$, so this holds true for all arrows with codomain $A$, meaning that ${\chi}_{A}\left(x\right)$ is the maximal sieve on $A$. So, for all $A$ and $x\in P\left(A\right)$, $x\in \mathrm{im}{i}_{A}$ implies ${\chi}_{A}\left(x\right)$ is the maximal sieve – thus, the square actually does commute. Conversely, suppose ${\chi}_{A}\left(x\right)$ is the maximal sieve. Then for all $f:Z\to A$ we have $P\left(f\right)\left(x\right)\in \mathrm{im}{i}_{Z}$. In particular, $P\left({1}_{A}\right)\left(x\right)\in \mathrm{im}{i}_{A}$, but since $P\left({1}_{A}\right)={1}_{P\left(A\right)}$, this means $x\in \mathrm{im}{i}_{A}$. So, in fact, $x\in \mathrm{im}{i}_{A}$ if and only if ${\chi}_{A}\left(x\right)$ is the maximal sieve.

This tells us that the square is a pullback. To see why, suppose we had another commuting square with $R\underset{}{\overset{j}{\to}}P$ on the left. Then, by the preceding paragraph we would have $x\in \mathrm{im}{j}_{A}$ if and only if ${\chi}_{A}\left(x\right)$ is the maximal sieve if and only if $x\in \mathrm{im}{i}_{A}$. Since ${i}_{A}$ and ${j}_{A}$ are injective, $x$ is the image of a unique element in each. Then, deﬁne a map $\phi :R\to Q$ that pairs up these preimages, by ${\phi}_{A}\left(w\right)={i}_{A}^{-1}\left({j}_{A}\left(w\right)\right)$. It’s easy to see that this deﬁnes a natural transformation (isomorphism, in fact), and clearly $i\circ \phi =j$ with $\phi $ unique. Thus, the square is a pullback.

We now show $\chi $ is unique with this property. Suppose $\mathit{\theta}:P\to \Omega $ was another map that made the square a pullback. We show that, for any $A$ and $x$, that ${\mathit{\theta}}_{A}\left(x\right)={\chi}_{A}\left(x\right)$. Take an arrow $f:Z\to A$ in ${\chi}_{A}\left(x\right)$, so that $P\left(f\right)\left(x\right)\in \mathrm{im}{i}_{Z}$. This is the case if and only if ${\mathit{\theta}}_{Z}\left(P\left(f\right)\left(x\right)\right)$ is the maximal sieve on $Z$. By naturality of $\mathit{\theta}$ this sieve is the same as $\Omega \left(f\right)\left({\mathit{\theta}}_{A}\left(x\right)\right)$, the set of arrows $g$ with codomain $Z$ such that $f\circ g\in {\mathit{\theta}}_{A}\left(x\right)$. Thus the previous statement is true if and only if for all arrows $g$ with codomain $Z$, $f\circ g\in {\mathit{\theta}}_{A}\left(x\right)$. This is true if and only if $f\in {\mathit{\theta}}_{A}\left(x\right)$, completing the proof of equality. To see how the ﬁnal iﬀ holds, consider that if $f\circ g\in {\mathit{\theta}}_{A}\left(x\right)$ for all $g$, then in particular $f\circ {1}_{Z}=f\in {\mathit{\theta}}_{A}\left(x\right)$, and if $f\in {\mathit{\theta}}_{A}\left(x\right)$, $f\circ g\in {\mathit{\theta}}_{A}\left(x\right)$ for all appropriate $g$, since ${\mathit{\theta}}_{A}\left(x\right)$ is a sieve.

So, $\Omega $ is a subobject classiﬁer for $\hat{A}$ with characterstic function $\chi :P\to \Omega $ and universal subobject $\text{true}:\Delta T\to \Omega $ as deﬁned. □

Let’s see what this means in the case of $\left[\mathbb{N},Set\right]$. Treat this as $\left[{\left({\mathbb{N}}^{\text{op}}\right)}^{op},Set\right]$ to apply the deﬁnitions of the previous theorem. A presheaf here is just a “set through time”. A sieve on $k\in {\mathbb{N}}^{\text{op}}$ is a set $\left\{n:n\ge s\right\}$ for any $s\ge k$. The maximal sieve on $k$ is $\left\{n:n\ge k\right\}$. Since a sieve is just a “run of integers”, we may choose to identify a sieve with its starting point $s$, so that a sieve on $k$ is identiﬁed with some $s\ge k$, the set of sieves on $k$ is the set of integers greater or equal to $k$, and ${\text{true}}_{k}$ picks out the maximal sieve $k$. All this is visualized as follows:

and the bolded elements are the ones selected by ${\text{true}}_{k}$.

The characteristic function $\chi $ gives the “time of truth”, in the following sense. Take $Q\hookrightarrow P$ a subfunctor. Let $\sigma $ denote the “transition function(s)” of $P$, of which $Q$’s are restrictions. ${\chi}_{k}\left(x\right)$ is given by the integer $n$ such that ${\sigma}^{n+t}\left(x\right)\in Q\left(n+t\right)$ for all $t\ge 0$ (note then clearly this $n$ must be at least $k$). In other words, the time $n$ at which the transition function carries $x$ into the subfunctor $Q$, after which it remains there for the rest of time – the time at which $x$’s membership in $Q$ becomes true. We can see that if $x$ is already in $Q\left(k\right)$ to begin with, ${\chi}_{k}\left(x\right)$ will be $k$, agreeing with ${\text{true}}_{k}$.

This discussion also reveals that $\left[\mathbb{N},FinSet\right]$ has no subobject classiﬁer – if it did, it would be given as above, but $\Omega $ is not a ﬁnite presheaf.