continuum hypothesis

The smallest infinite cardinal number is $\aleph_0$ (pronounced 'aleph null', or 'aleph naught'), the next is (by definition) $\aleph_1$, then $\aleph_2$, and so on.

There are $\aleph_0$ integers. There are strictly more real numbers than integers (proof by 'diagonalisation'), in fact there are $2^{\aleph_0}$ reals (proof by construction of a one-one mapping between the reals and the powerset of $\aleph_0$; this is the cardinality of the continuum, or $C$. So $\aleph_0 < C$. We know that $C$ cannot be less than $\aleph_1$, because the only infinite cardinal less than $\aleph_1$ is $\aleph_0$. So, is $C$ equal to, or greather than, $\aleph_1$?

If $\aleph_1 < C$, there would be sets with cardinality $\aleph_1$ that would have strictly more elements than in the set of integers, but stricly fewer elements than in the set of reals. Cantor's continuum hypothesis is that $C = \aleph_1$, that there are no such intermediate sized sets.

Gödel showed in 1938 that the continuum hypothesis cannot be disproved using just the axioms of set theory. Paul Cohen showed in 1963 that the continuum hypothesis cannot be proved using just the axioms of set theory. It is independent of those axioms, and is undecidable.

Hausdorff's generalised continuum hypothesis is that $\forall n \,{\tiny\bullet}\, 2^{\aleph_n} = \aleph_{n+1}$. It is also undecidable.

Under the Generalized Continuum Hypothesis, there are Aleph-1 real numbers, Aleph-2 functions from the reals to the reals, Aleph-3 functions from the functions from the reals to the reals to the functions from the reals to the reals, Aleph-4 functions from the functions from the functions from the reals to the reals to the functions from the reals to the reals to the functions from the functions from the reals to the reals to the functions from the reals to the reals, and so on. (There are simpler examples, too, but they're not as much fun to say :-) .

-- Kevin Wald. rec.arts.filk, April 2001