The continuum hypothesis, and what this page does not prove

By Cantor's theorem: $A \prec \mathcal{P}(A)$ there is a strict gap $\mathbb{N} \prec \mathcal{P}(\mathbb{N})$ (Equinumerous sets, $A \approx B$ and $A \preceq B$). In particular $\mathcal{P}(\mathbb{N})$ is uncountable (Finite, countably infinite, countable, uncountable), since a surjection $\mathbb{N} \to \mathcal{P}(\mathbb{N})$ would exist if it were at most countable (A nonempty set is at most countable iff it is a surjective image of $\mathbb{N}$) and the theorem forbids one; and so, by a completely different argument, is $\mathbb{R}$ ($\mathbb{R}$ is uncountable (Cantor's nested intervals, 1874)). The obvious next question is whether anything sits strictly in between.

The continuum hypothesis (CH) asserts that nothing does:

there is no set $A$ with $\mathbb{N} \prec A \prec \mathcal{P}(\mathbb{N})$.

Over ZFC this is equivalent to: every uncountable subset of $\mathcal{P}(\mathbb{N})$ is equinumerous with $\mathcal{P}(\mathbb{N})$ itself. The qualification matters, and it is one of the few places on this page where a statement is not choice free. Passing from the displayed form to the subset form requires knowing that an uncountable $A \subseteq \mathcal{P}(\mathbb{N})$ satisfies $\mathbb{N} \prec A$, that is, that $A$ has a countably infinite subset, and that is not a theorem of ZF, granted the consistency of ZF: this page records exactly that in FALSE: every infinite set has a countably infinite subset, in ZF, whose conclusion is conditional on the consistency of ZF and rests on an external independence result quoted there rather than proved. Over ZF that passage is therefore unavailable, so nothing here asserts the two forms to be equivalent, and only the displayed form is used below. Whether they genuinely come apart in some model of ZF is a further independence question, which this page neither settles nor uses.

CH is independent of ZFC (The continuum hypothesis and its generalisation are independent of ZFC ‡). Gödel (1938) showed that ZFC cannot refute it, by constructing the inner model $L$ of constructible sets, in which CH holds (Gödel 1938: ZF does not refute the Axiom of Choice ‡). Cohen (1963) showed that ZFC cannot prove it, by inventing forcing and building a model of ZFC in which CH fails (Cohen 1963: ZF does not prove the Axiom of Choice ‡ is the same method). Together, if ZFC is consistent then so are ZFC + CH and ZFC + not CH, so CH is settled by neither. Both results are external to this library: neither the constructible universe nor forcing is developed here, and both are quoted with references rather than proved. As with the false statements on this page, the honest form of the conclusion is conditional on the consistency of ZFC, which cannot be proved inside ZFC.

What this page has not proved. CH is usually stated about $\mathbb{R}$: that every uncountable set of reals is equinumerous with $\mathbb{R}$. That form is equivalent to the one above only once one knows $\mathbb{R} \approx \mathcal{P}(\mathbb{N})$, which this library now proves, in ZF, on a later page. At this point in the reading order, though, the two uncountability results on this page are still genuinely separate facts: $\mathcal{P}(\mathbb{N})$ is uncountable by the diagonal argument, and $\mathbb{R}$ is uncountable by nested intervals, and the bridge between them is not available here — it needs binary expansions, which are developed much later, on the same later page. Nothing on this page depends on that bridge.

None of this affects the theorems proved here. Countability of $\mathbb{Q}$, uncountability of $\mathbb{R}$ and of the irrationals, and Cantor's theorem are all decided, and all are theorems of ZF, choice included nowhere. Independence enters only for statements that compare sizes strictly between $\mathbb{N}$ and $\mathcal{P}(\mathbb{N})$, and for the choice principles recorded in The Axiom of Countable Choice ($\mathrm{AC}_\omega$) and its companions.

The generalised continuum hypothesis (GCH), that $A \prec B \prec \mathcal{P}(A)$ never holds for infinite $A$, is also independent of ZFC (The continuum hypothesis and its generalisation are independent of ZFC ‡), in the same conditional sense as CH above: if ZFC is consistent, then so are ZFC + GCH and ZFC + not GCH, and that consistency assumption cannot be dropped. GCH implies CH, being its instance at $A = \mathbb{N}$, an instance the hypothesis "for infinite $A$" genuinely licenses: $\mathbb{N} \not\approx n$ for every natural number $n$ (claim 4 of The pigeonhole principle on $\mathbb{N}$), so $\mathbb{N}$ is not finite in the sense of Finite, countably infinite, countable, uncountable. GCH is stronger in a striking further sense: over ZF it even implies the Axiom of Choice, a result of Sierpiński (Sierpiński 1947: the generalised continuum hypothesis implies the Axiom of Choice ‡). That implication, too, is quoted and not proved here. That CH does not conversely imply GCH is again a relative-consistency statement rather than a theorem, conditional on the consistency of ZFC, and it is likewise not proved here.