Subobject classifer in presheaf category
We wish to characterize the subobject classiﬁer in .
Deﬁnition. A sieve on is a set of arrows with codomain such that implies for any right-composable with .
We deﬁne as follows. For , is the set of sieves on . For a map , is the map sending , a sieve on , to , a sieve on .
Theorem. is the subobject classiﬁer in .
Proof. Denote by the constant presheaf with value (this is the terminal presheaf). Let be deﬁned with components sending to the maximal sieve on (all arrows with codomain ). We deﬁne the characteristic function and show that every subobject (subfunctor) in is the pullback of along (and is unique with this property).
Take some monic in . Note that an arrow is monic in if and only if its components are monic (thus injective) arrows in . Deﬁne with components as follows: Let be the sieve consisting of arrows for some such that . We now claim that:
commutes and is a pullback square. Take and suppose , so that . Then is the sieve on consisting of arrows such that . But, as is a natural transformation, , so this holds true for all arrows with codomain , meaning that is the maximal sieve on . So, for all and , implies is the maximal sieve – thus, the square actually does commute. Conversely, suppose is the maximal sieve. Then for all we have . In particular, , but since , this means . So, in fact, if and only if is the maximal sieve.
This tells us that the square is a pullback. To see why, suppose we had another commuting square with on the left. Then, by the preceding paragraph we would have if and only if is the maximal sieve if and only if . Since and are injective, is the image of a unique element in each. Then, deﬁne a map that pairs up these preimages, by . It’s easy to see that this deﬁnes a natural transformation (isomorphism, in fact), and clearly with unique. Thus, the square is a pullback.
We now show is unique with this property. Suppose was another map that made the square a pullback. We show that, for any and , that . Take an arrow in , so that . This is the case if and only if is the maximal sieve on . By naturality of this sieve is the same as , the set of arrows with codomain such that . Thus the previous statement is true if and only if for all arrows with codomain , . This is true if and only if , completing the proof of equality. To see how the ﬁnal iﬀ holds, consider that if for all , then in particular , and if , for all appropriate , since is a sieve.
So, is a subobject classiﬁer for with characterstic function and universal subobject as deﬁned. □
Let’s see what this means in the case of . Treat this as to apply the deﬁnitions of the previous theorem. A presheaf here is just a “set through time”. A sieve on is a set for any . The maximal sieve on is . Since a sieve is just a “run of integers”, we may choose to identify a sieve with its starting point , so that a sieve on is identiﬁed with some , the set of sieves on is the set of integers greater or equal to , and picks out the maximal sieve . All this is visualized as follows:
and the bolded elements are the ones selected by .
The characteristic function gives the “time of truth”, in the following sense. Take a subfunctor. Let denote the “transition function(s)” of , of which ’s are restrictions. is given by the integer such that for all (note then clearly this must be at least ). In other words, the time at which the transition function carries into the subfunctor , after which it remains there for the rest of time – the time at which ’s membership in becomes true. We can see that if is already in to begin with, will be , agreeing with .
This discussion also reveals that has no subobject classiﬁer – if it did, it would be given as above, but is not a ﬁnite presheaf.