01Overview
In 1874 Cantor proved that the reals are “more numerous” than the naturals: the two cannot be put into one-to-one correspondence. That broke the intuition that all infinities are alike, and set theory was born. His diagonal construction of a real missing from any list was later borrowed by Turing to prove the halting problem.
Naive set theory soon ran into trouble: in 1901 Russell formed “the set of all sets that do not contain themselves”, which contradicts itself either way. Zermelo and Fraenkel answered with axiomatic set theory (ZFC), constraining which sets may exist. Today almost every mathematical object can be encoded as a set, and the independence of the continuum hypothesis shows that some questions cannot be settled from the axioms at all.
02History
- 1874
Cantor proves the reals uncountable
The diagonal argument appears, and infinity splits into different cardinalities.
- 1901
Russell's paradox
Naive set theory develops a crack.
- 1908
Zermelo's axiomatisation
The axiom of separation restricts how sets may be constructed.
- 1922
ZFC takes shape
Fraenkel and Skolem complete the axiom of replacement.
- 1963
The continuum hypothesis is independent
Cohen's forcing shows CH cannot be decided from ZFC.
03Core concepts
Cardinality
The naturals, integers and rationals are equinumerous; the reals are not.
Diagonal argument
Build an object that differs from every item on the list — proving uncountability or undecidability.
Axiom of choice
Pick one element from each of arbitrarily many non-empty sets; equivalent to Zorn’s lemma.
04Hands-on
Do it once — it beats reading it ten times
Write a program that enumerates decimals in [0,1], constructs one that is not on the list by the diagonal method, and confirms it differs
05Self-check
Say it in your own words first, then open the answer. Whatever you cannot explain is what to review next.
Can you explain "Cardinality"?
The naturals, integers and rationals are equinumerous; the reals are not.
Can you explain "Diagonal argument"?
Build an object that differs from every item on the list — proving uncountability or undecidability.
Can you explain "Axiom of choice"?
Pick one element from each of arbitrarily many non-empty sets; equivalent to Zorn’s lemma.
What problem did it solve, and why was there nothing better at the time?
Go back to the history section: how was this done before, and what did it cost?
If you had to build it today, how would you break it down?
Use the hands-on task above: write a plan of at most three steps before you start.
06Key people
Georg Cantor
1845 – 1918
Founder of set theory and of transfinite numbers.
Bertrand Russell
1872 – 1970
Found Russell’s paradox; co-wrote Principia Mathematica.
Paul Cohen
1934 – 2007
Invented forcing and proved the continuum hypothesis independent.
07Further reading
- Principia Mathematica
- Set Theory