## Need help understanding a topos theory proof (any topos generated by subobjects of 1 in whose subobject lattices are complete and Boolean satisfies AC)

Hi all, I'm reading Mac Lane & Moerdijk's book "Sheaves in Geometry and Logic" and I don't understand a proof; sorry if this is the wrong place to ask, if there's somewhere better please let me know.

The proof in question is of Proposition VI.1.8 (page 276 in the paperback), which states:

Let $\mathcal{E}$ be a topos which is generated by subobjeccts of $1$, and moreover has the property that for each object $E$, $\mathrm{Sub}(E)$ is a complete Boolean algebra. Then $\mathcal{E}$ satisfies the axiom of choice.

Here the axiom of choice is the statement that any epimorphism $p: X \to I$ has a section $s: I \to X$, i.e. $ps = 1_I$. The proof starts as follows:

Let $p: X \to I$ be an epimorphism in $\mathcal{E}$. By completeness of $\mathrm{Sub}(I)$, we can apply Zorn's lemma and find a maximal subobject $m: M \to I$ such that $p$ has a section $s: M \to X$, i.e., $ps = m$.

I don't see how to show that Zorn's lemma applies here. Presumably I need to show that, given a linearly ordered set of subobjects $m_i: M_i \to I$ of $I$, $m_i = m_j k_{ij}$ for some $k_{ij}: M_i \to M_j$ whenever $m_i \leq m_j$, together with a set of sections $s_i: M_i \to X$ such that $p s_i = m_i$, $s_j k_{ij} = s_k$, there exists a section $s: M \to X$ such that $ps= m$, where $m: M \to I$ is the least upper bound in $\mathrm{Sub}(I)$ of the $m_i$'s, and such that the restriction of $s$ to each $M_i$ is $s_i$. It seems plausible that $m: M \to I$ will turn out to be a colimit in $\mathcal{E}/I$ of the collection $m_i: M_i \to I$, from which the required result would follow easily, but I don't know how to prove this. Can anybody help?

-

Your approach is absolutely right: apply Zorn's lemma to the poset of pairs $(M,s)$ where $M \subseteq I$ is a subobject and $s: M \to X$ is a partial section of $p$.

As you say, to see that this poset is chain-complete, we just need to show that the least upper bound in $\newcommand{\Sub}{\mathrm{Sub}} \Sub(I)$ of a chain ${M_i}$ is in fact a colimit in $\mathcal{C}/I$, and hence that the sections also extend.

The key point here is that as long as the chain is inhabited, this is a filtered colimit. Filtered colimits are computed in $\Sub(I)$ just as colimits in $\newcommand{\C}{\mathcal{C}}\C$ (Charles Rezk's answer has just appeared, and shows this nicely); and all colimits in $\C/I$ are computed just as colimits in $\C$; so filtered colimits in $\Sub(I)$ are colimits in $\C/I$, and we're done.

…at least modulo the question of the empty chain! but this is easy to fix, in (at least) two ways. The simplest way is just to look at the case of the empty chain separately, and see that it's trivial. A nicer way (to my taste) is to state Zorn's lemma as “any (inhabited chain)-complete poset has a maximal element above any given element”. Neither of these feels quite right to me here — both seem a little ad hoc — but they do at least both work :-)

-
 Thanks for your reply. I can see how showing that filtered colimits in $\mathrm{Sub}(I)$ coincide with those in $\mathcal{C}$ gives me the result I want. However I do not see how Charles's answer shows this, can you explain? Regarding your last paragraph, the version of Zorn's lemma I know says that a non-empty poset in which every chain has an upper bound has a maximal element; since any element is an upper bound for the empty chain, this case is automatic for any non-empty poset. – Phil Wild Sep 12 2010 at 17:39 Ah… like Charles, I had thought we were working with Grothendieck not elementary toposes and so could assume $\mathcal{E}$ was complete. Hmmm… – Peter LeFanu Lumsdaine Sep 13 2010 at 3:15

I'll try to show that a filtered colimit of a diagram of subobjects is still a subobject, which I suppose should include your linearly ordered diagram as a special case.

A map $X\to I$ is a subobject (i.e., a monomorphism), if and only if the projection maps $X\times_I X\to X$ from the fiber product to either of the factors are isomorphisms. If I have a family $X_i\to I$ of such monomorphisms indexed by a filtered category $C$, then $\mathrm{colim}_{i\in C} X_i \to \mathrm{colim}_{i\in C} I$ has to be monomorphism, since filtered colimits preserve finite limits, and because $\mathrm{colim}_{i\in C}I \approx I$ since $i\mapsto I$ is a constant diagram on the filtered category $C$.

(Possibly, when I say "filtered", I really mean "cofiltered". Can't figure out which is which.)

Added. I was thinking about a Grothendieck topos, which is cocomplete. But it seems you (and Moerdijk and Mac Lane) want a proof which works in an elementary topos, and I don't know what to do in that case.

The key line in the proof seems to be "By completeness of $\mathrm{Sub}(I)$ ..." Presumably, if $\mathrm{Sub}(I)$ is complete, we can form arbitrary "intersections" of subobjects; so $\mathrm{colim} X_i$ should be the intersection of all subobjects $Y$ of $I$ which contain all the $X_i$'s.

I don't know why $\mathrm{Sub}(I)$ should be complete in an elementary topos. It is mentioned (for instance, on p. 491) that in a cocomplete topos $\mathrm{Sub}(I)$ is a Heyting algebra, so is complete. So the proof should work in that case.

-
 Sorry if I'm being thick, but I don't follow your reply. Are the colimits you refer to those in the original topos $\mathcal{E}$? If so then how do I know that they exist? The completeness of the subobject lattices shows that the corresponding colimits exist in $\mathrm{Sub}(I)$; I don't see how it follows that $\mathcal{E}$ itself has all relevant colimits. – Phil Wild Sep 12 2010 at 17:46 Ah, I was thinking of a Grothendieck topos. So "topos" means "elementary topos" here? – Charles Rezk Sep 12 2010 at 19:02 Yes, I think the proposition is supposed to apply to elementary topoi. I don't understand your comment that you "don't know why \$\mathrm{Sub}(I) should be complete [...]" - I don't think it's supposed to be true in general, it's just one of the hypotheses of the proposition. – Phil Wild Sep 12 2010 at 23:10 Oh, it's a hypothesis! I missed that. – Charles Rezk Sep 13 2010 at 3:49