My question is, does there exist a set of subsets of the naturals, $S$, such that $S$ is uncountable, where for any two subsets $A,B \in S$ we have either $A \subset B $ or $B \subset A $?

Initially my thoughts were that we could construct a chain $A_{1} \subset A_{2} \subset \cdots $ and find a bijection by picking out one element which is 'new' to each set by axiom of choice and so we have bijected to a subset of naturals, however I'm not convinced this fully works.

Furthermore, I was thinking there may be a nice elegant solution by looking for such a set in either $ \mathbb{Q}^2 $ or $ \mathbb{Z}^2 $ for example, but any attempt seems to fail due to the 'ordering' part of the question.


Yes, there is - although what you've outlined doesn't work, since there are only countably many naturals, so any strategy based on "keep picking naturals" will break down long before you get uncountably many sets.

Replace $\mathbb{N}$ by $\mathbb{Q}$ (they're both countably infinite, so this is fine) and think about Dedekind cuts. A Dedekind cut is a set of the form $$\{q\in\mathbb{Q}: q<r\}$$ for some real $r$. There are as many Dedekind cuts as reals (indeed, we sometimes define the reals as Dedekind cuts), and any two Dedekind cuts are comparable.

Note that this does not rely on the axiom of choice in any way. Also, note that - if we include in addition $\emptyset$ and $\mathbb{Q}$ - we get a maximal family of sets with this property: any set of rationals $\subseteq$-comparable with every Dedekind cut is either a Dedekind cut or $\emptyset$ or $\mathbb{Q}$.

You may also be interested in the topic of Hausdorff (and other kinds of) gaps.


There is a particularly cute solution that does not involve Dedekind cuts. For each real number $r$ in $(0,1)$, let $S_r = \{ 2^k+m : k,m\in\mathbb{N} ∧ m ≤ \lfloor r·2^k \rfloor \}$. Then you can prove that $S_q \subsetneq S_r$ for every $q,r∈(0,1)$ such that $q<r$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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