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 20-Aug-2001 18:17:37 -0300,987;000000000000-00000013