Skip to content
Tutorials Center
My learning

Topics

Lesson 24 of 37 Β· Cardinality and Orders

Cantor's Diagonal Argument and Uncountability

Walk through Cantor's diagonal argument and Cantor's theorem on power sets, see why the real numbers cannot be listed, and meet the continuum hypothesis with runnable code.

The previous lesson showed that β„•, β„€ and β„š all have the same cardinality, β„΅β‚€. You might now guess that all infinite sets are the same size. They are not. In 1891 Cantor proved that some infinite sets are strictly larger than β„•, using an argument so short and so general that it reappears throughout logic and computer science: the diagonal argument.

Diagonalizing infinite binary sequences

Suppose someone claims to list all infinite binary sequences as sβ‚€, s₁, sβ‚‚, …. Build a new sequence d by flipping the diagonal: the n-th digit of d is the opposite of the n-th digit of sβ‚™. Then d differs from sβ‚€ in position 0, from s₁ in position 1, and from every sβ‚™ in position n. So d is not on the list, and the list was incomplete. Since the list was arbitrary, no list can ever be complete: the set of infinite binary sequences is uncountable.

Python Diagonalizing a finite corner of a list

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.

The real numbers are uncountable

Binary sequences stand for subsets of β„•, and also (with care) for real numbers in [0, 1]: write each real as a decimal expansion and diagonalize by changing the n-th digit to something other than 0, 9 and the existing digit (avoiding 0.4999… vs 0.5000… duplicates). Therefore |ℝ| > |β„•|. The cardinality of ℝ is called the continuum, written 𝔠, and equals 2^β„΅β‚€.

A consequence for computing: programs are finite strings, so there are only countably many of them, while there are uncountably many functions β„• β†’ {0, 1}. Almost all functions are not computable. This idea returns in the halting problem.

Python Diagonalizing a computable listing of rationals' digits

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.

Cantor's theorem: every set is smaller than its power set

The diagonal trick generalizes to any set A: there is no surjection from A onto its power set P(A). Take any function f: A β†’ P(A) and define D = {a ∈ A : a βˆ‰ f(a)}. If D = f(x) for some x, then x ∈ D iff x βˆ‰ f(x) = D, a contradiction. So D is missed, and |A| < |P(A)|.

For finite A this is obvious (n < 2ⁿ), but for infinite A it gives an endless tower of infinities: β„΅β‚€ < 2^β„΅β‚€ < 2^(2^β„΅β‚€) < ….

flowchart LR
    A["β„• (β„΅0)"] --> B["P(β„•) = ℝ (continuum)"] --> C["P(P(β„•))"] --> D["..."]

Each power set is strictly larger than the set before it.

Python Cantor's theorem on a finite set: no f hits D

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.

The continuum hypothesis

Is there any set with a cardinality strictly between β„΅β‚€ and 𝔠? Cantor believed not, and called this the continuum hypothesis (CH). Remarkably, CH can neither be proved nor refuted from the standard axioms of set theory: GΓΆdel (1940) showed it is consistent with them, and Cohen (1963) showed its negation is consistent too. It is the best-known example of a statement independent of ZFC.

Cardinal arithmetic in a nutshell

  • β„΅β‚€ + β„΅β‚€ = β„΅β‚€ Β· β„΅β‚€ = β„΅β‚€; countable infinite sets absorb finite and countable additions.
  • |P(β„•)| = |ℝ| = 2^β„΅β‚€: subsets of β„• correspond to infinite binary sequences.
  • |ℝ Γ— ℝ| = |ℝ|: the plane has as many points as the line.
  • |A| < |P(A)| for every set A, so there is no largest cardinal.

The diagonal argument works because the new object is defined from the list. If you try to prove that β„š is uncountable the same way, the diagonal number you build is generally irrational, so it is not in β„š and nothing breaks. Always check that the constructed object belongs to the set you started with.

Check your understanding

Quick check Β· 4 questions

of 4 answered You scored / 4 Β· perfect!

  1. 1. In the diagonal argument, the new sequence d is built by

    Flipping the diagonal guarantees d differs from each listed sequence in at least one place.
  2. 2. Which statement does Cantor's theorem give?

    No function from A onto its power set exists, so the power set is strictly larger.
  3. 3. Why does the uncountability of the reals imply some functions are not computable?

    Programs are finite strings and form a countable set; the functions N to {0,1} form an uncountable set, so most are not computed by any program.
  4. 4. What is known about the continuum hypothesis in ZFC?

    GΓΆdel and Cohen showed ZFC proves neither CH nor its negation (assuming ZFC is consistent).

Summary

  • Diagonalization builds an object that differs from every item on a supposed complete list.
  • The reals, the infinite binary sequences and the subsets of β„• are uncountable.
  • Cantor's theorem: |A| < |P(A)| for every set, so infinities come in infinitely many sizes.
  • The continuum hypothesis is independent of ZFC; most functions are not computable.

Next: Partial Orders and Lattices