nLab subobject classifier

Redirected from "subobject classifiers".
Contents

Context

Topos Theory

topos theory

Background

Toposes

Internal Logic

Topos morphisms

Extra stuff, structure, properties

Cohomology and homotopy

In higher category theory

Theorems

Universes

Contents

Idea

Subsets AA of a set XX correspond precisely to maps from XX to the set of truth values of classical logic via their characteristic function χ A:X{0,1}\chi_A:X\to \{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:*Ωtrue : * \to \Omega such that every monomorphism ABA \hookrightarrow B in the topos (hence every subobject) is the pullback of this morphism along a unique morphism (the characteristic morphism of AA) BΩB \to \Omega.

In this sense Ω\Omega is the classifying object for subobjects and true:*Ωtrue : * \to \Omega 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 PropProp or (sometimes in homotopy type theory) hProphProp.

Definition

Definition

In a category CC with finite limits, a subobject classifier is a monomorphism true:*Ωtrue \,\colon\, * \to \Omega out of the terminal object, such that for every monomorphism UXU \to X in CC there is a unique morphism χ U:XΩ\chi_U \colon X \to \Omega such that the following square commutes and is Cartesian (a pullback):

U * (pb) true X χ U Ω. \array{ U &\longrightarrow& * \\ \big\downarrow &{}^{{}_{(pb)}}& \big\downarrow{{}^\mathrlap{true}} \\ X &\underset{\chi_U}{\longrightarrow}& \Omega \mathrlap{\,.} }

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

Remark

Some terminology:

If it exists, the object Ω\Omega is also called the object of truth values, a global element KΩK \to \Omega is called a truth value and the element true:*Ωtrue : * \hookrightarrow \Omega is the truth value true, where all these terms allude to the internal logic of the category CC.

Note that the subobjects classified by the truth values are subterminal objects.

The morphism χ U\chi_U is also called the characteristic map or classifying map of the subobject UXU \hookrightarrow X.

Proposition

If CC has finite limits and is in addition a locally small category, then it has a subobject classifier precisely if the subobject-assigning presheaf

Sub:C opSet Sub : C^{op} \to Set
X{UX}/ X \mapsto \{U \hookrightarrow X\}/\sim

is representable. In this case the representing object is the subobject classifier: there is a natural isomorphism

Sub(X)C(X,Ω) Sub(X) \simeq C(X, \Omega)

in XCX \in C.

Moreover, in this case CC is well powered.

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

In more detail: given a morphism f:cdf: c \to d in CC, the function

Sub(f):Sub(d)Sub(c) Sub(f): Sub(d) \to Sub(c)

takes a subobject i:tdi: t \hookrightarrow d to the subobject of cc obtained by pulling back ii along ff. (Notice that monomorphisms, as discussed there, are stable under pullback.)

The representability of this functor means there is an object Ω\Omega together with a subobject t:TΩt: T \hookrightarrow \Omega which is universal, meaning that given any subobject i:sci: s \hookrightarrow c, there is a unique morphism f:cΩf: c \to \Omega such that ii is obtained as the pullback of tt along ff.

Proof

To see that a subobject classifier induces such a natural isomorphism, we need that the morphisms Sub(f)Sub(f) for fMor(C)f \in Mor(C) corresponds to the morphisms C(f,Ω)C(f,\Omega). This is the pasting law for pullbacks.

Conversely, to see that a subobjects-representing object Ω\Omega is a subobject classifier, use that by naturality we have for each morphism ϕ:XΩ \phi : X \to \Omega a commuting diagram

Sub(Ω) C(Ω,Ω) Sub(ϕ) C(ϕ,Ω) Sub(X) C(X,Ω) \array{ Sub(\Omega) &\stackrel{\simeq}{\to}& C(\Omega, \Omega) \\ {}^{\mathllap{Sub(\phi)}}\downarrow && \downarrow^{\mathrlap{C(\phi,\Omega)}} \\ Sub(X) &\stackrel{\simeq}{\to}& C(X, \Omega) }

whose commutativity says that every element of Sub(X)Sub(X) is the pullback along some ϕ:XΩ\phi : X \to \Omega of the subobject of Ω\Omega corresponding under the natural isomorphism to Id:ΩΩId : \Omega \to \Omega.

By further playing around with this one finds that this latter subobject of Ω\Omega has to be a terminal object.

Examples

In SetSet

In the category Sets of sets, the 2-element set 2={f,t}\mathbf{2} = \{f, t\} (the classical Boolean domain) plays the role of Ω\Omega; the morphism t:12t \colon 1 \to \mathbf{2} just names the element tt. Given a subset SXS \subseteq X, the characteristic function χ S:X2\chi_S: X \to \mathbf{2} is the function defined by χ S(x)=t\chi_S(x) = t if xSx \in S, and χ S(x)=f\chi_S(x) = f if xSx \notin S.

Remark

It is not usually true in toposes that Ω\Omega is the coproduct 2=1+1\mathbf{2} = 1 + 1; toposes where that occurs are called Boolean. Thus the category SetSet of sets is a Boolean topos, as is the presheaf topos Set GSet^G when GG is a groupoid.

In a presheaf topos

Proposition

The subobject classifier in a presheaf topos PSh(S)PSh(S) is the presheaf that sends each object USU \in S to the set sieves(U)sieves(U) of sieves on it

Ω:Usieves(U) \Omega \;\colon\; U \mapsto sieves(U)

Here sieves(U)sieves(U) is equivalently the set of subobjects of the representable presheaf Y(U)Y(U).

The corresponding morphism true:*Ωtrue : * \to \Omega of presheaves is the natural transformation that picks over each object the maximal sieve true U=maximal sieves(U):*sieves(U)true_U = maximal_{sieves(U)} : * \to sieves(U).

Remark

If one views a presheaf over a small category SS as a set varying (or evolving) over SS, then the subobject classifier in PSh(S)PSh(S) may be viewed as encapsulating the ways of an element to be in the set ranging from ‘never’ to ‘always’ being in the set.

In Set=PSh(*)Set = PSh(\ast) these two extremes are the only possibilities, but in the general case there are ways to become an element ‘over time’.

It might be helpful to have a look at the simple example of a subobject classifier in the presheaf topos of directed graphs worked out at Quiv to get some intuition.

In GSetG Set

As a special case of presheaf toposes, for GG a discrete group and GSet=[BG,Set]G Set = [\mathbf{B} G, Set] the topos of G-sets, there are precisely two sieves on the single object of the delooping groupoid BG\mathbf{B}G: 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 GG-set with trivial GG-action.

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

In a sheaf topos

The following is adapted from p. 34 of Caramello.

Let (C,J)(C, J) be a Grothendieck site. A sieve SS on an object cCc \in C is JJ-closed when, for any arrow f:dcf :d \to c, if f *(S)J(d)f^*(S) \in J(d) then fSf \in S. It’s called closed since this is a closure property: SS contains all arrows it covers. If (C,J)(C, J) is a locale with the open covers topology, then this condition means that SS is a collection of subopens of cc which is closed under unions. Clearly, every sieve on cc can be saturated to a closed one.

The subobject classifier of Sh(C,J)\mathrm{Sh}(C,J) is defined on objects as

Ω J(c)={S|S is a J-closed sieve on c} \Omega_J(c) = \{ S | \text{S is a J-closed sieve on c} \}

and on morphisms as

Ω J(f:cd)=f * \Omega_J(f : c \to d) = f^*

where f *f^* denotes, as above, pullback of sieves.

The arrow true:1Ω J\mathsf{true} : 1 \to \Omega_J picks the maximal sieve on each object (the one generated by the identity).

Given a mono m:BAm : B \to A, the classifying arrow χ m:AΩ J\chi_m : A \to \Omega_J is given by

χ m(c)(x)={f:dc|A(f)(x)B(d)}, \chi_m(c)(x) = \{f : d \to c | A(f)(x) \in B(d)\},

for any cCc \in C and xA(c)x \in A(c).

In a non-boolean topos

An example of a non-Boolean topos is the category of sheaves over a “typical” topological space XX such as the real line \mathbb{R} in its usual topology. In this case, Ω\Omega is the sheaf where the set of sections over an open subset UU is the set of open subsets of UU, 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 XX (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

Proposition

Let \mathcal{E} be a topos and XX \in \mathcal{E} any object. Write /X\mathcal{E}/X for the corresponding over-topos.

The subobject classifier of /X\mathcal{E}/X is p 2:Ω ×XXp_2 : \Omega_{\mathcal{E}} \times X \to X.

Proof

This follows for instance from the statement that the inverse image of any base change geometric morphism is a logical functor and hence preserves subobject classifiers: Here we are looking at the base change along p:X*p : X \to * and hence p *Ω Ω ×Xp^* \Omega_{\mathcal{E}}\simeq \Omega_{\mathcal{E}} \times X.

But the statement is also easily directly checked.

In a non-topos

The category Set *Set_\ast 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.

The opposite of the category of commutative von Neumann algebras has a subobject classifier given by 2\mathbb{C}^2 according to Simon Henry on MathOverflow, but is not a topos because it is not cartesian closed (see Dmitri Pavlov’s answer to the same MathOverflow question).

Properties

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

Proposition

Every monomorphism in C\mathbf{C} is a regular monomorphism, i.e. is an equalizer of some pair of maps.

Proof

For χ i:XΩ\chi_i: X \to \Omega the characteristic map of a mono i:AXi: A \to X, we find that ii is the equalizer of a pair of maps XΩX \rightrightarrows \Omega:

1 ! t X χ i Ω.\array{ & & 1 \\ & \mathllap{!} \nearrow & \downarrow \mathrlap{t} \\ X & \underset{\chi_i}{\to} & \Omega. }
Corollary

C\mathbf{C} is balanced, i.e., a morphism in C\mathbf{C} is an isomorphism iff it is both monic and epic.

Proof

“Only if” is trivial. The “if” comes from the fact that an epic (epimorphic) equalizer must be an isomorphism, for if i:AXi: A \to X is the equalizer of f,g:XYf, g: X \rightrightarrows Y and ii is epic, then f=gf = g, whence 1 X1_X is their equalizer, so i:AXi: A \to X must have been an isomorphism.

Proposition

Any two epi-mono factorizations of a map in C\mathbf{C} are canonically isomorphic.

Proof

Suppose ip=jqi p = j q where p,qp, q are epic and i,ji, j are monic. Since jj is regular, it is the equalizer of some parallel pair f,gf, g as in the diagram

A p B q i C j D gf E,\array{ A & \stackrel{p}{\to} & B & & \\ \mathllap{q} \downarrow & & \downarrow \mathrlap{i} & & \\ C & \underset{j}{\to} & D & \stackrel{\overset{f}{\to}}{\underset{g}{\to}} & E, }

so that fip=fjq=gjq=gipf i p = f j q = g j q = g i p, whence fi=gif i = g i since pp is epic, whence ii factors through jj as jj is the equalizer: i=jki = j k for some k:BCk: B \to C. Then also kp=qk p = q since jkp=ip=jqj k p = i p = j q and jj is monic. We have that kk is monic since ii is, and kk is epic since qq is. Thus kk is an isomorphism.

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

The subobject classifier always comes with the structure of an internal poset; that is, a relation Ω×Ω\subseteq\, \hookrightarrow \Omega\times\Omega which is internally reflexive, antisymmetric, and transitive. This can be constructed directly (see Proposition 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\mathbf{C} is finitely complete, each subobject poset Sub(X)Sub(X) has intersections (gotten as pullbacks or fiber products of pairs of monics i:AX,j:BXi: A \to X,j: B \to X), and the intersection operation

:Sub(X)×Sub(X)Sub(X)\cap: Sub(X) \times Sub(X) \to Sub(X)

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

:hom(X,Ω×Ω)hom(X,Ω)\cap: \hom(X, \Omega \times \Omega) \to \hom(X, \Omega)

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

:Ω×ΩΩ\wedge: \Omega \times \Omega \to \Omega

making Ω\Omega an internal meet-semilattice.

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

Proposition

There is an internal implication operator

:Ω×ΩΩ\Rightarrow: \Omega \times \Omega \to \Omega

uniquely specified by the internal condition

wuviffwuv.w \wedge u \leq v \qquad iff \qquad w \leq u \Rightarrow v.
Proof (sketch)

Construct Ω×Ω\subseteq \hookrightarrow \Omega \times \Omega as the equalizer of the pair of maps

Ω×Ωπ 1Ω\Omega \times \Omega \stackrel{\overset{\pi_1}{\longrightarrow}}{\underset{\wedge}{\longrightarrow}} \Omega

and then define :Ω×ΩΩ\Rightarrow: \Omega \times \Omega \to \Omega to be the characteristic map of Ω×Ω\subseteq \hookrightarrow \Omega \times \Omega. Now if χ u,χ v\chi_u, \chi_v are two maps XΩX \to \Omega, one calculates that wXw \hookrightarrow X is contained in the subobject classified by χ uχ v\chi_u \Rightarrow \chi_v iff wu=wuvw \cap u = w \cap u \cap v, which is just a way of saying wuvw \cap u \leq v.

Corollary

In every subobject poset Sub(X)Sub(X), meets distribute over any joins that exist.

Proof

Because UU \cap - is left adjoint to the external operator UU \Rightarrow - on Sub(X)Sub(X), it preserves any joins that happen to exist in Sub(X)Sub(X).

Normally these results are proved in the context of toposes, where we may say for example that Ω\Omega 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 Ω\Omega is always injective, and, so is the power object Ω X\Omega^X for every object XX (See at injective object for some of the details). In particular, every object XX embeds into an injective object by the singleton monomorphism XΩ XX\to\Omega^X: ‘A topos has enough injective objects!’. More generally, injective objects in a topos are precisely the ones that are retracts of some Ω X\Omega^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 ΩΩ\Omega \to \Omega is an isomorphism and even an involution. Thus Ω\Omega is a Hopfian object.

An online proof may be found here.

Categories with a contractible subobject classifier

Suppose a topos \mathcal{E} has a connected components functor Π\Pi left adjoint to ΔΓ\Delta\dashv \Gamma assigning to an object XX the set of it connected components. We call XX connected if Π(X)\Pi(X) is a singleton and contractible if Π(X Y)\Pi(X^Y) is connected for all YY\in\mathcal{E}. It can be shown that provided Π\Pi preserves finite products, Ω\Omega is contractible iff Ω\Omega is connected which in turn implies the same for all other injective objects (see at sufficiently cohesive topos).

Now the subobject classifier Ω\Omega has always two disjoint points true\mathsf{true}, false\mathsf{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 Ω\Omega. The intuition here is that truth and falsity are continuously connected in such toposes and blend into each other, endowing (the logic in) \mathcal{E} with a certain Hegelian flavor. The contractability of Ω\Omega 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 Ω\Omega relevant in this context is at sufficiently cohesive topos.

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 RingRing, 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 00 of every object AA would have to be the kernel of its classifying map, so that every object in this abelian category would embed into the subobject classifier Ω\Omega (including, say, all small products of Ω\Omega 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 \mathbb{N} \hookrightarrow \mathbb{Z} which is epic).

Even though all monos in Grp are regular, we can kill off GrpGrp by observing that if t:1Ωt: 1 \to \Omega were a subobject classifier, the proof of Proposition indicates that every mono i:AXi: A \to X would have to be the kernel of χ i\chi_i. But not all monos in GrpGrp 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 GrpGrp or AbAb are rarely distributive.

  • For any nontrivial category with biproducts, there are non-distributive subobject lattices. Take any object AA, so that we have three subobjects i 1:AAAi_1: A \to A \oplus A, i 2:AAAi_2: A \to A \oplus A, and Δ:AAA\Delta: A \to A \oplus A. Then i 1i 2=i_1 \vee i_2 = \top, whereas i 1Δ==i 2Δi_1 \wedge \Delta = \bot = i_2 \wedge \Delta. Under distributivity we have

    Δ=Δ=Δ(i 1i 2)=(Δi 1)(Δi 2)==\Delta = \Delta \wedge \top = \Delta \wedge (i_1 \vee i_2) = (\Delta \wedge i_1) \vee (\Delta \wedge i_2) = \bot \vee \bot = \bot

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

Directly related to this distributivity property is the question when a variety of algebras has a subobject classifier (cf. Johnstone 1990, pp.448f).

Generalizations

Weak subobject classifier

There are many subclasses of monomorphisms, such as regular monomorphisms, strong monomorphisms, and extremal monomorphisms. As a result, there are weaker forms of subobject classifiers that only classify a subclass of monomorphisms instead of all monomorphisms.

Suppose there is a category CC with finite limits. Let SS be a subclass of monomorphisms in CC, whose elements we shall refer to as SS-monomorphisms. An SS-subobject classifier is an SS-monomorphism true:*Ωtrue : * \to \Omega out of the terminal object, such that for every SS-monomorphism UXU \to X in CC there is a unique morphism χ U:XΩ\chi_U : X \to \Omega such that there is a pullback diagram of the following form:

U * true X χ U Ω. \array{ U &\to& * \\ \downarrow && \downarrow^{\mathrlap{true}} \\ X &\stackrel{\chi_U}{\to}& \Omega } \,.
  • If SS is the class of all monomorphisms in CC, then Ω\Omega is just a subobject classifier.
  • If SS is the class of all extremal monomorphisms in CC, then Ω\Omega is an extremal subobject classifier.
  • If SS is the class of all strong monomorphisms in CC, then Ω\Omega is a strong subobject classifier.
  • If SS is the class of all regular monomorphisms in CC, then Ω\Omega is a regular subobject classifier.
  • If SS is the class of all effective monomorphisms in CC, then Ω\Omega is an effective subobject classifier.
  • If SS is the class of all strict monomorphisms in CC, then Ω\Omega is a strict subobject classifier.
  • If SS is the class of all κ\kappa-compact monomorphisms, for some regular cardinal κ\kappa, then Ω\Omega is a κ\kappa-compact subobject classifer.

Strong subobject classifiers in particular are important in the definition of a quasitopos.

Let κ\kappa be an inaccessible cardinal. Then κ\kappa-compact subobject classifers are used in the syntactic category of Martin-Löf type theories like book HoTT.

Object classifier

In higher topoi the subobject classifiers are the universal fibrations:

In the (n+1,1)-topos nGrpdn Grpd or (n,0)Cat(n,0) Cat of (n,0)-categories the subobject classifier is the forgetful functor

(n,1)true:(n1,0)Cat *(n1,0)Cat (n,1) true : (n-1,0)Cat_* \to (n-1,0)Cat

from the (n,1)(n,1)-category of pointed (n1,0)(n-1,0)-categories to that of (n1,0)(n-1,0)-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,0)-category the subobject classifier in Set does fit precisely into this pattern:

the set of truth values Ω\Omega may be regarded as the (0,1)-category of (-1,0)-categories (of which there are two) and the one-element set ** is the (0,1)-category of pointed (-1,0)-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).

References

The concept was introduced in

Discussion of the concept can be found in the usual suspects

See also

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

  • Chang Ku Im, On elementary toposes , Bull. Korean Math. Soc. 16, No.2 (1980) pp.55-71. (pdf)

For sheaves

The existence of subobject classifiers in categories of algebras is considered in

  • Peter Johnstone, Collapsed Toposes and Cartesian Closed Varieties , JA 129 (1990) pp.446-480.

  1. For M the class of strong monomorphisms, this is called a weak subobject classifier in Johnstone (2002, p.120).

  2. We mean a nontrivial category, obviously, where “trivial” here means every object is terminal.

Last revised on March 6, 2024 at 13:54:02. See the history of this page for a list of all contributions to it.