Subobject classifer in presheaf category

We wish to characterize the subobject classiﬁer in $\hat{A} = [A^{o p}, S e t]$ .

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 $Ω \in \hat{A}$ as follows. For $A \in A$ , $Ω (A)$ is the set of sieves on $A$ . For a map $f : A \to A^{'}$ , $Ω (f) : Ω (A^{'}) \to Ω (A)$ is the map sending $S$ , a sieve on $A^{'}$ , to $\{g : f \circ g \in S\}$ , a sieve on $A$ .

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

Proof. Denote by $Δ T$ the constant presheaf with value $\{T\}$ (this is the terminal presheaf). Let $true : Δ T \to Ω$ be deﬁned with components ${true}_{A} : \{T\} \to Ω (A)$ sending $T$ to the maximal sieve on $A$ (all arrows with codomain $A$ ). We deﬁne the characteristic function $χ$ and show that every subobject (subfunctor) in $\hat{A}$ is the pullback of $true$ along $χ$ (and $χ$ 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 $S e t$ . Deﬁne $χ : P \to Ω$ with components $χ_{A} : P (A) \to Ω (A)$ as follows: Let $χ_{A} (x)$ be the sieve consisting of arrows $f : Z \to A$ for some $Z$ such that $P (f) (x) \in im i_{Z}$ . We now claim that:

Q ΔT

itχruPe Ω

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

This tells us that the square is a pullback. To see why, suppose we had another commuting square with $R \to_{}^{j} P$ on the left. Then, by the preceding paragraph we would have $x \in im j_{A}$ if and only if $χ_{A} (x)$ is the maximal sieve if and only if $x \in 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 $φ : R \to Q$ that pairs up these preimages, by $φ_{A} (w) = i_{A}^{- 1} (j_{A} (w))$ . It’s easy to see that this deﬁnes a natural transformation (isomorphism, in fact), and clearly $i \circ φ = j$ with $φ$ unique. Thus, the square is a pullback.

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

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

Let’s see what this means in the case of $[ℕ, S e t]$ . Treat this as $[{(ℕ^{op})}^{o p}, S e t]$ to apply the deﬁnitions of the previous theorem. A presheaf here is just a “set through time”. A sieve on $k \in ℕ^{op}$ is a set $\{n : n \geq s\}$ for any $s \geq k$ . The maximal sieve on $k$ is $\{n : n \geq k\}$ . 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 \geq k$ , the set of sieves on $k$ is the set of integers greater or equal to $k$ , and ${true}_{k}$ picks out the maximal sieve $k$ . All this is visualized as follows:

Ω : 0 {0 1 2 3 ...}

1 {1 2 3 ...}

2 {2 3 ...}

3 {3 ...}

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

The characteristic function $χ$ gives the “time of truth”, in the following sense. Take $Q ↪ P$ a subfunctor. Let $σ$ denote the “transition function(s)” of $P$ , of which $Q$ ’s are restrictions. $χ_{k} (x)$ is given by the integer $n$ such that $σ^{n + t} (x) \in Q (n + t)$ for all $t \geq 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 (k)$ to begin with, $χ_{k} (x)$ will be $k$ , agreeing with ${true}_{k}$ .

This discussion also reveals that $[ℕ, F i n S e t]$ has no subobject classiﬁer – if it did, it would be given as above, but $Ω$ is not a ﬁnite presheaf.