16
$\begingroup$

An elementary topos is a category that:

  1. has finite limits
  2. is cartesian closed
  3. has a subobject classifier

and one can show (with quite a bit of effort) that it has finite colimits.

Is there, starting from the axioms, a quick and easy way to see that it has an initial object? What part of the axioms are really needed to prove this?

Motivation: Occasionally people discuss whether there should be a map $\emptyset \to \emptyset$. If there is not, then we need to stop talking about the empty "set" and $\mathsf{Set}$ fails to have an initial object, hence fails to be a topos. I want to see what part of the axioms above are actually violated by that, i.e. how $\mathsf{Set}$ fails to be a topos.

$\endgroup$
  • 2
    $\begingroup$ For the motivation, I think focusing on a particular axiomatic definition may be the wrong approach. One reason toposes (and ordinary set theory, for that matter) are important is because they encode higher order logic. That every object has an empty subobject is the expression of the fact there are contradictory propositions. $\endgroup$ – Hurkyl Jul 2 '16 at 12:47
10
$\begingroup$

I believe that you can construct the initial object elementarily in the following steps, with no knowledge about monadicity needed.

  1. Recall that we can define for any object $A$ the universal quantification operator $\forall_A : \Omega^A \to \Omega$ as the classifying morphism of the subobject $1 \to \Omega^A$ with transpose given by $1 \times A \to 1 \xrightarrow{t} \Omega$, where $t$ is the universal monomorphism. (In $\mathrm{Set}$, for a family $f : A \to \Omega$ of truth values, $\forall_A(f)$ is the truth value of $\forall x \in A{:}\ f(x)$.)

  2. In particular, we can construct the global element of $\Omega$ denoting falsity as the composition $1 \to \Omega^\Omega \xrightarrow{\forall_\Omega} \Omega$, where $1 \to \Omega^\Omega$ is the transpose of $\Omega \xrightarrow{\mathrm{id}} \Omega$. (In $\mathrm{Set}$, this global element is the truth value of $\forall \varphi \in \Omega{:}\ \varphi$, i.e. $\bot$.)

  3. We then obtain the initial object as the subobject classified by this morphism.

To verify that the constructed object is indeed the initial object, you probably need to know the universal property of $\forall_A$. It is given, with full proof, in Theorem 13.3 of Thomas Streicher's beautiful notes on category theory and categorical logic.

$\endgroup$
  • 1
    $\begingroup$ That's cool! I think it can't get nicer than that :) +1. Spelling the universal property out, one sees that $A\to 1$ factors through the subobject $0\to 1$ you constructed if and only if $A\times\Omega\to\Omega$ factors through $1\to\Omega$, which (see end of my answer) implies that $A$ is initial. $\endgroup$ – Hanno Jul 2 '16 at 15:45
  • $\begingroup$ I'm actually gobsmacked that I didn't think of this. It's literally the straightforward translation of how you define falsehood in the type theory associated with a topos... $\endgroup$ – Malice Vidrine Jul 2 '16 at 18:50
6
$\begingroup$

I know of no quick and easy way to see it. However, Johnstone's Topos Theory has a reasonably nice discussion of why with Lemma 1.31, Theorem 1.34, and Corollary 1.36.

The thrust is that the functor $\Omega^-:\mathcal{E}^{op}\to\mathcal{E}$ in a topos is monadic, and therefore creates all limits. This ends up meaning that $\mathcal{E}^{op}$ has all finite limits because $\mathcal{E}$ does; but $\mathcal{E}^{op}$ has finite limits exactly when $\mathcal{E}$ has finite colimits.

Edit: To round out the answer a little more, I incorporate my comment that the usual proof for finite cocompleteness relies on all three axioms in an essential way. To apply Beck's theorem to $\Omega^-$ one must show mainly that $\mathcal{E}^{op}$ has coequalisers of reflexive pairs, and one gets these by the presence of equalisers in $\mathcal{E}$. One shows that these coequalisers are preserved by using the Beck-Chevalley condition for $\Omega^-$, which relies on the subobject classifier's universal property. And finally, if you don't have all finite limits, none of this gives you all finite colimits. It does, on reflection, seem that "has equalisers of coreflexive pairs" could replace the "finite limits" condition if all you want is an initial object, though.

Thus, if $\mathbf{Set}$ were to somehow lack an initial object, our interpretation of it as a category would need to either

  • fail in Cartesian closure,
  • fail to have some equalisers (and thus also fail in finite completeness),
  • or fail to have a subobject classifier.

Any of these would be pretty hard to swallow, and someone who wanted to deny the empty set worked as an initial object would have the burden of explaining what the objects and morphisms are in their category of sets.

$\endgroup$
  • $\begingroup$ Even if there really is no elementary proof (known), this still leaves me in the dark about, whether the full strength of the axioms are needed to show that an initial object exists. $\endgroup$ – Stefan Perko Jul 2 '16 at 9:36
  • $\begingroup$ @StefanPerko Observe that the functor $\Omega^{-}$ require the existance of $\Omega$ (the subobject-classifier) and of the exponential objects (i.e. the cartesian closedness condition). So Malice answer proves that the axioms are sufficient. Clearly they are not necessary, indeed we are plenty of categories having small colimits (and hence also initial objects) that are not toposes. $\endgroup$ – Giorgio Mossa Jul 2 '16 at 9:49
  • $\begingroup$ @StefanPerko - If you're asking if you can drop one of the three conditions above and still prove an initial object exists, my suspicion is the answer is no; the universal property of the subobject classifier is needed to show the Beck-Chevalley condition holds, and this and equalisers are needed to show that the functor is monadic. $\endgroup$ – Malice Vidrine Jul 2 '16 at 9:51
  • $\begingroup$ @MaliceVidrine Yes, that's what I meant. I am not convinced yet, that your suspicion is well-founded, but perhaps it is. I'll wait and see for now. $\endgroup$ – Stefan Perko Jul 2 '16 at 9:53
  • $\begingroup$ @StefanPerko - I can say with confidence that if it works under a weakening of any of those three conditions, the proof would have to be very different than the standard one, and obscure enough not to be in any of the literature in my library. $\endgroup$ – Malice Vidrine Jul 2 '16 at 9:55
5
$\begingroup$

Outline: An explicit limit construction of the initial object is contained e.g. in Moerdijks-MacLane's Sheaves in Geometry and Topology. I will recall this construction and hopefully argue elementarily that it indeed describes an initial object. Elementary means that it can be formalized in the first-order theory of elementar topoi.

Construction: Let ${\mathscr E}$ be an elementary topos with power functor $P: {\mathscr E}\to {\mathscr E}^{\text{op}}$ and subobject classifier $\Omega=P1$ . Further, denote $\varepsilon_X: X\to P^2 X$ the map corresp. to the evaluation $X\times PX\to \Omega$ corresp. to the subobject $\in_X\in\text{Sub}(X\times PX)$, and $!: P^2 1 \to 1$ the unique morphism.

Claim: The equalizer of $\varepsilon_{\Omega}, P!: P1\rightrightarrows P^3 1$ is an initial object in ${\mathscr E}$.

Proof: Let $X\in {\mathscr E}$ be any object admitting a morphism $f: X\to P1=\Omega$ such that $$\varepsilon_{\Omega} \circ f = P!\circ f: X\to P^3 1.$$ I claim that $X$ is initial in ${\mathscr E}$. (Remark: This seems stronger than the claim, but it is not, since in any topos any morphism to the initial object is an isomorphism; actually, this is a side-product of our proof)

Denote $\chi: A\hookrightarrow X$ the subobject of $X$ corresponding to $f$ and consider the natural bijection $${\mathscr E}(X,P^3 1)\ \cong\ \text{Sub}_{\mathscr E}(X\times P^2 1=X\times P\Omega).$$ IfI didn't mix up things again, under this bijection the morphism $\varepsilon_\Omega\circ f$ corresponds to the pullback of $\in_\Omega$ along $\chi\times\text{id}: X\times P\Omega\to \Omega\times P\Omega$. On the other hand, the morphism $P!\circ f$ corresponds to $A\times P\Omega\stackrel{\chi\times\text{id}}{\to} X\times P\Omega$. Intuitively, the first subobject contains those $(x,T)$ where the set $T$ of truth values contains the truth value of the statement that $x\in X$ belongs to $T$; the second contains those $(a,T)$ for $a\in A$ and any set of truth values $T$.

