11
$\begingroup$

I came up with this question when trying to give a more detailed answer to a question by Tim Campion in a comment to Ingo Blechschmidt's answer to Examples of statements that are valid in every spatial topos.

There is an obvious internalized form of Zorn's lemma for toposes. Basically, you can use the Mitchell-Bénabou language to spell out the following:

given a poset $(P,\leqslant)$, consider the object of pairs $(C,u)$ where $C$ is a chain in $P$ and $u$ is an upper bound of $C$ in $P$. We say that the internal Zorn's lemma IZ holds if whenever the projection $(C,u)\mapsto C$ from this object to all chains of $P$ is epi, the object of maximal elements of $P$ is "as inhabited as $P$ itself", that is, has the same support as $P$.

If you do not care for a more rigorous formulation, skip everything until the questions.

Here is this more rigorous formulation. Given a poset $P$ in a topos $\mathscr S$, we can form the objects $\max(P)\rightarrowtail P$ of maximal elements of $P$ and $\operatorname{chains}(P)\rightarrowtail\Omega^P$ of chains of $P$. We can also form the object of upper-bounded-chains of $P$, call it, say, $\operatorname{ubc}(P)$: it is uniquely determined by saying that $\hom(X,\operatorname{ubc}(P))$ must be in one-to-one correspondence with pairs $(C,u)$, where $C\rightarrowtail X\times P$ is a subobject of $X\times P$ and $u:X\to P$ is a morphism, such that $C$ is a chain and $u$ is an upper bound of $C$, if one considers $u$ as an element of $X^*(P)$ and $C$ as a subobject of $X^*(P)$, in the slice topos $\mathscr S/X$.

Clearly there is a canonical projection $\pi:\operatorname{ubc}(P)\to\operatorname{chains}(P)$, given by sending $(C,u)$ to $C$.

We can then formulate the internal version IZ of the Zorn lemma as follows:

If $\pi:\operatorname{ubc}(P)\to\operatorname{chains}(P)$ is epi, then $\max(P)$ has the same support as $P$; that is, the image of $\max(P)\to1$ is the same as the image of $P\to1$ (where $1$ is the terminal object of $\mathscr S$).

Minimal question: do all toposes satisfy this?

I suspect that, arguing internally, one might deduce from IZ internal choice IC which in turn implies booleannes, but somehow I don't see how to actually do it.

Extended question (again in case the answer to the minimal question is negative): there might be more sophisticated internalizations of the Zorn's lemma. For example, one can consider, for an object $P$, the object $\operatorname{Orders}(P)$ of partial orders on $P$ and then internalize the statement "partial orders with all chains upper-bounded are included in partial orders having a maximal element". Is there a form which would be weaker, in the sense that it holds for some topos which does not satisfy IZ?

Here is a version about which I would like to ask specifically. This actually corresponds on the "classical" side to the variant of the Zorn's lemma with requiring upper bounds for nonempty chains only.

Call an internal poset $(P,\leqslant)$ internally inductive if for any object $X$ and any $C\rightarrowtail X\times P$ which is a chain of $X^*(P)$ in $\mathscr S/X$, the object $U_C\rightarrowtail X^*(P)$ of upper bounds of $C$ has support no less than $C$. That is, the image of the composite $U_C\rightarrowtail X\times P\to X$ contains the image of $C\rightarrowtail X\times P\to X$, where $X\times P\to X$ is the projection.

We then say that IIZ holds in $\mathscr S$ if for every internally inductive poset $P$, the object $\max(P)$ has the same support as $P$, as above.

And the specific instance of my Extended question is,

Which toposes satisfy IIZ? How does it compare to IZ?

Important correction

As Gro-Tsen points out in a comment, this does not make much sense unless I restrict to Grothendieck toposes with Axiom of Choice holding in my set theory. Slightly more generally, one may consider toposes bounded over a topos with AC. Maybe still more generality is possible, but let us stick to this for definiteness.

$\endgroup$
6
  • 2
    $\begingroup$ I don’t have time for a full answer now, but John Bell has a couple of nice papers on Zorn’s Lemma in constructive settings: Zorn's lemma and complete Boolean algebras in intuitionistic type theories (1997), and Some new intuitionistic equivalents of Zorn’s Lemma (2003). In particular, the first shows that a form of Zorn’s lemma (not immediately sure if it’s the same as yours) holds in all Grothendieck toposes. $\endgroup$ Commented Apr 13, 2023 at 10:07
  • 1
    $\begingroup$ @PeterLeFanuLumsdaine Wow, thanks! Shall investigate. $\endgroup$ Commented Apr 13, 2023 at 10:09
  • 2
    $\begingroup$ If you take a model of classical $\mathsf{ZF}$ in which Choice fails (maybe with a limited form of Replacement so the existence of such a model be provable in $\mathsf{ZFC}$), and consider the category of its sets, that forms a (boolean) topos, at least if by “topos” we understand “elementary topos”: I get a headache trying to read your internal Zorn's lemma, but I should hope that in the above context it would simply reduce to Zorn's lemma, and this fails. Right? So are you restricting yourself to Grothendieck toposes? This deserves clarification. $\endgroup$
    – Gro-Tsen
    Commented Apr 13, 2023 at 10:25
  • $\begingroup$ @Gro-Tsen ooooops sorry! Let me incorporate this, thank you very much for pointing this out! $\endgroup$ Commented Apr 13, 2023 at 10:29
  • $\begingroup$ I did it. As for the formulation, yes, I agree it is painful to read. In fact maybe I made a mistake somewhere. But in any case I intended to have it such that in the topos of sets it becomes the plain ordinary Zorn's lemma. $\endgroup$ Commented Apr 13, 2023 at 10:35

1 Answer 1

9
$\begingroup$

Assuming the law of excluded middle internally your formulation of Zorn's lemma is equivalent to the axiom of choice by the usual argument. Now there are Boolean Grothendieck topos in which the axiom of choice fails. Hence they don't satisfies Zorn lemma either.

I think the simplest example of this is to take $G$ to be a non-discrete but pro-discrete localic/topological group (typically $G = \mathbb{Z}_p$ the group of p-addic integer) and consider $\mathcal{T}$ the topos of sets endowed with a continuous (hence smooth) action of $G$ (that is the stabilizer of each point is an open subgroup)

Assuming LEM in the base, $\mathcal{T}$ is clearly boolean (sub-object are $G$-stable subsets and set theoretic complement preserve subobject).

But $\mathcal{T}$ doesn't satisfies either internal nor external choice. For exemple for $G = \mathbb{Z}_p$ the infinite product of all the $\mathbb{Z}/p^k\mathbb{Z}$ with their canonical action is the initial object. (more generally, the product of the $G/U$ for $U$ in a fundamental system of open subgroup is empty unless $G$ is discrete).

Edit: However it should be noted that, assuming Zorn lemma in the base topos, an appropriate version of Zorn lemma is known to holds in every Localic Grothendieck topos (but the topos mentioned above is not localic of course). This is proved as Proposition D4.5.14 in Sketches of an elephant.

More precisely, one take the Zorn lemma to be the statement: "every inductie poset has a maximal element" but where "inductive" is defined as the internal statement "every chain as an upper bound". More precisely prop D4.5.14 shows that if P is an (internally) inductive poset in a localic topos, then it has an (internally) maximal element given by a global section. In particular, it proves the internal statement "there exists a maximal element" is valid.

One also have the stronger version of the internal Zorn Lemma where the quantification over "all inductive poset" is interpreted internally using the Stack semantics, because every slice of a localic topos is localic, and we can apply D4.5.14 in each slice.

The paper by Bell linked in Peter Lumsdain comment, also prove a similar result but for an (at least in appearance) weaker version of Zorn lemma where "inductive" is taken as "every chain has a least upper bound" instead of an upper-bound. Bell explicitly says that he doesn't know how to prove the stronger version of Zorn lemma, but looking at the proof of D4.5.14 it seems to me that the whole point is that both version of Zorn lemma are constructively equivalent: given any poset the poset of chains ordered by inclusion is inductive in Bell's stronger sense, so assuming Bell's version of ZL one get a maximal chain in every poset and an upper bound for a maximal chain has to be a maximal element.

$\endgroup$
12
  • 2
    $\begingroup$ I looked at Bell's paper as well and to me none of the change is significant in the presence of LEM. I can confirm that LEM + ZL => AC holds: The most convincing argument is simply that the internal logic of a topos with LEM (and NNO) is "essentially equivalent" (up to the change of language...) to Bounded ZF, and this proof doesn't rely on any unbounded replacement. Note that the claim Bell makes about ZL being "Strongly persistent" only means it is valid in all localic Grothendieck topos. Where indeed it is well known that LEM valid <=> the locale is boolean <=> internal/external AC valid $\endgroup$ Commented Apr 13, 2023 at 14:12
  • 2
    $\begingroup$ I'm not sure what to add here. Bell ZL is enough to prove AC (assuming LEM) as you need to apply ZL to the the poset of partial section of a surjective map $X \to Y$ which has supremum of chains. So that it is still in line with my previous comment. I don't know if ZL+ holds in all all localic topos - beyond that Bell says he doesn't know how to prove it. I'm not sure what you are asking about WAC, but from what I can see it is also equivalent to AC under LEM, so also fail in the above-mentioned example. $\endgroup$ Commented Apr 13, 2023 at 14:29
  • 2
    $\begingroup$ Regarding comparison between internal logic and standard set theory the most up-to-date reference is probably MIke Shulman's paper arxiv.org/abs/1808.05204 but I think for my previous comment you can replace "bounded ZF" by Zermelo set theory with no changes $\endgroup$ Commented Apr 13, 2023 at 14:34
  • 1
    $\begingroup$ Regarding ZL+ => LEM. I would say no : if Bell is correct and ZL+ holds in localic topos in which 1 is projective, then I believe the assumption that 1 is projective is weaker than Boolean for a localic topos - it has to do with being of covering dimension 0 or something like that. but I'm not 100% sure of what I'm saying here. $\endgroup$ Commented Apr 13, 2023 at 14:41
  • 1
    $\begingroup$ That seems to be also equivalent to ZL: If an inductive poset (in either sense) has a maximal chain, then an upper bound for that chain is a maximal element. $\endgroup$ Commented Apr 15, 2023 at 16:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .