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?

  • 2
    $\begingroup$ No, you definitely cannot have an example with the standard axioms, as within ZFC one cannot prove such a set exists. $\endgroup$
    – kodiak
    Feb 22 at 13:53
  • $\begingroup$ @kodiak sure, I know that one cannot prove that a set exists within ZFC that violates CH. But if CH is independent of ZFC then there must exist a subset of R which cannot be proved to be either countable or to have the cardinality of the continuum, otherwise there could not exist a model in which CH does not hold (since every subset of R would be either $\aleph_0$ or $2^{\aleph_0}$.) $\endgroup$
    – Oliver
    Feb 22 at 14:00
  • $\begingroup$ In fact any infinite subset for which you cannot exhibit a bijection to $\mathbb N$ nor to $\mathbb R$ (or $\mathcal P (\mathbb N)$) would be a candidate. The hard part would be to exhibit such a subset... Maybe the non-normal numbers subset which seems to both be uncountable and have a Lebesgue measure of $0$ could be a good candidate. But I am not aware of any well known results... $\endgroup$ Feb 22 at 14:37
  • $\begingroup$ ... More exactly, I think that without CH it will be hard to prove the cardinality of that set. But I cannot make sure whether it is really impossible to prove it... $\endgroup$ Feb 22 at 14:40
  • 1
    $\begingroup$ Take some undecidable problem $\mathcal{P}$ and define $S =\mathbb{R}$ if $\mathcal{P}$ is true and $\emptyset$ if false. $\endgroup$
    – caduk
    Feb 22 at 15:27

2 Answers 2


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.


The first paragraph of this answer is unfortunately rather technical; this is somewhat unavoidable, as explained by the second paragraph of this answer.

Let $X$ be the set of reals which are either constructible (in the sense of Godel's $L$, not constructive logic) or code a well-ordering of $\mathbb{N}$ of ordertype $\ge\omega_1^L$. This $X$ is definitely uncountable: if $\omega_1^L=\omega_1$ then there are $\omega_1$-many constructible reals, and if $\omega_1^L<\omega_1$ then there are continuum-many reals witnessing that $\omega_1^L$ is countable. However, beyond this nothing more can be said: it's consistent with $\mathsf{ZFC}$ that $\omega_1^L=\omega_1<\mathfrak{c}$ (e.g. add $\omega_2$-many Cohen reals to $L$).

Of course this is a really messy definition, but there are pretty strong limitations to doing much better. For example, $\mathsf{ZFC}$ proves that every Borel - or even analytic (= continuous image of a Borel set) - has the perfect set property, and so cannot be a counterexample to $\mathsf{CH}$. The general topic this sort of result belongs to is descriptive set theory.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .