2
$\begingroup$

Let ${\cal P}(\omega)$ denote the power-set of $\omega$. We order it by set inclusion $\subseteq$ and say that ${\cal C}\subseteq {\cal P}(\omega)$ is a chain if for all $A, B\in {\cal C}$ we have $A\subseteq B$ or $B \subseteq A$.

Interestingly, chains in ${\cal P}(\omega)$ can have length $2^{\aleph_0}$. Zorn's Lemma implies that every chain is contained in a maximal chain with respect to set inclusion.

Question. What is the cardinality of the collection of maximal chains in ${\cal P}(\omega)$ having uncountable cardinality?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
7
$\begingroup$

Any maximal chain in $\mathcal{P}(\omega)$ is determined by (that is, is the unique maximal chain containing) a countable subchain; this is basically just a restatement of the fact that $\omega_1$ doesn't embed into $\mathcal{P}(\omega)$. This gives an upper bound of $2^{\aleph_0}$ for the number of distinct maximal chains.

On the other hand, it's easy to show that there are at least $2^{\aleph_0}$ distinct size-continuum maximal chains in $\mathcal{P}(\omega)$ - each bijection $\mathbb{N}\rightarrow\mathbb{Q}$ gives rise to such a chain via Dedekind cuts, and different bijections give rise to incompatible chains in this way - so this bound is sharp.

Improve this answer
$\endgroup$
7
$\begingroup$

Any linear order $\le$ on $\omega$ will determine a maximal chain, namely, the chain $\mathcal C$ of all initial segments of $\le$.

(Is $\mathcal C$ maximal? If $A\notin \mathcal C$, then $A$ is not an initial segment. So let $x < y$, $y \in A$, $x\notin A$.
Let $B\in \mathcal C$ be the initial segment of all elements $< y$. As $x \in B \setminus A$, $y\in A \setminus B$, $A $ and $B$ are not comparable.)

Any maximal chain $\mathcal C$ determines a linear order, namely: $x\le y$ iff all elements of $\mathcal C$ containing $y$ also contain $x$.

(Easy to see that this is reflexive and transitive. If it is not antisymetric, let $\mathcal C_+$ be the set of all elements of $\mathcal C$ containing $x$ (and $y$), and $\mathcal C_-$ the rest. All element of $C_+$ are above all elements of $C_-$. Add a new set to the chain by taking the union of all sets in $C_-$ and adding $x$.
Linearity is easy.)

Hence the set of maximal chains is "the same" as the set of linear orders, which is easily seen to have cardinality continuum.

But you wanted uncountable chains. Ok, so use a fixed linear order of the even numbers that gives an uncountable chain, and combine it in continuum many ways with linear orders of the odd numbers, which you put above the even numbers.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Btw, this correspondence between maximal chains and linear orders works on any set, not just on countable set. $\endgroup$ Commented Aug 10, 2022 at 13:07

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.