15
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Gro-Tsen Dec 11 '20 at 10:17
17
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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... $\endgroup$ – Jochen Glueck Dec 3 '20 at 3:04
  • $\begingroup$ Finally, I have also found this result in a book: Proposition 1.5.9 in "Universal Algebra (1981)" by Paul M. Cohn. $\endgroup$ – Jochen Glueck Dec 21 '20 at 3:48
  • $\begingroup$ 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? $\endgroup$ – Jochen Glueck Dec 21 '20 at 3:48
  • 1
    $\begingroup$ @JochenGlueck Yes, that's fine, but please make sure the wording doesn't let people think the result is due to me. $\endgroup$ – Andreas Blass Dec 21 '20 at 12:38
  • $\begingroup$ Thank you for your response. I've made sure that no such misunderstanding can occur. $\endgroup$ – Jochen Glueck Dec 23 '20 at 23:11

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.