Set Theory – Example of Uncountable Subset of R with Different Cardinality

logicset-theory

I am new to mathematical logic so forgive me if this is a bad question.

I understand that the Continuum Hypothesis (CH) is independent of ZFC and therefore there exist models of ZFC in which the CH is false. In such models, by the very definition of CH being false, there must exist a set whose cardinality is strictly between that of the natural numbers ($\aleph_0$) and the real numbers ($2^{\aleph_0}$).

Does it follow from this that there must exist an uncountable subset of $\mathbb R$ which it is impossible to prove has the same cardinality as $\mathbb R$ (using the axioms of ZFC)?

If so, has an example of such a subset been documented? If not, is it known to be impossible to define one?

Best Answer

On one hand, sure, there are such sets. For example, you can construct one by following the proof of Hartogs's theorem. Hartogs's theorem gives that the set of all order types of well-orderings of subsets of $\mathbb{N}$ has cardinality $\aleph_1$ exactly (and is therefore uncountable). However, there are only continuum many relations on subsets of $\mathbb{N}$, so we can code a representative of each of these $\aleph_1$-many order types as a real number. Here, a representative just means some relation with that order type. This gets you a subset $\mathcal{W}$ of $\mathbb{R}$ with cardinality exactly $\aleph_1$. The coding can be done fairly explicitly (although I will leave that as an exercise in this answer).

Since the Continuum Hypothesis is independent of ZFC, it's clear that ZFC cannot prove that $\mathcal{W}$ (a set with cardinality $\aleph_1$) has the same cardinality as $\mathbb{R}$ (which has cardinality $2^{\aleph_0}$).

On the other hand, your explicit question was whether it follows from [the fact that the Continuum Hypothesis (CH) is independent of ZFC and therefore there exist models of ZFC in which the CH is false] that there must exist an uncountable subset of $\mathbb{R}$ which it is impossible to prove has the same cardinality as $\mathbb{R}$. And the answer to this question is a bit more delicate. In the colloquial sense, this certainly does not follow merely from the fact that CH is independent of ZFC.

But practically, much easier, slightly dodgy answers could have worked: consider e.g. the set defined using Separation as $\mathbb{N} \cup \{x \in \mathbb{R} \:|\: x = x \text{ and CH holds}\}$, which has the same cardinality as $\mathbb{R}$ precisely if CH holds, and smaller cardinality otherwise - but then not cardinality $\aleph_1$ (instead, you can prove it countable then). If you want to understand in precisely what way such answers are dodgy, you have to grapple with some borderline philosophical questions, such as what it means to give an example of a set. But that's a story for another time.

Related Question