11
$\begingroup$

In the book of Szabo "Algebra of Proofs", Definition 13.1.9 introduces an elementary topos as a cartesian closed category with a subobject classifier. On the other hand, many other sources including Johnstone add to this definition that the category should contain limits of finite diagrams. For the proof that the requirement on limits of finite diagrams can be removed, Szabo refers the reader to the paper "Colimits in topoi" by Robert Pare who writes in the second paragraph of the section "Preliminaries on topoi" that the existence of finite limits follows from the existence of equalizers which can be derived from appropriate application of the subject classifier. But for finding a monomorphism from the subobject classifier we should have the corresponding pullbacks in the category. Why such pulbacks exist? The definition of a subobject classifier works only in one direction: given a monomorphism it yields the characteristic morphism. But for the opposite direction (from a characteristic morphism to a monomorphism) the definition does not say anything on the existence of the corresponding pullbacks.

The Question. Is it true that a cartesian closed category with a subobject classifier indeed has pullbacks?

If yes, could you provide a (desirably simple) proof? Thank you.

$\endgroup$
  • 2
    $\begingroup$ Maybe you should clarify how you define subobject classifier in general ? The definition I would consider standard contains the fact that pullback of monomorphisms exists. (And product and pullback of monomorphisms are enough to get all finite limits because fiber product can be constructed as pullback of a diagonal inclusion) $\endgroup$ – Simon Henry May 29 at 19:16
  • $\begingroup$ @SimonHenry I take the definition of a subobject classifier from Wikipedia: en.wikipedia.org/wiki/Subobject_classifier $\endgroup$ – Taras Banakh May 29 at 19:23
  • $\begingroup$ The definition of "subobject classifier" on the Wikipedia page indeed omits any requirement that pullbacks of "True" along arbitrary morphisms to $\Omega$ should exist. On the other hand, the first sentence on that page implicitly includes that requirement. $\endgroup$ – Andreas Blass May 29 at 20:20
  • $\begingroup$ Maybe it's worth mentioning that, if all pullbacks of "true"$:1\to\omega$ exist, then so do all pullbacks of monomorphisms. To pull back a monomorphism $X\to Y$ along a map $f:\to Y$, just compose $f$ with the classifying map of $X\to Y$ and pull "true" back along that composite. $\endgroup$ – Andreas Blass May 29 at 20:22
  • 3
    $\begingroup$ The construction of colimits in a topos was first done by Christian Mikkelsen in his thesis at Aarhus (which is brilliant but difficult to obtain). The monadicity result was then found by Bob Paré. $\endgroup$ – Paul Taylor May 29 at 22:01
18
$\begingroup$

I'll give a counter-example to the claim that having a subobject classifier and being cartesian closed implies the existence of all finite limits. However, this is based on the definition of sub-object classifier given on wikipedia (linked in the comment above) that I would consider as incorrect:

The wikipedia definition (at the time this is written) only asks that for every monomorphism $U \hookrightarrow X$ there is a unique map $X \to \Omega$ such that $U$ is the pullback of the universal subobject $1 \hookrightarrow \Omega$, but it does not ask that every map $X \to \Omega$ be the classifier of some subobject (i.e. that all pullbacks of the universal subobject exist).

If you add the requirement that every map to $\Omega$ classify something, i.e. that pullback of the map $1 \to \Omega$ exists, then it follows that pullbacks of all monomorphisms exist. Moreover pullbacks of monomorphisms, and the existence of finite products imply (in a $1$-category) the existence of all finite limits: A fiber product $B \times_A C$ can be recovered as the pullback of the monomorphism $A \to A \times A$ along $B \times C \to A \times A$.

Consider the category $C$ of finite sets that are not (isomorphic to) the three element sets, with all functions between them. (feel free to replace three by any odd prime).

  • $C$ has products: if $|A \times B| = 3$ then $|A|=3$ or $|B|=3$, so $C$ is stable under product in the category of sets. As it is a full subcategory it follows that these are products in $C$ as well.

  • $C$ has a subobject classifier in the sense of Wikipedia's definition, given by the usual $1=\{\top\} \to \Omega = \{ \bot, \top \}$. Indeed given any mono $A \subset B$ in $C$, its classifying map $B \to \Omega$ in set is also a classyfing map in $C$.

  • $C$ do not have a subobject classifier in the sense of what I would consider the correct definition: the map $4 \to \Omega$ classying $3 \subset 4$ does not have a pullback, indeed if the pullback $P$ existed there should be exactly three maps $1 \to P$, which is the case for no objects of $C$.

  • In particular, this is an example of a pullback in $C$ that does not exists.

  • $C$ is cartesian closed. If $X,Y \in C$ then their exponential $X^Y$ in Set is also in $C$ as $|X^Y|=|X|^{|Y|}=3$ has a unique solution given by $|X|=3$ and $|Y|=1$ hence never happen for $X \in C$. Again as $C$ is a full subcategory stable under product this implies that these are exponential objects in $C$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you so much for the answer, which has clarified the things. $\endgroup$ – Taras Banakh May 29 at 20:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.