MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $B$ be some set. The problem is to find a set $A\subset\mathcal{P}(B)$ of subsets of $B$ which is totally ordered by inclusion and such that there exists a bijection $A\leftrightarrow \mathcal{P}(B)$.

This is an easy exercise if $B$ is countable where one can explicitly construct such a set (one identifies $B$ with $\mathbb{Q}$ and takes $A$ to be the set of sets of the form $(-\infty, r)$ for all $r\in \mathbb{R}$)

My question now is the following: For which sets $B$ can the existence of such an $A$ be shown using any combination of (reasonable) additional hypotheses (e.g. AC, CH, GCH, ...)? Under which circumstances can one find $B$'s that don't admit such an $A$?

share|cite|improve this question
If I remember correctly, William Mitchell has shown in his thesis that if you add $\omega_{\omega_1}$ Cohen reals to the universe then in the resulting model there is no subset of $\mathcal{P}(\omega_1)$ of size $2^{\omega_1}$ which is linearly ordered under inclusion. – Ashutosh Feb 17 '13 at 2:09
Here's a reference: William Mitchell - Aronszajn trees and the independence of the transfer property, Annals of Math. Logic., Vol. 5, Issue 1, 1972, pp. 21-46 – Ashutosh Feb 17 '13 at 2:12
up vote 7 down vote accepted

Let's think about the countable case like this: think of the binary tree $2^{\lt\omega}$, which has size $\omega$, but has $2^\omega$ many branches. Each branch describes a cut in the natural lexical order on the nodes, and so we have a countable linear order with $2^\omega$ many cuts.

So consider a cardinal $\kappa$ and the tree $2^{\lt\kappa}$, which admits a similar lexical order. If this tree has size $\kappa$, then we get a linear order of size $\kappa$ with $2^\kappa$ many cuts. And such a family of cuts turns into a chain just as you point out in the question.

Thus, if $B$ has size $2^{\lt\kappa}$, then we can find $A$ of size $2^\kappa$. In particular, whenever $2^{\lt\kappa}=\kappa$, then $P(\kappa)$ has a chain of size $2^\kappa$, as you desire.

In particular, under the GCH, the phenomenon will occur for every infinite cardinal, since GCH implies $2^{\lt\kappa}=\kappa$ for all infinite cardinals $\kappa$.

Lastly, let me point out that this argument method can be turned into a characterization. Namely, the sets $B$ for which there is an $A$ as you desire are exactly the sets $B$ of size $\kappa$ for which there is a linear order on $\kappa$ with $2^\kappa$ many cuts. The one direction we've established, and for the converse, when there is such a chain $A$ in $P(B)$ of that size, then we may place a pre-order on $B$ according to the order in which points are added to sets in the chain (and extend this to a linear order). Each element of $A$ gives a cut in this order, and so we have a linear order on $\kappa$ with $2^\kappa$ many cuts.

So the phenomenon occurs for exactly those sets $B$ of size $\kappa$ for which there is a linear order on $\kappa$ with $2^\kappa$ many cuts.

share|cite|improve this answer
Note that the $2^{\lt\kappa}=\kappa$ property, while sufficient, is not necessary. For example, it could be that $2^\beta=2^\kappa$ for some $\beta\lt\kappa$ with $2^{\lt\beta}\leq\kappa$, and in this case, we would still have the tree $2^{\lt\beta}$ of size at most $\kappa$, but still having $2^\kappa$ many cuts. – Joel David Hamkins Feb 17 '13 at 1:53

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.