categories: Re: Subclassifier object question

[Vaughan Pratt <pratt@cs.stanford.edu>]

The direct answer to Bill Halchin's concern (`it seems like every
element will be "classified" as belonging to "subX"') is that this is
the defining characteristic of subX: subX consists of those elements
of X that belong to subX.  That is, every element of subX has to be
classified as belonging to subX.

The triviality of this answer suggests that Bill's real question is,
how does the pullback

        f
    Y ----> X
    |       |
   !|       |g
    |       |
    v   z   v
    1 ----> Z

in the definition of topos work in the case of sets?  Here's one answer.

The basic idea is that there are two equally good ways of defining a
subset of a set X, in terms of functions respectively to and from X.

TO: A function f:Y->X has an image f(Y), a subset of X.

FROM: A function g:X->Z has an inverse image g^-1({z}) of any given
element z of Z, also a subset of X.

Every subset of X arises in both ways (provided in the latter case that Z
has at least two elements).  With a little care it can be made to arise
in a canonical way in both cases, and moreover such that these two ways
are paired up according to the subset they each determine.

TO:  Now there are many functions to X with the same image.  However any
two _injections_ i:Y->X, i':Y'->X have the same image if and only if
there is a bijection j:Y->Y' for which the evident triangle commutes,
namely i'j = i.  Call two such injections isomorphic.  The isomorphism
classes of injections to X are then in bijection with the subsets of X.

FROM:  Even if we hold Z and an element z thereof fixed there may
still be many functions g:X->Z with the same inverse image g^-1({z}).
This happens for |Z| >= 3, where two g's can agree on the members of
a subset yet disagree about which of the non-z elements of Z to send
the nonmembers to.  On the other side, if Z is a singleton we lose the
proper subsets of X, and if Z is empty we lose all subsets.

We are now in a position to analyze the subobject classifier condition,
which can be stated for sets as follows.

    For every injection i:Y->X there exists a unique g:X->Z making the
    above square a pullback.

Existence and uniqueness each appear twice in this condition, once
explicitly, and once implicitly in the notion of pullback.

For the former, the existence requirement ensures that Z has enough
elements to permit it to classify at all, while uniqueness prevents it
from having too many, avoiding ``overclassification.''  Thus |Z|=2 is
the only possible choice for a subobject classifier, i.e. Z (along with
its element z) is determined up to isomorphism.

For the latter, the uniqueness requirement in the definition of pullback
ensures that i is an injection, and existence makes it the the maximal
injection into X for which g(i(y)) = z for all y in Y.  Note furthermore
that g uniquely determines i up to isomorphism, i.e. the property of
being a pullback ensures that for each g there exists a unique i up to
isomorphism, giving us the other direction of our desired bijection.

Although everything said above has been for Set, it can be lifted (with
the necessary care) to any cartesian closed category with the obvious
generalizations of set to object, function to morphism, injection to
monic, and element to morphism-from-1.

What does not lift are properties of the topos Set not common to all
toposes, such as that Set has a natural numbers object {0,1,2,...},
and is a Boolean topos (the logic of set membership is Boolean).

An example of a topos with no natural numbers object is furnished by
the subtopos of Set consisting just of its finite sets.  The argument
that Set is a topos shows with almost no modification (and in particular
with the same subobject classifier) that this evidently cartesian closed
subcategory is itself a topos.

An example of a non-Boolean topos is furnished by the cartesian closed
category of directed graphs made a topos by taking Z to be the 2-clique
(two vertices and four edges) with one of its self-loops duplicated
and the duplicate taken as z (the elements of a directed graph being
its self-loops).  A CCC can be made a topos in at most one way up to
isomorphism of its subobject classifier, so (given that this choice
works), this strange graph is it for this topos.

One quick way to see that this is a topos is to present it as the
presheaf category Set^C where C is the category E=>V with two objects
E,V and two morphisms s,t:E->V.  A graph is a functor from C to Set;
it assigns sets to E and V (respectively the set of edges and the set of
vertices), and functions to s and t, respectively the source and target
functions specifying the two vertices the edges run between.  The relevant
theorem here is that the functor category Set^C is a topos for any small
category C.  For C = E=>V the theorem automatically constructs the above
strange graph.

Vaughan Pratt