Countability, Cantor's diagonal argument, and Hilbert's Hotel
Georg Cantor's revolutionary discovery was that not all infinities are equal. The natural numbers, integers, and rationals are all "countably infinite" -- they can be listed one by one. But the real numbers cannot: they form a strictly larger infinity.
This insight shattered the ancient belief that infinity was a single, undifferentiated concept, and opened up an entire hierarchy of infinite sizes measured by cardinal numbers.
Construct bijections between the natural numbers and other infinite sets. See why the integers and rationals are countable despite seeming "bigger."
Watch bijections with the natural numbers being constructed
Key insight: A set is countably infinite if its elements can be listed in a sequence -- that is, put in bijection with the natural numbers. The integers and rationals are countable; the reals are not.
Watch the diagonal argument in action: given any list of real numbers, we construct a new real number that differs from every entry on the list.
Proving the reals are uncountable by constructing a missing number
| # | 0. | d1 | d2 | d3 | d4 | d5 | d6 | d7 | d8 | d9 | d10 | d11 | d12 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| r1 | 0. | 2 | 7 | 2 | 7 | 2 | 7 | 2 | 7 | 2 | 7 | 2 | 7 | |
| r2 | 0. | 3 | 4 | 1 | 0 | 3 | 4 | 1 | 0 | 3 | 4 | 1 | 0 | |
| r3 | 0. | 4 | 1 | 0 | 3 | 4 | 1 | 0 | 3 | 4 | 1 | 0 | 3 | |
| r4 | 0. | 5 | 8 | 9 | 6 | 5 | 8 | 9 | 6 | 5 | 8 | 9 | 6 | |
| r5 | 0. | 6 | 5 | 8 | 9 | 6 | 5 | 8 | 9 | 6 | 5 | 8 | 9 | |
| r6 | 0. | 7 | 2 | 7 | 2 | 7 | 2 | 7 | 2 | 7 | 2 | 7 | 2 | |
| r7 | 0. | 8 | 9 | 6 | 5 | 8 | 9 | 6 | 5 | 8 | 9 | 6 | 5 | |
| r8 | 0. | 9 | 6 | 5 | 8 | 9 | 6 | 5 | 8 | 9 | 6 | 5 | 8 | |
| r9 | 0. | 0 | 3 | 4 | 1 | 0 | 3 | 4 | 1 | 0 | 3 | 4 | 1 | |
| r10 | 0. | 1 | 0 | 3 | 4 | 1 | 0 | 3 | 4 | 1 | 0 | 3 | 4 | |
| d* | 0. | ? | ? | ? | ? | ? | ? | ? | ? | ? | ? | ? | ? |
Key insight: The diagonal argument shows that no list can contain all real numbers in [0, 1]. By changing the n-th digit of the n-th number, we produce a real number not on the list. Therefore the reals are uncountable.
A fully occupied hotel with infinitely many rooms can always accommodate new guests. Explore the paradoxes of countable infinity through this famous thought experiment.
A hotel with infinitely many rooms, all full -- yet there is always room for more
Key insight: Hilbert's Hotel illustrates that a countably infinite set can absorb one new element, finitely many, or even countably infinitely many more elements without changing its cardinality. Infinity plus infinity is still the same infinity.