subobject classifier in nLab

Contents

1. Idea

Subsets A of a set X correspond precisely to maps from X to the set of truth values of classical logic via their characteristic function χA:X→{0,1} . The concept of a subobject classifier generalizes this situation to toposes other than Set:

A subobject classifier in a topos is a morphism true:*→Ω such that every monomorphism A↪B in the topos (hence every subobject) is the pullback of this morphism along a unique morphism (the characteristic morphism of A) B→Ω.

In this sense Ω is the classifying object for subobjects and true:*→Ω the generic subobject.

The existence of a subobject classifier in a category is a powerful property which induces much other structure that lies at the heart of topos theory.

By restricting the class of monomorphism appropriately, the concept can be relativized to the concept of an M-subobject classifier1: e.g. demanding only classification of strong monomorphisms leads to quasitoposes.

In type theory, a type closely related to the subobject classifier is the type of propositions, often denoted Prop or (sometimes in homotopy type theory) hProp.

2. Definition

See for instance (MacLane-Moerdijk, p. 32).

This appears for instance as (MacLane-Moerdijk, prop. I.3.1).

In more detail: given a morphism f:c→d in C, the function

takes a subobject i:t↪d to the subobject of c obtained by pulling back i along f. (Notice that monomorphisms, as discussed there, are stable under pullback.)

The representability of this functor means there is an object Ω together with a subobject t:T↪Ω which is universal, meaning that given any subobject i:s↪c, there is a unique morphism f:c→Ω such that i is obtained as the pullback of t along f.

3. Examples

In Set

In the category of sets, the 2-element set 2={f,t} plays the role of Ω; the morphism t:1→2 just names the element t. Given a subset S⊆X, the characteristic function χS:X→2 is the function defined by χS(x)=t if x∈S, and χS(x)=f if x∉S.

In a presheaf topos

In GSet

As a special case of presheaf toposes, for G a discrete group and GSet=[BG,Set] the topos of G-sets, there are precisely two sieves on the single object of the delooping groupoid BG: the trivial one and the empty one. Hence the subobject classifier here is the 2-element set as in Set, but now regarded as a G-set with trivial G-action.

For toposes of (left) actions of general monoids M the picture changes dramatically, since then there will usually exist non-trivial left ideals and, accordingly, the structure of Ω will become richer: Its underlying set has elements all left ideals, with m∈M acting on a left ideal L by mapping it to the left ideal {n∈M|n⋅m∈L}. (Of course, the same description of Ω applies to the case of groups as well, it is just, that groups lack non-trivial left ideals!)

In a non-boolean topos

An example of a non-Boolean topos is the category of sheaves over a “typical” topological space X such as the real line ℝ in its usual topology. In this case, Ω is the sheaf where the set of sections over an open subset U is the set of open subsets of U, with the obvious restriction maps; the sheaf topos in this case is guaranteed to be non-Boolean provided there are some non-regular open sets in X (a open set is regular if it is the interior of its closure). The “internal logic” of such a topos is intuitionistic.

In a slice topos

In a non-topos

The category Set* of pointed sets has a subobject classifier (specified up to unique isomorphism as the pointed set with two elements).

If one is willing to admit non-locally small categories, then the category of classes in ZFC is not a topos (it is not cartesian closed) but has a subobject classifier: any two-element set.

4. Properties

Suppose a category C has a subobject classifier; this entails some striking structural consequences for C. We list a few here:

Already these results impose some tight restrictions on C. We get some more by exploiting the internal structure of Ω.

The subobject classifier always comes with the structure of an internal poset; that is, a relation ⊆↪Ω×Ω which is internally reflexive, antisymmetric, and transitive. This can be constructed directly (see Proposition 4.4 below), or obtained via the Yoneda lemma since the collection of subobjects of any object is an external poset.

Similarly, since we assume that C is finitely complete, each subobject poset Sub(X) has intersections (gotten as pullbacks or fiber products of pairs of monics i:A→X,j:B→X), and the intersection operation

is natural in X. Hence we have a family of maps

natural in X; by the Yoneda lemma, we infer the presence of an internal intersection map

making Ω an internal meet-semilattice.

More significantly, Ω is an internal Heyting algebra. More accurately, it’s a Heyting algebra provided it has joins; without joins it is a cartesian closed poset:

Normally these results are proved in the context of toposes, where we may say for example that Ω is an internal Boolean algebra if and only if the topos is Boolean. But as the proofs above indicate, we need only exploit the definition of subobject classifier making reference only to finite limit structure.

In a topos, the subobject classifier Ω is always injective, and, so is the power object ΩX for every object X (See at injective object for some of the details). In particular, every object X embeds into an injective object by the singleton monomorphism X→ΩX: ‘A topos has enough injective objects!’. More generally, injective objects in a topos are precisely the ones that are retracts of some ΩX (Cf. Borceux 1994, p.315; Moerdijk-MacLane 1994, p.210).

Johnstone’s exercise

A curiosity from Johnstone’s Topos Theory, posed as an exercise, is that any monomorphism Ω→Ω is an isomorphism and even an involution. Thus Ω is a Hopfian object?.

