Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$P(\mathbb N)$ = power set of $\mathbb N$.

$A \subset P(\mathbb N)$ is a chain if $a,b \in A \implies$ either $a \subseteq b$ or $ b \subseteq a$

That is we have something like this:

$$\ldots a \subseteq b \subseteq c \subseteq\ldots$$ where $a,b,c \in A$ are distinct.

We can show easy enough that there is an uncountable chain - this is done by noting $\mathbb N\sim\mathbb Q$ then using Dedekind cuts in $\mathbb Q$ to define $\mathbb R$ we see that a family of (nearly arbitrary) cuts satisfy the condition.

For instance the family $L_r=\{q \in \mathbb Q : q < r \}$ for $r > 0$ gives us the sets we need and obviously we can pick others.

I tried doing this for $ \mathbb R$ and don't seem to be getting anywhere. To be more specific, does there exist a chain in $P(\mathbb R)$ with cardinality $2^ \mathbb R$ ? Given a set of cardinality $X$ (necessarily non-finite), is there a chain in $P(X)$ of the same cardinalty of $P(X)$?

share|improve this question
Adam, I see that you used $\LaTeX$ in parts of your question. It is possible, and even better, to fully $\TeX$-ify your post as it makes it easier (much much easier) to read. –  Asaf Karagila Dec 12 '11 at 22:41
Thanks Brian M. Scott for point out the error. –  William Dec 12 '11 at 22:47
In the meantime, this MO question might be useful. –  Asaf Karagila Dec 12 '11 at 23:01
I deleted my comments on formatting - just to clear this section up + that link probably has some mileage great find. –  Adam Dec 12 '11 at 23:05
My hunch is that this depends greatly on the behavior of the continuum function (the cardinality of power sets). –  Asaf Karagila Dec 12 '11 at 23:05

2 Answers 2

up vote 3 down vote accepted

Consider the tree $T=2^{\lt\omega_1}$, consisting of all countable ordinal length binary sequences. The number of such sequences is precisely the continuum, since there are $\omega_1$ many levels, each of size continuumn. The lexical order on this tree (or on any two ordinal-length binary sequences), compares them by the order of their least differing bit, placing the shorter one below when one is an initial segment of the other.

Notice that any path $p\in 2^{\omega_1}$ through the tree determines a cut in the lexical order, namely, the collection $X_p$ of $s\in T$ which preceed $p$ in the lexical order. Furthermore, if $p$ preceeds $q$ lexically, then $X_p\subset X_q$, and so we have a chain in $P(T)$ of size $2^{\omega_1}$.

Thus, without any additional assumption, this establishes chains in $P(\mathbb{R})$ of size at least $2^{\omega_1}$.

In particular, if the continuum hypothesis holds, then $|\mathbb{R}|=\omega_1$, and so this shows that there is a chain in $P(\mathbb{R})$ of size $2^{\mathbb{R}}$. So an affirmative answer to your question is a consequence of CH and thus consistent with the axioms of ZFC.

More generally, we obtain a positive answer under the much weaker assumption merely that $2^{\lt\frak{c}}=\frak{c}$, an assumption that follows from but is much weaker than CH. For example, this assumption is compatible with $2^\omega=\aleph_{15}$, if also $2^{\aleph_{14}}=\aleph_{15}$. In this case, the tree $T=2^{\lt\frak{c}}$ has size $\frak{c}$ and $2^{\frak{c}}$ many branches. And so the cuts determined by the lexical predecessors of paths through this tree gives rise to a chain of size $2^{\frak{c}}$ in $P(\frak{c})$, as desired.

share|improve this answer
Similarly, if $2^{\lt\kappa}=\kappa$, then there is a chain in $P(\kappa)$ of size $2^\kappa$. –  JDH Dec 13 '11 at 0:36

Under the Generalized Continuum Hypothesis, this true by a slight generalization of the Dedekind cut argument:

Assume GCH, and let $\alpha$ be an initial ordinal. (Since GCH implies AC, this is enough to establish the result for an arbitrary infinite set). I will prove that $\mathcal{P} (\alpha)$ contains a chain of cardinality $2^\alpha$.

Let $A=\{X\mid X\subseteq \alpha\}$ with the lexicographic ordering -- that is, $X < Y$ iff $\beta\in Y$ where $\beta$ is the least element on which the two sets differ. (Intuition for $\alpha=\omega$: A is the set of binary fractions between 0 and 1).

Let $B=\bigcup_{\beta<\alpha}\{X \mid X\subseteq \beta\}\subseteq A$. (Intuition: dyadic rationals are countable yet dense).

Because $\alpha \preccurlyeq B = \bigcup_{\beta<\alpha} 2^\beta \preccurlyeq \alpha\times\alpha$, we have $|B|=|\alpha|$. (GCH used for $2^\beta \preccurlyeq \alpha$).

Define an order-embedding $(A,\leq) \to (\mathcal{P}(B),\subseteq)$ by $X \mapsto \{Y\in B \mid Y<X\}$. (Intuition: Dedekind cuts). It is trivial that this mapping is monotonic, and fairly easy to see that it is injective. Thus, the image of $A$ is a chain in $\mathcal{P}(B)\cong\mathcal{P}(\alpha)$ of cardinality the same as $A$, namely $2^\alpha$.

(Adapted from an old Wikipedia refdesk answer of mine.)

share|improve this answer
But under GCH everything is so simple and boring... :( –  Asaf Karagila Dec 12 '11 at 23:34
Well, as JDH remarks, this at least shows that the existence of long chains cannot be disproved. –  Henning Makholm Dec 12 '11 at 23:52
Well... duh :-) vision from the future... $\small\text{But under AC everything is so simple and boring...}$ ;-) –  Asaf Karagila Dec 12 '11 at 23:55
Hmm, three years into the future, I kinda sorta agree and disagree with my last comment there. See you again in three years! :-) –  Asaf Karagila Mar 10 at 8:09

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.