Worked solution: Gödel and Cohen: the continuum hypothesis is independent of ZFC (1963)

Step 1 of 9: The continuum hypothesis: no cardinality strictly between

\aleph_0

and

2^{\aleph_0}

Previous step Next step

In plain words

The natural numbers $\mathbb{N}$ form the smallest infinite size, called $\aleph_0$ ; Cantor's diagonal argument (1891) shows the real numbers $\mathbb{R}$ form a strictly bigger infinity, whose size is written $2^{\aleph_0}$ . It is natural to wonder whether some intermediate size sits strictly between them, the way $2$ sits between $1$ and $3$ .

Cantor conjectured in 1878 that the answer is no: every infinite subset of $\mathbb{R}$ is either the same size as $\mathbb{N}$ or the same size as $\mathbb{R}$ itself, with nothing in between. This claim is the continuum hypothesis ( $\mathrm{CH}$ ), equivalently written $2^{\aleph_0} = \aleph_1$ , where $\aleph_1$ denotes the very next infinite size after $\aleph_0$ .

2^{\aleph_0} = \aleph_1

Detailed analysis

Cantor proposed the continuum hypothesis ( $\mathrm{CH}$ ) in 1878: every infinite subset of $\mathbb{R}$ has cardinality either $\aleph_0$ (countable) or $2^{\aleph_0}$ (the cardinality of the continuum), with no cardinality strictly in between. Equivalently, since Cantor's theorem always gives $\aleph_1 \le 2^{\aleph_0}$ (where $\aleph_1$ is the least uncountable cardinal), $\mathrm{CH}$ says $2^{\aleph_0} = \aleph_1$ exactly.

Hilbert listed this as the very first of his 23 problems in 1900, expecting it would soon be settled one way or the other by ordinary mathematical proof, in the style of Cantor's own diagonal argument. Peter Koellner's Stanford Encyclopedia entry on the Continuum Hypothesis surveys this history and the modern understanding of what came next.

What came next, over the following six decades, turned out to upend the very expectation that $\mathrm{CH}$ could be proved or refuted by ordinary means at all: the next step explains precisely what it means for a mathematical statement to be neither provable nor refutable from the accepted axioms of set theory.

Terms in this step

Cardinal number: A cardinal number measures the size of a set; two sets have the same cardinal exactly when there is a one-to-one correspondence between them. $\aleph_0$ is the cardinal of $\mathbb{N}$ ; $\aleph_1$ is the smallest cardinal bigger than $\aleph_0$ .
The continuum $2^{\aleph_0}$: The cardinality of the set of all subsets of $\mathbb{N}$ , written $2^{\aleph_0}$ by analogy with counting subsets of a finite set of size $n$ as $2^n$ . This equals the cardinality of $\mathbb{R}$ , since real numbers can be coded as infinite binary sequences.

Knowledge used in this step

The ZFC axioms Ordinal and cardinal numbers