Applications of Zorn’s lemma that aren’t chain-complete/directed-complete?

Question

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”.)

Answer 1

On the one hand, one might expect that there can be no fully satisfactory example of the phenomenon, in light of the observations mentioned in the comments, namely, that every partial order fulfilling the Zorn's lemma hypothesis can be extended to one in which also every chain has a least upper bound. In effect, one adds nodes to play the roles of those least upper bounds.

The point is that instance of the phenomenon that someone might present can immediately be criticized as unnatural on the grounds that it is incomplete — by forming the completion, we could have chosen an equivalent but better version of the poset, one achieving exactly the same maximal elements, but in which every chain has a least upper bound.

In this sense, the question is fundamentally concerned with whether there are natural partial orders in which every chain is bounded but for which the least upper bound property fails. Indeed there are, and I shall mention several.

Let me begin by observing that every application of Zorn is equivalently made with an order not having the LUB property.

Duplication orders. Take any partial $\mathbb{P}$ and consider the duplication order $\mathbb{P}^*$, in which every element has been duplicated, replaced with two or more clones that are incomparable to each other but ordered with respect to the other elements according to the original order. Every chain in $\mathbb{P}^*$ has an upper bound, if this was true for $\mathbb{P}$, but now there are no least upper bounds for chains not having a largest element, since any of the clones works equally well. The duplication construction is often used for various purposes in mathematics, and this example shows furthermore that every application of Zorn's lemma can be turned into an example of the requested incomplete phenomenon.

But let me also mention several other examples of naturally occuring partial orders in which every chain has an upper bound, but many chains do not have least upper bounds.

Hausdorff order. 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.

Turing degrees and the exact pair phenomenon. Another type of partial 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, by which every increasing countable chain admits (diverse, nonunique) pairs above, such that any point below both is below something in the chain.

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. But see this related question, Does every countable set of Turing degrees have an upper bound, without AC? So the Turing degrees are an interesting case in the absence of AC.

Mod(T). Consider the class of models of $T$, a first-order theory. This is naturally ordered by the submodel relation, but the property that unions of chains of models of $T$ is still a model of $T$ is equivalent to having an $\forall\exists$ axiomatization. Such kinds of theories are quite common, because with $\forall\exists$ assertions the theory can express certain basic closure properties. But some theories $T$ do not admit such an axiomatization, and in this case, the union of a chain of models of $T$ will not generally be a model of $T$, but by compactness there will always be upper bounds. For example, if $T$ is the theory of a dense linear order with a largest element, then every chain is contained in a model of $T$, but we will often have a choice in placing a new largest element.

Surreals. The class of surreal numbers have the property that every set of surreals is bounded, but no set of surreal numbers has a least upper bound or greatest lower bound, except by containing a largest or least element already. The reason is that for any set $A\subset\text{No}$ with no largest element and any upper bound $A<b$, there will be smaller upper bounds $A<c<b$ added at the next available stage after all the elements of $A$ and $b$.

Conway games. More generally, the Conway games generally provide a nonlinear order with the same property. The Conway games admit a natural order (see this article), and while every set of games is bounded, chains do not generally have least upper bounds.

The last few examples are proper class examples, and they only exhibit the every-chain-is-bounded property for set-sized chains. That feature is not sufficient to produce maximal elements via Zorn — for example, every set of ordinals is bounded, but there is no largest ordinal. Nor are there maximal surreal numbers nor maximal Conway games.

Answer 2

I hope to both answer the question, and at the say time (in Peter's words) "strengthen the (circumstantial) evidence that any examples must be very rare/obscure". I won't attempt to avoid AC or LEM.

A natural class of nonexamples are algebras (in the universal algebra sense) whose operations have finite arity. The union of a chain of algebras is also an algebra, and this is a least upper bound in the poset of algebras under inclusion. So it is extremely unlikely that you would see Zorn's lemma used in such an algebraic setting without also seeing the chain-complete condition.

However, a natural class of examples are algebras with operations of infinite (fixed) arity.

At the risk of making the example feel contrived, but for the sake of simplicity and concreteness, consider the class $X$ of algebras defined via a single $\omega$-ary operation $x$ subject to no relations.

Claim: Given any nonempty set $S$, there is a "free" $X$-algebra satisfying no relations except the identity relations, defined on a set containing $S$.

Proof 1: By transfinite recursion we build up new elements. At the base case, just start with $S_0=S$. At successor steps, let $S_{\alpha+1}$ be the set where we append to $S_{\alpha}$ all "formal terms" of the form $x(\underline{s})$ where $\underline{s}$ is an $\omega$-sequence from $S_{\alpha}$. Finally, at limits, take the union of the previous steps. Check that this process stabilizes at the first uncountable ordinal.$\square$

Proof 2: Let $P$ be the poset of triples $(T_1,T_2,y)$, where $T_2\supseteq T_1\supseteq S$ are sets, and $y$ is a function $y\colon T_1^{(\omega)}\to T_2$ (interpreted as defining $x$ on part of $T_2$), subject to allowing no nontrivial relations. We order this poset by saying $(T_1,T_2,y)\leq (T_1',T_2',y')$ when $T_1\subseteq T_1'$, $T_2\subseteq T_2'$, and $y$ is a restriction of $y'$.

This poset does not have chain completeness on some countable chains. It does have upper bounds of we also allow $T_1=T_2=V$ (however, to avoid issues with proper classes of chains, we can take $T_1$ and $T_2$ to be elements of some universe [in the Grothendiek sense], or equal that universe.) Apply the general version of Zorn's lemma.$\square$

Note: To see that the poset in the previous proof is not chain complete, consider the following example. Let the sets $S_{\alpha}$ be the sets from proof 1. Let $x_{\alpha}\colon S_{\alpha}^{(\omega)}\to S_{\alpha+1}$ be the map sending a sequence $\underline{s}$ to the formal term $x(\underline{s})$.

Consider the initial countable chain $(S_0,S_1,x_0)<(S_1,S_2,x_1)<\ldots$. Any upper bound $(T_1,T_2,y)$ on this chain must have $T_1\supseteq S_{\omega}:=\bigcup_{n<\omega}S_n$. After restricting $y$ to $S_{\omega}^{(\omega)}$, and replacing $T_2$ by the union of $T_1$ and the image of this restricted map, we may as well assume $T_1=S_{\omega}$.

However, $\bigcup_{n<\omega} x_n$ is only a partial function on $S_{\omega}^{(\omega)}$, and there are multiple distinct ways to extend that partial function to a total function. So there is no least upper bound on the given chain. (There are minimal upper bounds though, each looking essentially just like $(S_{\omega},S_{\omega+1},x_{\omega})$.)

There are aspects of this example that can be generalized to make it less trivial and less contrived, but I hope it gives at least one example of the sort of thing you were looking for.

Edited to add another example not needing any proper classes: Let $U$ be any set (finite or infinite). Let $P$ be the collection of all $X$-algebra structures (whether free or not) on $U$. We can make $P$ into a poset by the usual subalgebra relation. This poset is chain complete (which takes a little work), but does not have least upper bounds on any chains of countable cofinality.