(in category theory/type theory/computer science)
of all homotopy types
of (-1)-truncated types/h-propositions
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 $\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 : * \to \Omega$ such that every monomorphism $A \hookrightarrow B$ in the topos (hence every subobject) is the pullback of this morphism along a unique morphism (the characteristic morphism of $A$) $B \to \Omega$.
In this sense $\Omega$ is the classifying object for subobjects and $true : * \to \Omega$ the generic subobject.
That the existence of a subobject classifier in a category is a very powerful property that induces much other structure 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 classifier^{1}: 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$.
In a category $C$ with finite limits, a subobject classifier is a monomorphism $true : * \to \Omega$ out of the terminal object, such that for every monomorphism $U \to X$ in $C$ there is a unique morphism $\chi_U : X \to \Omega$ such that there is a pullback diagram
See for instance (MacLane-Moerdijk, p. 32).
Some terminology:
If it exists, the object $\Omega$ is also called the object of truth values, a global element $K \to \Omega$ is called a truth value and the element $true : * \hookrightarrow \Omega$ is the truth value true, where all these terms allude to the internal logic of the category $C$.
Note that the subobjects classified by the truth values are subterminal objects.
The morphism $\chi_U$ is also called the characteristic map or classifying map of the subobject $U \hookrightarrow X$.
If $C$ has finite limits and is in addition a locally small category, then it has a subobject classifier precisely if the subobject-assigning presheaf
is representable. In this case the representing object is the subobject classifier: there is a natural isomorphism
in $X \in C$.
Moreover, in this case $C$ is well powered.
This appears for instance as (MacLane-Moerdijk, prop. I.3.1).
In more detail: given a morphism $f: c \to d$ in $C$, the function
takes a subobject $i: t \hookrightarrow 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 $\Omega$ together with a subobject $t: T \hookrightarrow \Omega$ which is universal, meaning that given any subobject $i: s \hookrightarrow c$, there is a unique morphism $f: c \to \Omega$ such that $i$ is obtained as the pullback of $t$ along $f$.
To see that a subobject classifier induces such a natural isomorphism, we need that the morphisms $Sub(f)$ for $f \in Mor(C)$ corresponds to the morphisms $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 $\phi : X \to \Omega$ a commuting diagram
whose commutativity says that every element of $Sub(X)$ is the pullback along some $\phi : X \to \Omega$ of the subobject of $\Omega$ corresponding under the natural isomorphism to $Id : \Omega \to \Omega$.
By further playing around with this one finds that this latter subobject of $\Omega$ has to be a terminal object.
In the category of sets, the 2-element set $\mathbf{2} = \{f, t\}$ plays the role of $\Omega$; the morphism $t: 1 \to \mathbf{2}$ just names the element $t$. Given a subset $S \subseteq X$, the characteristic function $\chi_S: X \to \mathbf{2}$ is the function defined by $\chi_S(x) = t$ if $x \in S$, and $\chi_S(x) = f$ if $x \notin S$.
It is not usually true in toposes that $\Omega$ is the coproduct $\mathbf{2} = 1 + 1$; toposes where that occurs are called Boolean. Thus the category $Set$ of sets is a Boolean topos, as is the presheaf topos $Set^G$ when $G$ is a groupoid.
The subobject classifier in a presheaf topos $PSh(S)$ is the presheaf that sends each object $U \in S$ to the set $sieves(U)$ of sieves on it, equivalently the set of subobjects of the representable presheaf $Y(U)$: $\Omega : U \mapsto sieves(U)$.
The corresponding morphism $true : * \to \Omega$ of presheaves is the natural transformation that picks over each object the maximal sieve $true_U = maximal_{sieves(U)} : * \to sieves(U)$.
As a special case of presheaf toposes, for $G$ a discrete group and $G Set = [\mathbf{B} G, Set]$ the topos of permutation representations, there are precisely two sieves on the single object of the delooping groupoid $\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 $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 $\Omega$ will become richer: Its underlying set has elements all left ideals, with $m\in M$ acting on a left ideal $L$ by mapping it to the left ideal $\{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!)
If one views a presheaf as a set varying (, or evolving) over $S$, then the subobject classifier can 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$ 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.
An example of a non-Boolean topos is the category of sheaves over a “typical” topological space $X$ 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 $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.
Let $\mathcal{E}$ be a topos and $X \in \mathcal{E}$ any object. Write $\mathcal{E}/X$ for the corresponding over-topos.
The subobject classifier of $\mathcal{E}/X$ is $p_2 : \Omega_{\mathcal{E}} \times X \to X$.
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 \to *$ and hence $p^* \Omega_{\mathcal{E}}\simeq \Omega_{\mathcal{E}} \times X$.
But the statement is also easily directly checked.
The category $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.
Suppose a category $\mathbf{C}$ has a subobject classifier; this entails some striking structural consequences for $\mathbf{C}$. We list a few here:
Every monomorphism in $\mathbf{C}$ is a regular monomorphism, i.e., is an equalizer of some pair of maps.
For $\chi_i: X \to \Omega$ the characteristic map of a mono $i: A \to X$, we find that $i$ is the equalizer of a pair of maps $X \rightrightarrows \Omega$:
$\mathbf{C}$ is balanced, i.e., a morphism in $\mathbf{C}$ is an isomorphism iff it is both monic and epic.
“Only if” is trivial. The “if” comes from the fact that an epic (epimorphic) equalizer must be an isomorphism, for if $i: A \to X$ is the equalizer of $f, g: X \rightrightarrows Y$ and $i$ is epic, then $f = g$, whence $1_X$ is their equalizer, so $i: A \to X$ must have been an isomorphism.
Any two epi-mono factorizations of a map in $\mathbf{C}$ are canonically isomorphic.
Suppose $i p = j q$ where $p, q$ are epic and $i, j$ are monic. Since $j$ is regular, it is the equalizer of some parallel pair $f, g$ as in the diagram
so that $f i p = f j q = g j q = g i p$, whence $f i = g i$ since $p$ is epic, whence $i$ factors through $j$ as $j$ is the equalizer: $i = j k$ for some $k: B \to C$. Then also $k p = q$ since $j k p = i p = j q$ and $j$ is monic. We have that $k$ is monic since $i$ is, and $k$ is epic since $q$ is. Thus $k$ is an isomorphism.
Already these results impose some tight restrictions on $\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 5 below), or obtained via the Yoneda lemma since the collection of subobjects of any object is an external poset.
Similarly, since we assume that $\mathbf{C}$ is finitely complete, each subobject poset $Sub(X)$ has intersections (gotten as pullbacks or fiber products of pairs of monics $i: A \to X,j: B \to 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 $\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:
There is an internal implication operator
uniquely specified by the internal condition
Construct $\subseteq \hookrightarrow \Omega \times \Omega$ as the equalizer of the pair of maps
and then define $\Rightarrow: \Omega \times \Omega \to \Omega$ to be the characteristic map of $\subseteq \hookrightarrow \Omega \times \Omega$. Now if $\chi_u, \chi_v$ are two maps $X \to \Omega$, one calculates that $w \hookrightarrow X$ is contained in the subobject classified by $\chi_u \Rightarrow \chi_v$ iff $w \cap u = w \cap u \cap v$, which is just a way of saying $w \cap u \leq v$.
In every subobject poset $Sub(X)$, meets distribute over any joins that exist.
Because $U \cap -$ is left adjoint to the external operator $U \Rightarrow -$ on $Sub(X)$, it preserves any joins that happen to exist in $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 $\Omega^X$ for every object $X$. In particular, every object $X$ embeds into an injective object by the singleton monomorphism $X\to\Omega^X$: ‘A topos has enough injective objects!’. More generally, injective objects in a topos are percisely the ones that are retracts of some $\Omega^X$ (Cf. Borceux 1994, p.315; Moerdijk-MacLane 1994, p.210).
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.
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 category^{2} 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:
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:
Even though all monos in Grp are regular, we can kill off $Grp$ by observing that if $t: 1 \to \Omega$ were a subobject classifier, the proof of Proposition 3 indicates that every mono $i: A \to X$ would have to be the kernel of $\chi_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 $i_1: A \to A \oplus A$, $i_2: A \to A \oplus A$, and $\Delta: A \to A \oplus A$. Then $i_1 \vee i_2 = \top$, whereas $i_1 \wedge \Delta = \bot = i_2 \wedge \Delta$. Under distributivity we have
but $\Delta = \bot$ forces $A = 0$. So the only such category that can have a subobject classifier is trivial.
In higher topoi the the subobject classifiers are the universal fibrations:
in the (n+1)-topos $n Cat$ 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 $\mathbf{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).
quasitopos where a weaker notion of subobject classifier only classifies strong monomorphisms.
classifying space, classifying stack, moduli space, moduli stack, derived moduli space
Francis Borceux, Handbook of Categorical Algebra 3 , Cambridge UP 1994.
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)