27
$\begingroup$

Zorn’s Lemma applies to posets in which every chain has an upper bound. However, in all applications I know, the poset is also evidently chain-complete — chains have least upper bounds. A few classic such applications:

  • AC, using a poset of “partial choice functions”
  • the Well-Ordering Principle, using a poset of “partial well-orderings” (ordered by end-extension, not simply $\subseteq$)
  • Hahn–Banach, using a poset of “partial functionals defined on subspaces”
  • extension of filters to ultrafilters, using a poset of filters.

Are there any natural applications of Zorn’s Lemma where the poset isn’t chain-complete, or where chain-completeness is less obvious than existence of upper bounds?

(Indeed, all examples I know are equally obviously directed-complete. Under AC, this is equivalent to chain-complete, but constructively, directed-completeness is stronger. For those wondering why I’m caring about use of AC while considering Zorn’s Lemma, note that constructively, ZL does not imply AC — this is shown in John Bell’s very nice analysis Zorn's lemma and complete Boolean algebras in intuitionistic type theories, JSL 1997, https://doi.org/10.2307/2275642. His surprising (to me) insight is that ZL itself doesn’t imply LEM or AC — most applications, including the classical proof of ZL=>AC, use LEM for the final step “a maximal partial object must be total”.)

$\endgroup$
4
  • 5
    $\begingroup$ I for one would be interested just in some natural examples of posets which have upper bounds for chains but not least upper bounds (or less obviously so), even if there's no particular application of Zorn's lemma in such a poset. $\endgroup$ – Tim Campion Apr 18 at 19:01
  • 2
    $\begingroup$ Can we extend any given partial order in which every chain has an upper bound to one where every chain has a least upper bound? I would want to add new nodes to serve as the least upper bound of any chain lacking a least upper bound. But I'm not sure whether this argument would inadvertantly use LEM (since frankly I can never tell whether I am inadvertantly using LEM or not—it is a core part of my mathematical thinking). $\endgroup$ – Joel David Hamkins Apr 18 at 19:02
  • 3
    $\begingroup$ @JoelDavidHamkins You can always Ind-complete. That is, embed $P$ into $Ind(P)$, the poset of downward-closed, upwards-directed subsets of $P$, ordered by inclusion. The poset $Ind(P)$ has least upper bounds for chains, and more generally (but equivalently in ZFC) for directed sets, and is universal with this property. This doesn't require anything more than $P$ being a poset. Now I'm realizing you were probably aware of this and asking about whether this is still true in less than ZFC... for that I suspect the answer is yes but I don't really know... $\endgroup$ – Tim Campion Apr 18 at 20:22
  • 3
    $\begingroup$ @TimCampion: The answer is yes — Ind-completion, constructed exactly as you describe, is the “free dcpo on a poset” in IHOL (i.e. the logic of an elementary topos), if I’m not mistaken. So it doesn’t rely on any kind of choice or excluded middle. $\endgroup$ – Peter LeFanu Lumsdaine Apr 18 at 21:54
15
$\begingroup$

Although this is not an application of Zorn's lemma, the Hausdorff order of almost inclusion on subsets of $\mathbb{N}$ is a natural order where every chain has an upper bound, but many chains do not have least upper bounds.

Namely, the almost-inclusion relation $A\subseteq^*B$ for subsets $A,B\subseteq\mathbb{N}$ holds when all but finitely many elements of $A$ are in $B$. One can take equivalence classes with respect to the almost equal relation $A=^*B$, and induce the order on the quotient.

Every chain has an upper bound in its union, but nontrivial countable chains never have least upper bounds, as Hausdorff proved. So this is a natural order where every chain has an upper bound, but many chains do not have least upper bounds.

Another type of example occurs with the Turing degrees. Every countable chain in the Turing degrees has an upper bound, simply by encoding the whole chain, but no nontrivial countable chain has a least upper bound in light of the exact pair phenomenon.

If one were simply to add a node atop the whole structure, then every chain would have an upper bound, but no nontrivial countable chains would have least upper bounds, providing another example.

I suppose another trivial example would be the rational unit interval $\mathbb{Q}\cap[0,1]$. Clearly that isn't what you are looking for.

$\endgroup$
12
  • 1
    $\begingroup$ Aronszajn trees are never chain-complete. Indeed, no branching $\omega_1$ tree can be chain complete, since it would have to have continuum many nodes on level $\omega$. $\endgroup$ – Joel David Hamkins Apr 18 at 20:41
  • 1
    $\begingroup$ This is very vague and speculative, but I wonder if there is some reasonable partial order on countable graphs with the Rado graph being the unique maximum, where you could use Zorn's lemma to prove its existence... $\endgroup$ – Sam Hopkins Apr 18 at 20:54
  • 1
    $\begingroup$ @SamHopkins Well, the countable random graph is universal for countable graphs, so we could consider the countable graphs under the embedded induced subgraph relation. Every chain would have an upper bound, because there is a universal graph. But I think there wouldn't be least upper bounds, since there are strict subgraphs that are isomorphic to the whole thing. This is something like the Hausdorff order situation. $\endgroup$ – Joel David Hamkins Apr 18 at 20:58
  • 1
    $\begingroup$ But one should consider the pre-order quotient, since the embedding order itself is not anti-symmetric. And then things get tricky without AC, just as in my first comment above. $\endgroup$ – Joel David Hamkins Apr 18 at 21:06
  • 2
    $\begingroup$ @TimCampion The order of countably infinitely many side-by-side copies of the rational unit interval has that property. $\endgroup$ – Joel David Hamkins Apr 19 at 7:43

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.