To supplement Vaughn Pratt's excellent account of the subobject classifier in the topos of directed graphs, it may help to make explicit the following: The truth object merely represents (i.e., concentrates) a notion which applies in any category. Given two maps x and y with the same codomain, x BELONGS TO y iff the Steenrod lifting problem has a solution (Exist z) x=yz. If y is monic, then of course there is at most one "proof" z of such a belonging relation. Further specializing, if x is also monic, the relation in question is usually called "inclusion of parts" ; specializing in another direction, if the domain of x is a favorite element-kind in the particular category (such as a generic arrow or generic dot in the case of graphs, or the terminal object 1), then it is called "membership". Note that pioneers such as Dedekind and Banach did NOT need to distinguish notationally between these special cases (in contrast to the Peano tradition which seems to have brought more confusion than clarification). The dual Steenrod division problem, which he called "extension", is equally important in mathematical practice; existentially quantifying it we obtain a "delta" relation dual to the epsilon relation: f IS DETERMINED BY g iff there exists (a procedure) p so that f=pg. Again if g is epic there can be at most one p, and of interest is the case where the codomain of f is restricted to a favorite "type"(=space of values for functions). Question: Are there useful categories wherein this determination relation is concentrated in one object as the belonging relation is for toposes?
From: Vaughan Pratt <pratt@cs.stanford.edu> To: categories@mta.ca Subject: categories: Re: Subclassifier object question Date: Mon, 20 Aug 2001 13:01:52 -0700
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
27-Aug-2001 07:06:29 -0300,2121;000000000001-0000001b