Grades 9–12FoundationsLesson available

Countability and Cantor's diagonal argument

Comparing infinite sets by bijections: ℕ, ℤ and ℚ are countable, every set is strictly smaller than its power set, and Cantor's diagonal argument shows that the real numbers are uncountable.

math.found.countability

Open lesson Show everything needed to reach this topic

Builds on

Functions Proof: direct, contrapositive, contradiction and induction Real numbers and irrationality

Required prerequisites, all the way down: 14

You will learn to

Show that ℤ and ℚ are countable by constructing explicit enumerations or bijections.
Define the power set P(A) and prove Cantor's theorem that no function A → P(A) is surjective.
Reproduce Cantor's diagonal argument that [0, 1) is uncountable, handling numbers with two decimal expansions.

Definition

Sets A and B have the same cardinality if there is a bijection A → B.
A set is countable if it is finite or has the same cardinality as ℕ; otherwise it is uncountable.
The power set P(A) is the set of all subsets of A.

Theorem

ℤ, ℚ and ℕ × ℕ are countable.
A countable union of countable sets is countable (the general statement uses the axiom of countable choice).
Cantor's theorem: for every set A there is no surjection from A onto P(A).
ℝ is uncountable; in fact ℝ and P(ℕ) have the same cardinality.

Common misconceptions

Thinking a proper subset of an infinite set must be smaller: ℕ and the even numbers have the same cardinality.
Objecting that the diagonal number 'can just be added to the list'; the argument shows that every list misses some number.
Forgetting that 0.4999… = 0.5, which a careful diagonal argument must avoid (for example by never changing a digit to 0 or 9).

Leads to

Ordinals and cardinals Completeness, compactness and Löwenheim–Skolem Computability Measure theory and integration

Optional discoveries

Forcing and independence Is there a set strictly larger than ℕ but smaller than ℝ? This is the continuum hypothesis; Gödel (1940) and Cohen (1963) showed that, if ZFC is consistent, it can be neither proved nor refuted in ZFC.Wonder Trail →
Gödel's incompleteness theorems A diagonal idea reappears in Gödel's proof through a self-referential sentence; the resemblance is genuine in spirit, but Gödel's diagonal lemma is a different construction.
← Counting
← Sets
← Set-builder notation, quantifiers and infinite sets
← Rational numbers