# Suprema of directed sets

Let $$(X, \le)$$ be a partially ordered set. We call a subset $$S \subseteq X$$...

• ... a chain if each two elements in $$S$$ are comparable with respect to $$\le$$ (in other words, $$S$$ is linearly ordered with respect to $$\le$$).

• ... directed if for all $$x,y \in S$$ there exists $$z \in S$$ that dominates $$x$$ and $$y$$.

Obviously, every chain is directed.

Question. Assume that every chain in $$X$$ has a supremum. Does it follow that every directed set in $$X$$ has a supremum?

Remarks.

(1) By Zorn's lemma, $$X$$ has a maximal element (in fact, every element of $$X$$ is dominated by a maximal element of $$X$$).

(2) Since the empty set is a chain and thus has a supremum, it follows that $$X$$ has a smallest element (though this doesn't seem to be particularly relevant to the question).

(3) Let $$D \subseteq X$$ be directed. We cannot apply Zorn's lemma directedly to $$D$$ since the supremum of a chain in $$D$$ might not be in $$D$$. What we can do is to add the set of all supremuma of subsets of $$D$$ (whenever they exist) to $$D$$, and thus obtain a new set $$\tilde D$$. Then $$\tilde D$$ is closed with respect to taking suprema, but I cannot see if (and why) $$\tilde D$$ is directed.

Actually, the answer to the question is yes if and only if this set $$\tilde D$$ is always directed: the implication "$$\Rightarrow$$" is trivial, and the implication "$$\Leftarrow$$" follows from applying Zorn's lemma to $$\tilde D$$ and from the fact that a maximal element in a directed set is always the supremum of this set.

(4) In general, a directed set does not necessarily contain a co-final chain. For instance, let $$\mathcal{F}$$ denote the set of all finite subsets of $$\mathbb{R}$$, ordered by set inclusion. Obviously, $$\mathcal{F}$$ is directed; but every union of a chain of finite sets if at most countable, so $$\mathcal{F}$$ does not contain a co-final chain.

(5) Let $$D \subseteq X$$ be directed. We can apply Zorn's lemma to the set $$\mathcal{D}$$ of all directed subsets of $$D$$ that have a supremum in $$X$$, or to the set $$\mathcal{S}$$ of all subsets of $$D$$ that have a supremum in $$X$$; so $$\mathcal{D}$$ and $$\mathcal{S}$$ both have a maximal element $$D_{\max}$$ and $$S_{\max}$$, respectively. But I see no way to show that $$D_{\max}$$ or $$S_{\max}$$ is co-final in $$D$$ (and thus equal to $$D$$).

(6) If $$X$$ is a lattice (i.e., every (non-empty) finite subset of $$X$$ has a supremum), then the answer to the question is yes: Indeed, let $$D \subseteq X$$ be directed, and let $$\mathcal{S}$$ denote the set of all subsets of $$D$$ that have a supremum in $$X$$. Then $$\mathcal{S}$$ contains all finite subsets of $$D$$, and $$\mathcal{S}$$ is stable with respect to monotone unions (i.e., unions of chains). This implies that $$\mathcal{S}$$ equals the power set of $$D$$, so in particular, $$D \in \mathcal{S}$$.

Motivation. In a preprint of mine I briefly considered a similar question in the context of ordered vector spaces, and I remarked that I do not know the answer in this specific vector space setting. Now, I'm about to submit a revision of this preprint, and I noted that I do not even know the answer for general partially ordered sets (without any vector space structure).

• Even though this isn't relevant to your question, I think it's still interesting to point out that the constructive versions of these notions (and relations to fixed-point theorems) appear in the paper “On the Bourbaki-Witt Principle in Toposes” by Bauer and Lumsdaine (except that “directed” is defined as meaning that every finite subset has an upper bound, including the empty set, so: directed+inhabited), and IIUC, it follows from this paper that “chain-complete ⇒ directed-complete” does not hold constructively. – Gro-Tsen Dec 11 '20 at 10:17

## 1 Answer

Yes, a poset that has suprema of all chains also has suprema of all directed sets. This is known, and I vaguely recall seeing it attributed to Solovay. The proof consists of showing, by induction on cardinals $$\kappa$$, that having suprema of all chains implies having suprema for all directed set of size $$\leq\kappa$$.

The case of finite $$\kappa$$ is trivial, since a finite directed set has a top element. The case of $$\kappa=\aleph_0$$ is almost trivial, since a countable directed set contains a cofinal chain. So assume from now on that $$\kappa$$ is uncountable and that $$D$$ is a directed subset of $$X$$ with $$|D|=\kappa$$.

Write $$D$$ as the union of an increasing (with respect to $$\subseteq$$) transfinite sequence of subsets $$D_i$$, each of cardinality $$<\kappa$$. (If $$\kappa$$ is a regular cardinal, then this sequence necessarily has length $$\kappa$$, but if $$\kappa$$ is singular then the sequence can be shorter.) We may assume that each $$D_i$$ is also directed; just choose for each pair in $$D$$ an upper bound in $$D$$, and close each $$D_i$$ under the "chosen upper bound" function. (The cardinality of the closure will be at most the maximum of $$|D_i|^2$$ and $$\aleph_0$$, so it is still $$<\kappa$$.)

So, by induction hypothesis, each $$D_i$$ has a supremum $$s_i$$ in $$X$$, and, since the $$D_i$$ form an $$\subseteq$$-increasing sequence, their suprema $$s_i$$ form a $$\leq$$-increasing sequence in $$X$$. By hypothesis, the sequence of $$s_i$$'s has a supremum $$x$$ in $$X$$, and it is easy to check that this $$x$$ also serves as the supremum of $$D$$.

• Thanks a lot! I could really kick myself... Of course, I've tried induction over the cardinality of $D$, but when I did so, I didn't get how I can choose each $D_i$ to be directed... – Jochen Glueck Dec 3 '20 at 3:04
• Finally, I have also found this result in a book: Proposition 1.5.9 in "Universal Algebra (1981)" by Paul M. Cohn. – Jochen Glueck Dec 21 '20 at 3:48
• By the way, is it fine with you if I thank you for your assistance in the acknowledgements section of an article where I use this result? – Jochen Glueck Dec 21 '20 at 3:48
• @JochenGlueck Yes, that's fine, but please make sure the wording doesn't let people think the result is due to me. – Andreas Blass Dec 21 '20 at 12:38
• Thank you for your response. I've made sure that no such misunderstanding can occur. – Jochen Glueck Dec 23 '20 at 23:11