Skip to content
Tutorials Center
My learning

Topics

Lesson 35 of 38 Ā· Axioms and Paradoxes

Alephs and the Continuum Hypothesis

Meet the aleph numbers, state the continuum hypothesis, and learn why Gƶdel and Cohen showed it cannot be proved or refuted from ZFC, with a cardinal calculator.

We have found two different infinite sizes: ℵ₀ for the natural numbers and š”  = 2^ℵ₀ for the real line, and we know ℵ₀ < š” . Is there anything between them? A set of real numbers that is bigger than the countable sets but smaller than the whole line? This question, posed by Cantor in the 1870s, is the continuum hypothesis, and its answer turned out to be one of the great surprises of twentieth-century mathematics.

The aleph numbers

With the axiom of choice, every set can be well-ordered, so every set is matched with a unique initial ordinal: the least ordinal that has that cardinality. The infinite cardinals are listed in increasing order as

Text
ℵ₀ < ℵ₁ < ℵ₂ < ... < ℵ_ω < ℵ_(ω+1) < ...
  • ℵ₀ = ω is the smallest infinite cardinal: the size of ā„•.
  • ℵ₁ is the next cardinal after ℵ₀: the size of the set of all countable ordinals, ω₁.
  • In general ℵ_(α+1) is the least cardinal larger than ℵ_α.

Every set has a cardinal on this list (that is the content of the well-ordering theorem), and cardinals are comparable.

The continuum hypothesis

By Cantor's theorem, 2^ℵ₀ > ℵ₀, so 2^ℵ₀ ≄ ℵ₁. The question is whether equality holds.

Continuum Hypothesis (CH). 2^ℵ₀ = ℵ₁. Equivalently: every infinite set of real numbers is either countable or has the same cardinality as ā„; there is no set of intermediate size.

Generalized Continuum Hypothesis (GCH). For every infinite cardinal Īŗ, 2^Īŗ is the next cardinal after Īŗ.

Hilbert put CH first on his famous list of 23 problems in 1900.

The answer: it is independent

Two theorems settled the matter, in a way nobody expected:

  • Kurt Gƶdel (1938–1940): if ZFC is consistent, then ZFC + CH is consistent. Gƶdel built an inner model of set theory called the constructible universe L, in which CH (and AC) holds. So CH cannot be disproved from ZFC.
  • Paul Cohen (1963): if ZFC is consistent, then ZFC + ¬CH is consistent. Cohen invented the method of forcing to build models of set theory where 2^ℵ₀ is larger, for instance ℵ₂. So CH cannot be proved from ZFC.

Together: CH is independent of ZFC. Neither it nor its negation follows from the standard axioms (assuming ZFC itself is consistent). Cohen received the Fields Medal in 1966 for this work.

flowchart TD
  Z["ZFC"] --> L["Gƶdel (1940): a model where CH holds"]
  Z --> F["Cohen (1963): a model where CH fails"]
  L --> I["CH is independent of ZFC"]
  F --> I

Two models of ZFC settle the question in opposite ways.

Independence is like the parallel postulate in geometry. It is not that nobody has found the proof: it is that a proof is impossible. Mathematicians now explore which new axioms (such as large cardinal axioms or forcing axioms) might settle the matter, and different programs suggest different answers. The question "what is the true value of 2^ℵ₀?" is still open in this sense.

What cannot vary

Even though the exact value of 2^ℵ₀ is not fixed by ZFC, some facts are theorems. For example, 2^ℵ₀ cannot be ℵ_ω: by Kƶnig's theorem, 2^ℵ₀ has uncountable cofinality, which ℵ_ω does not. And by Cantor's theorem, the powers keep growing: 2^ℵ₀ < 2^(2^ℵ₀) < ....

A cardinal calculator

Cardinal arithmetic with the three values we know is easy to program. We represent a cardinal as one of: a finite number, "aleph0" or "c" (the continuum), with larger values reported as "bigger". The rules below are consequences of the identities ℵ₀ + ℵ₀ = ℵ₀, ℵ₀ Ā· ℵ₀ = ℵ₀, 2^ℵ₀ = š” , and š”  Ā· š”  = š”  (since 2^ℵ₀ Ā· 2^ℵ₀ = 2^(ℵ₀+ℵ₀) = 2^ℵ₀).

Python Cardinal arithmetic on finite numbers, ℵ₀ and the continuum

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Whether c is ℵ₁ is exactly what this calculator cannot tell you, and neither can ZFC.

Beth numbers

A related list avoids the question. The beth numbers are defined by repeated power sets: ā„¶ā‚€ = ℵ₀, ℶ₁ = 2^ā„¶ā‚€ = š” , ā„¶ā‚‚ = 2^ℶ₁, and so on. GCH is the statement ℵ_α = ā„¶_α for all α. These are cardinals that are known to exist and be distinct, whatever CH says.

Python The first levels of the power-set tower

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check your understanding

Quick check Ā· 4 questions

of 4 answered You scored / 4 Ā· perfect!

  1. 1. What does the continuum hypothesis state?

    CH says there is no cardinal strictly between ℵ₀ and 2^ℵ₀, so 2^ℵ₀ is the next cardinal, ℵ₁.
  2. 2. What did Cohen prove in 1963?

    Cohen's forcing method gave models of ZFC where CH fails. Together with Gƶdel's result, CH is independent.
  3. 3. What did Gƶdel show about CH?

    In L, the constructible universe, CH holds. So adding CH to ZFC does not create a contradiction.
  4. 4. Which statement about cardinals is a theorem of ZFC?

    Cantor's theorem proves 2^ℵ₀ > ℵ₀. The exact value cannot be decided in ZFC.

Summary

  • The aleph numbers list the infinite cardinals in order: ℵ₀ < ℵ₁ < ℵ₂ < ... (with choice).
  • The continuum hypothesis says 2^ℵ₀ = ℵ₁; GCH says 2^Īŗ = κ⁺ for every infinite Īŗ.
  • Gƶdel (constructible universe, 1938–1940) showed CH is consistent with ZFC; Cohen (forcing, 1963) showed its negation is consistent too.
  • So CH is independent of ZFC; new axioms are the only way to settle it.
  • Simple rules such as ℵ₀ Ā· ℵ₀ = ℵ₀, 2^ℵ₀ = š”  and š”  Ā· š”  = š”  still hold.

Next: Practice: Cardinality and Countability