Number of ways to split an ordered set

Question

Start with a totally ordered set $A$ of size (cardinality) $N$.
What is the size of the set $S$ of subsets of $A$ such that if $y$ is in the subset, any element $x$ in $S$ such that $x < y$ is also in the subset? Does the answer depend on the details of the ordering (if so, why)?

$$ S = \{B|B\subseteq A, \forall x \in A, y \in B \text{ if } x<y \text{ then } x \in B\} $$

More colloquially:

• How many ways can you split an ordered set into two pieces?
• Can the answer change if I define a new ordering on the initial set $A$?

For finite sets I expect the answer to be: $(N+1)$, and No, the ordering doesn't matter. Using the reals as an example of an infinite set, at least using the usual ordering, I think the answer is the same cardinality as the reals, and I have no idea if that depends on the ordering somehow.

I've been told never to extend intuition to infinite sets, so along with the answers I'd really appreciate, as best as possible, explanations of "why"/"where" intuition from finite sets breaks down if the answer is not simple.

Answer 1

It should be exactly N for all sets, since the empty set isn't a part of your partition (it isn't less than or greater than anything in $A$).

As a simple example, consider $A=\{1,2,3,4\}$.

$S=\left\{\{1\},\{1,2\},\{1,2,3\},\{1,2,3,4\}\right\}\implies|S|=|A|=4$

Also, this really only makes practical sense for countably finite sets. If you try to partition the reals this way, then there are uncountably infinitely many other points you can split the reals at, infinitely close to any point at which you're trying to split the reals. So the number of ways you can split the interval $[0,1]$ is uncountably infinite. Technically this is still the same as the cardinality of the set of all real numbers in the interval - but I don't see this fact being particularly helpful since any continuous subset of the reals has the same cardinality as the set of all real numbers.

Answer 2

Let's adopt a certain formalism to fix notions. Consider first an arbitrary ordered set $(A, R)$ (where $R \subseteq A \times A$ is an order on A which need not be total). We shall call $S \subseteq A$ an initial subset (some authors call them down-sets) if

$$(\forall x, y)(x \in S \land y \leqslant_{R} x \implies y \in S)$$

Let us further denote $$\mathscr{S}_{R}^{\downarrow}(A)=\{S |\ S\ \mathrm{ initial \ with \ respect \ to}\ R\}$$ easily seen to be closed under both arbitrary unions and (non-empty) intersections, fact which renders it into an algebraic closure system. Hence, for given $X \subseteq A$ one can speak of the initial subset generated by $X$, defined as the intersection of all the initial subsets including $X$ and characterised as the smallest such initial subset (the minimum with respect to inclusion among all those including $X$); we shall denote this generated initial subset by $[X]$.

We also introduce the notion of antichain, also known as free subset: $L \subseteq A$ is free (with respect to the fixed order $R$) if

$$(\forall x, y)(x, y \in L \land x \neq y \implies x \nleqslant_{R} y\land y \nleqslant_{R} x)$$

in other words if no two distinct elements of $L$ are comparable. Let us write $\mathscr{L}_{R}(A)$ for the set of all free subsets of $A$.

Now we can formulate a first result:

Proposition 1. The map $\Phi: \mathscr{L}_{R}(A) \rightarrow \mathscr{S}_{R}^{\downarrow}(A), \Phi(L)=[L]$ is injective and increasing (the orders considered on both domain of definition and codomain being given by inclusion).

Next, we recall the notion of maximal element: $x$ is said to be maximal in $X \subseteq A$ if $$x \in X \land (\forall y)(y \in X \land y\geqslant_{R} x \implies y=x)$$ We denote by $\mathrm{Max}_{R}(X)$ the set of all elements of $X$ maximal with respect to $R$ and make the following remark:

for any $X \subseteq A$ it holds that $\mathrm{Max}_{R}(X) \in \mathscr{L}_{R}(A)$.

We say that $(A, R)$ is a Noetherian ordered set if:

$$(\forall X)(\emptyset \neq X \subseteq A \implies \mathrm{Max}_{R}(X)\neq \emptyset)$$

in other words if any nonempty subset has at least a maximal element. Under the hypothesis of a Noetherian order, we have the following characterisation of initial subsets:

$(\forall S)(S \in \mathscr{S}_{R}^{\downarrow}(A) \implies S=[\mathrm{Max}_{R}(S)])$

stating that any initial subset is generated by its set of maximal elements. Combining this result with the previous remark we infer:

Proposition 2. In case $A$ is a Noetherian ordered set the map $\Phi$ defined in Proposition 1 becomes an increasing bijection

(note it will not in general be an order embedding, that would only be the case if the order $R$ were discrete, equal to the diagonal $\Delta_{A}$).

Thus, on a general Noetherian ordered set there are as many initial subsets as there are free subsets, with a natural correspondence between the two classes. If we additionally assume that $R$ is a total order, turning $(A, R)$ into the dual of a well-ordered set (well-ordered sets are nothing else than totally ordered Artinian sets, where Artinianity is the order-theoretic dual of Noetherianity, if one may use such wording), then the free subsets of $A$ trivially are either empty or singletons and we can claim that:

$$|\mathscr{S}_{R}^{\downarrow}(A)|=|\mathscr{L}_{R}(A)|=|A|+1$$

Hope you will find this expound instructive.