To see that this forces $X=0$, consider first a third subobject of $X\times P\Omega$, namely the graph of $X\to \Omega\to P\Omega$, where $\Omega\to P\Omega$ is singleton map. Intuitively, it's the set of $(x,\{\chi(x)\})$, i.e. the set $T$ contains exactly the truth value of $x$ belonging to $A$. This subobject is contained in the subobject corresponding to the l.h.s., hence also in $A\times P\Omega$. Projecting on the first factor reveals $A=X$, so both subobjects are in fact the whole of $X\times P\Omega$. Appealing to the intuitive description of the l.h.s. again, this would mean that in the 'context of $X$', any set of truth values contains $1$.

Let's try to formalize this as saying that ${\mathscr E}/_X$ is trivial: Revisiting the formal description of the l.h.s. subobject of $X\times P\Omega$ again for $A=X$, we see that the map $X\times P\Omega\xrightarrow{\text{eval}_1\circ\pi_{P\Omega}} \Omega$ factors through $1\to\Omega$. Restricting to singleton-sets $s: \Omega\hookrightarrow P\Omega$ and using that $\text{eval}_1\circ s = \text{id}_{\Omega}$, we see that $X\times 1\to X\times \Omega$ is an isomorphism.

This map however is the universal monic in the topos ${\mathscr E}/_X$ - this being an isomorphism implies that the only subobjects are the identities, hence ${\mathscr E}/_X$ is trivial. Finally, the triviality of ${\mathscr E}/_X$ implies that $X$ is initial: if $f,g: X\rightrightarrows Y$ are two parallel arrows, then their equalizer $K\to X$ can be regarded a morphism in ${\mathscr E}/_X$, so is an isomorphism, so $K=X$ and $f=g$.

Edit: To show that there exists a morphism $X\to Y$ for any $Y$, note that $X\times Y\to X$ can be viewed as a morphism in ${\mathscr E}/_X$, hence is an isomorphism, and its inverse gives rise to a morphism $X\to Y$.

Note that these argument can be made explicit in the first-order theory of topoi, avoiding 'stepping outside' of ${\mathscr E}$.

$\endgroup$
3
$\begingroup$

For the specific case of the category of nonempty sets:

Consider the sets $\{0\}, \{0, 1\}, \{1\}$ and the maps $$f: \{0\}\rightarrow\{0, 1\}: 0\mapsto 0$$ and $$g:\{1\}\rightarrow\{0, 1\}: 1\mapsto 1.$$ The diagram formed by $f$ and $g$ can only have $\emptyset$ as a limit: indeed, given any set $A$ and maps $f': A\rightarrow \{0\}$, $g': A\rightarrow\{1\}$, we have $f\circ f'=g\circ g'$ iff $A$ is empty.

In particular, note that we're not using the universal property of limits here: the category of nonempty sets doesn't even satisfy the much weaker "commuting cones" property,

"For every finite diagram $D$, there is an object $A$ and morphisms $m_X$ from $A$ to each object $X$ of $D$ such that for each morphism $f: X\rightarrow Y$ in $D$, $f\circ m_X=m_Y$."

$\endgroup$
  • $\begingroup$ "time and time again" was maaybe an exaggeration, sorry. I don't know actually, but: math.stackexchange.com/a/1846253/166694 (see the comments) $\endgroup$ – Stefan Perko Jul 2 '16 at 9:09
  • 1
    $\begingroup$ I am not sure how to understand your answer. I don't "know" yet, that topoi have colimits at all. I want to avoid showing that first (because that is complicated and lengthy). $\endgroup$ – Stefan Perko Jul 2 '16 at 9:10
  • $\begingroup$ @StefanPerko I didn't realize you wanted to avoid colimits - the original version of the question wasn't as clear on this. I'll think a bit more about the problem (I agree the proof that colimits exist is quite hard). $\endgroup$ – Noah Schweber Jul 2 '16 at 9:19
  • $\begingroup$ Okay, I am still trying to understand how this works in an arbitrary topos... $\endgroup$ – Stefan Perko Jul 2 '16 at 9:46
  • $\begingroup$ @StefanPerko You're right, this is just for the category of nonempty sets. For a moment I thought I saw a nice way to construct "disjoint" morphisms using the axioms in a straightforward way, but now I'm not sure. I'll leave this up since it answers the concrete subquestion. $\endgroup$ – Noah Schweber Jul 2 '16 at 9:55
2
$\begingroup$

$\text{Sub}(1) \cong \hom(1, \Omega)$.

If $1$ has no proper subobjects, then there are unique maps $1 \to \Omega$ and $\Omega \to 1$ and so they must be inverses, leading to the horrible situation where the subobject classifier is terminal!

This implies that there are no proper subobjects of any object. Every equalizer must be invertible! Every pair of parallel arrows must be equal!! Every morphism is monic!!! We deduce the category is equivalent to the terminal category. (and, incidentally, therefore has an initial object)

This observation isn't enough to prove that an initial object exists, but proving that $1$ must have a proper subobject in a nondegenerate topos might be enough for your purposes.

$\endgroup$
  • 1
    $\begingroup$ Now find some object which has no proper subobjects. That object is initial. Say, the extension of the formula "For every x of type $\Omega$, $x=true$." This will use the internal logic of the universal quantifier, but will not require knowing the topos has colimits. $\endgroup$ – Colin McLarty Jul 3 '16 at 3:14
1
$\begingroup$

There is a completely elementary way to prove the existence of an initial object in any topos.

Step 1. For every $X$ find a mono $X\hookrightarrow\Omega^X$.
It can be done by considering the characteristic arrow $X\times X\to\Omega$ of the diagonal $(id,id):X\hookrightarrow X\times X$ and then taking its adjoint.

Step 2. Prove that if there is only one arrow from $Z$ to $\Omega$ then there exist arrows from $Z$ to every object $X$.
The uniqueness of $Z\to\Omega$ means that all monos over $Z$ are isomorphic. In particular every mono over $Z$ is isomorphic to $id_Z$. Take a pullback of $X\hookrightarrow\Omega^X$ along any arrow $Z\to\Omega^X$ (e.g. adjoint to $\top!:Z\times X\to\Omega$). It is monic, therefore isomorphic to $id_Z$, so we can take $id_Z$ as the first pullback projection. The second pullback projection $Z\to X$ is the arrow sought.

Step 3. Prove that if there is only one arrow from $Z$ to $\Omega$ and $a,b:Z\to X$ then $a=b$.
Take an equalizer of $a$ and $b$. It's monic, therefore isomorphic to $id_Z$. From $a\,id_Z = b\,id_Z$ we get $a=b$.

Step 4. Find such $Z$ that there is only one arrow from $Z$ to $\Omega$.
There are two evident arrows $\Omega\to\Omega$: $id$ and $(\top!)$. Precompose them with $\pi_2:1\times\Omega\to\Omega$ and consider their adjoints $1\to\Omega^\Omega$. Denote $e:E\to 1$ any solution to this pair of adjoints (there exists at least one such solution -- their equalizer). Then do some algebra: $$ \ulcorner id_\Omega \pi_2 \urcorner e = \ulcorner \top ! \pi_2 \urcorner e $$ $$ id_\Omega \pi_2 (e\pi_1,\pi_2) = \top ! \pi_2 (e\pi_1,\pi_2) $$ $$ \pi_2 = \top ! \pi_2\quad\mbox{as morphisms $E\times\Omega\to\Omega$} $$ Take any arrow $a:E\to\Omega$ and apply the last equation to $(id_E,a)$ obtaining $$ a = \top !_\Omega a = \top !_E $$ The right hand side is independent of $a$, therefore all arrows $E\to\Omega$ coincide. Take $Z=E$.

$\endgroup$

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.