1
$\begingroup$

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.

$\endgroup$
5
  • 2
    $\begingroup$ The set $\mathbb Q$ of all rational numbers can be split in $2^{\aleph_0}$ ways. (If you require that both parts be nonempty and the lower part has no greatest element, you can identify those splittings with Dedekind cuts.) $\endgroup$
    – bof
    Commented Dec 6, 2018 at 23:56
  • $\begingroup$ For $\mathbb R$ the set $S$ consists of $\varnothing$, $\mathbb R$ and all intervals $(-\infty, a)$ and $(-\infty, a]$ for $a\in\mathbb R$. So $|S|=2+2|\mathbb R|=|\mathbb R|$. $\endgroup$
    – Christoph
    Commented Dec 7, 2018 at 9:11
  • $\begingroup$ @bof The set $\mathbb{N}$ can only be split $\aleph_0$ ways, but $|\mathbb{N}| = |\mathbb{Q}|$ correct? Despite both being totally ordered sets of the same size, we get different answers. I really don't understand what is going on. $\endgroup$
    – PPenguin
    Commented Dec 7, 2018 at 14:35
  • 1
    $\begingroup$ What's going on is that the number of ways an ordered set can be split deponds nott just on the cardinality but onthe ordering. Why would you expect the ordering to be irrelevant? $\endgroup$
    – bof
    Commented Dec 7, 2018 at 14:45
  • $\begingroup$ @bof I naively expected the details of the ordering to be irrelevant because the setup appears to only use the existence of the linear ordering, and so it is unclear to me how the fine grained details of the ordering so drastically affect the results. A linear ordering having an exponential number of downward closed sets!? This is fascinating. This seems to come out of nowhere to me, and I'd like to understand it better. $\endgroup$
    – PPenguin
    Commented Dec 10, 2018 at 18:15

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Is your definition of Noetherian order standard? The one I know also imposes that there be no infnite antichain. Also, I find this answer very interesting but I think it would benefit from the inclusion of a few examples. Also, I think Emmy Noether wrote her last name Noether, i.e. this is not an english translation of her name. $\endgroup$
    – nombre
    Commented Dec 7, 2018 at 10:34
  • 1
    $\begingroup$ My mindset is of extrapolating the order theoretical properties of Noetherianity/Artinianity as they occur in the case of (lattices of subobjects of) algebraic structure. This leads to the definitions I suggested. I lack a wider reference frame by which to compare how standard my definition is but I certainly know of some professors of mine in a university I belonged to using the same terms with the same meaning as I do. I would like to ask about the reference where you encountered the additional condition on antichains. You are right about the orthography of the name! $\endgroup$
    – ΑΘΩ
    Commented Dec 7, 2018 at 12:58
  • $\begingroup$ Mine comes from a thesis(Corps de transséries of Michael Schmeling) which uses results due to Higman, Erdős and Rado. In Higman's context, the condition of no infinte anti-chain is important but I understand that it may not be the case in general. $\endgroup$
    – nombre
    Commented Dec 7, 2018 at 15:29
  • $\begingroup$ Thank you for the reference. By the way, as a remark, postulating the ''strong Noetherianity'' property (including the cardinal restriction on free subsets) is equivalent to claiming ''standard Noetherianity'' of the inclusion-ordered closure system of initial subsets (as they end up all being finitely generated). $\endgroup$
    – ΑΘΩ
    Commented Dec 7, 2018 at 15:42
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ The empty set does satisfy the defining property of elements of $S$. (being downward-closed) $\endgroup$
    – Christoph
    Commented Dec 7, 2018 at 9:08
  • $\begingroup$ bof's comment above explains why the technicalities with infinite sets must be important and interesting, as the expectations that "It should be N for all sets" apparently breaks down spectacularly in some cases. $\endgroup$
    – PPenguin
    Commented Dec 7, 2018 at 14:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .