Let $(X, \leq)$ be a totally ordered set. A downset of $X$ is a subset $A$ of $X$ with the property $$ \forall x \in X \forall a \in A : ( x \leq a \Rightarrow x \in A ) $$ Denote $\mathcal{D}(X)$ for the set of downsets of $X$. We trivially have $\lvert \mathcal{D}(X) \rvert \leq 2^{\lvert X \rvert}$ and equality is possible, e.g. if $X = \mathbb{Q}$. If $X$ is a finite set, then $\lvert \mathcal{D}(X) \rvert = \lvert X \rvert + 1$.

If $X$ is an infinite, complete totally ordered set, then $\lvert \mathcal{D}(X) \rvert = \lvert X \rvert$, because all downsets are of the form $$ \lbrace x \in X \mid x < a \rbrace \text{ or } \lbrace x \in X \mid x \leq a \rbrace $$ for some $a \in X$. I was wondering if for an infinite, non-complete totally ordered set, there are general results on the cardinality of $\lvert \mathcal{D}(X) \rvert$, or criteria to determine whether $\lvert \mathcal{D}(X) \rvert < 2^{\lvert X \rvert}$ or $\lvert X \rvert < \lvert \mathcal{D}(X) \rvert$.

  • 2
    $\begingroup$ Some relevant posts: mathoverflow.net/q/72101/7206 and mathoverflow.net/q/72130/7206 and mathoverflow.net/q/48231/7206 $\endgroup$ – Asaf Karagila Jan 11 '17 at 17:40
  • $\begingroup$ You star with totally ordered sets and then you mention complete posets (partially ordered sets) and describe their downsets, but those are actually the downsets of totally ordered sets, which makes it a bit misleading (I suppose you mean totally ordered sets in all your text; otherwise it's wrong because a poset in general will have other types of downsets). $\endgroup$ – amrsa Jan 11 '17 at 22:19
  • $\begingroup$ You're right, I was talking about totally ordered sets the whole time; will change this to make it more clear. $\endgroup$ – Bib-lost Jan 12 '17 at 7:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.