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$
18
  • 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$ May 29, 2020 at 19:16
  • $\begingroup$ @SimonHenry I take the definition of a subobject classifier from Wikipedia: en.wikipedia.org/wiki/Subobject_classifier $\endgroup$ May 29, 2020 at 19:23
  • 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$ May 29, 2020 at 22:01
  • 1
    $\begingroup$ It should also be noted that the reason why this confusion has arisen is because of ambiguity in the usage of cartesian [closed]. For Freyd and Lawvere, cartesian meant having all finite limits, whereas in computer science it has come to mean just products. $\endgroup$ May 30, 2020 at 8:27
  • 1
    $\begingroup$ @PeterLeFanuLumsdaine. I exchanged emails with Christian Mikkelsen sometime after the above comment and found out about his website, but I didn't know about TAC - that's a useful stable citatation, thanks. (His website is mainly about his own impressive genealogical research, with about 250 of his and his wife's ancestors! It also shows when Denmark switched from patronymics to surnames.) $\endgroup$ Jan 18, 2023 at 21:58

1 Answer 1

20
$\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$.

$\endgroup$
1
  • $\begingroup$ Thank you so much for the answer, which has clarified the things. $\endgroup$ May 29, 2020 at 20:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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