An online proof may be found here.

5. Categories with a contractible subobject classifier

Suppose a topos ℰ has a connected components functor Π left adjoint to Δ⊣Γ assigning to an object X the set of it connected components. We call X connected if Π(X) is a singleton and contractible if Π(XY) is connected for all Y∈ℰ. It can be shown that provided Π preserves finite products, Ω is contractible iff Ω is connected which in turn implies the same for all other injective objects (see at sufficiently cohesive topos).

Now the subobject classifier Ω has always two disjoint points true, false whence provided it is connected we can view it (together with its Heyting algebra structure) has a (highly nonlinear) generalized interval object and define a notion of homotopy relative to Ω. The intuition here is that truth and falsity are continuously connected in such toposes and blend into each other, endowing (the logic in) ℰ with a certain Hegelian flavor. The contractability of Ω was taken as a key property of a gros topos of spaces by William Lawvere. Further information on this particular class of cohesive toposes and discussion of properties of Ω relevant in this context is at sufficiently cohesive topos.

6. Categories without subobject classifiers

As the previous section indicates, having a subobject classifier is a very strong property of a category and “most” categories with finite limits don’t have one.

For example, there is an easy condition ensuring a category2 with a terminal object can’t have a subobject classifier: if there are no nonidentity morphisms out of the terminal object. This includes the following examples.

• Any top bounded partial order.

• In Ring, the category of rings, there are no nonidentity morphisms out of the terminal object the zero ring.

Here’s another obstacle:

• If an abelian category had a subobject classifier, every subobject of every object would have to be the kernel of its classifying map. In particular, the subobject 0 of every object A would have to be the kernel of its classifying map, so that every object in this abelian category would embed into the subobject classifier Ω (including, say, all small products of Ω with itself) which in nontrivial cases would cause size issues.

But a real killer is the fact that all monos are regular, or its consequences of the category being balanced and uniqueness of epi-mono factorizations:

• The categories Pos, Cat, Top are not balanced (consider the map from a discrete structure on a set to an indiscrete structure on the same set, induced by the identity function). The category CMon is not balanced (consider the inclusion ℕ↪ℤ which is epic).

Even though all monos in Grp are regular, we can kill off Grp by observing that if t:1→Ω were a subobject classifier, the proof of Proposition 4.1 indicates that every mono i:A→X would have to be the kernel of χi. But not all monos in Grp are kernels.

Perhaps an even more decisive killer is the observation that meets distribute over (arbitrary) joins in subobject orders. This eliminates many categories from consideration:

• Lattices of subobjects in Grp or Ab are rarely distributive.

• For any nontrivial category with biproducts, there are non-distributive subobject lattices. Take any object A, so that we have three subobjects i1:A→A⊕A, i2:A→A⊕A, and Δ:A→A⊕A. Then i1∨i2=⊤, whereas i1∧Δ=⊥=i2∧Δ. Under distributivity we have

  Δ=Δ∧⊤=Δ∧(i1∨i2)=(Δ∧i1)∨(Δ∧i2)=⊥∨⊥=⊥

  but Δ=⊥ forces A=0. So the only such category that can have a subobject classifier is trivial.

7. Generalizations: object classifier

In higher topoi the subobject classifiers are the universal fibrations:

in the (n+1)-topos nCat of n-categories the subobject classifier is the forgetful functor

from the n-category of pointed (n−1)-categories to that of (n−1)-categories, which forgets the point.

This is described in more detail at generalized universal bundle. See also the discussion at stuff, structure, property.

In fact, using the notion of (-1)-category the subobject classifier in Set does fit precisely into this pattern:

the 2-element set 2 may be regarded as the 0-category of (-1)-categories (of which there are two) and the one-element set * is the 0-category of pointed (-1)-categories, of which there is one.

In the context of (∞,1)-topos theory subobject classifiers are discussed in section 6.1.6 of

Whereas for 1-toposes the subobject classifier is the key structural ingredient (besides the exactness properties), in higher topos theory this role is taken over by the object classifier, as pointed out in Lurie (2009).

8. Related concepts

9. References

The concept was introduced in

• William Lawvere, Quantifiers and sheaves , Actes Congrès intern. math. 1 (1970), pp.329-334. (pdf)

Discussion of the concept can be found in the usual suspects

• Francis Borceux, Handbook of Categorical Algebra 3 , Cambridge UP 1994.

• R. Goldblatt, Topoi - The Categorical Analysis of Logic, 2nd ed. North-Holland Amsterdam 1984. (Dover reprint New York 2006; project euclid)

• Peter Johnstone, Topos Theory , Academic Press New York 1977.

• Peter Johnstone, Sketches of an Elephant I , Oxford UP 2002.

• Saunders MacLane, Ieke Moerdijk, Sheaves in Geometry and Logic , Springer Heidelberg 1994. (section I.3-4)

See also

• Francis Borceux, When is Ω a cogenerator in a topos ? , Cah. Top. Géom. Diff. Cat. XVI no.1 (1975) pp.3-15. (numdam