Subobject classifer in presheaf category


We wish to characterize the subobject classifier in  = [Aop,Set].

Definition. A sieve on A A is a set of arrows with codomain A such that f S implies f g S for any g right-composable with f.

We define Ω Â as follows. For A A, Ω(A) is the set of sieves on A. For a map f : A A, Ω(f) : Ω(A) Ω(A) is the map sending S, a sieve on A, to g : f g S, a sieve on A.

Theorem. Ω is the subobject classifier in Â.

Proof. Denote by ΔT the constant presheaf with value T (this is the terminal presheaf). Let true : ΔT Ω be defined with components trueA : T Ω(A) sending T to the maximal sieve on A (all arrows with codomain A). We define the characteristic function χ and show that every subobject (subfunctor) in  is the pullback of true along χ (and χ is unique with this property).

Take some monic Q P in Â. Note that an arrow is monic in  if and only if its components are monic (thus injective) arrows in Set. Define χ : P Ω with components χA : P(A) Ω(A) as follows: Let χA(x) be the sieve consisting of arrows f : Z A for some Z such that P(f)(x) im iZ. We now claim that:

  Q         ΔT


itχruPe         Ω

commutes and is a pullback square. Take x P(A) and suppose x im iA, so that x = iA(y). Then χA(x) = χA(iA(y)) is the sieve on A consisting of arrows f : Z A such that P(f)(iA(y)) im iZ. But, as i is a natural transformation, P(f)(iA(y)) = iZ(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 P(A), x im iA 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 A we have P(f)(x) im iZ. In particular, P(1A)(x) im iA, but since P(1A) = 1P(A), this means x im iA. So, in fact, x im iA 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 jP on the left. Then, by the preceding paragraph we would have x im jA if and only if χA(x) is the maximal sieve if and only if x im iA. Since iA and jA are injective, x is the image of a unique element in each. Then, define a map φ : R Q that pairs up these preimages, by φA(w) = iA1(j A(w)). It’s easy to see that this defines a natural transformation (isomorphism, in fact), and clearly i φ = j with φ unique. Thus, the square is a pullback.

We now show χ is unique with this property. Suppose 𝜃 : P Ω 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 A in χA(x), so that P(f)(x) im iZ. 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 g 𝜃A(x). Thus the previous statement is true if and only if for all arrows g with codomain Z, f g 𝜃A(x). This is true if and only if f 𝜃A(x), completing the proof of equality. To see how the final iff holds, consider that if f g 𝜃A(x) for all g, then in particular f 1Z = f 𝜃A(x), and if f 𝜃A(x), f g 𝜃A(x) for all appropriate g, since 𝜃A(x) is a sieve.

So, Ω is a subobject classifier for  with characterstic function χ : P Ω and universal subobject true : ΔT Ω as defined.

Let’s see what this means in the case of [,Set]. Treat this as [(op)op,Set] to apply the definitions of the previous theorem. A presheaf here is just a “set through time”. A sieve on k op is a set n : n s for any s k. The maximal sieve on k is n : n 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 identified with some s k, the set of sieves on k is the set of integers greater or equal to k, and truek 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 truek.

The characteristic function χ gives the “time of truth”, in the following sense. Take QP 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) Q(n + t) for all t 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 truek.

This discussion also reveals that [,FinSet] has no subobject classifier – if it did, it would be given as above, but Ω is not a finite presheaf.