Infinite Sets

Countability, Cantor's diagonal argument, and Hilbert's Hotel

Infinite Sets

Some infinities are bigger than others. The integers and the fractions can be lined up and counted, but the real numbers cannot.

Countability Explorer

Choose the integers or the rationals and press play or Step to watch them get listed one by one. For the fractions, follow the zigzag through the grid and notice duplicates are skipped.

Countability Demonstrations

Watch bijections with the natural numbers being constructed

Enumeration: 0, 1, -1, 2, -2, 3, -3, ... Each integer gets a unique natural number index.
f(0)
0
Number line:
0
Step 1/20
Go deeper:Infinite Sets

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.

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.

Cantor's Diagonal Argument

Press play or Step to walk down the diagonal, changing the n-th digit of the n-th number. Watch the new number come out different from every row on the list.

Cantor's Diagonal Argument

Proving the reals are uncountable by constructing a missing number

Suppose we could list all real numbers in [0,1). We read down the diagonal, flip each digit, and build a number that differs from every row -- a contradiction.
#0.d1d2d3d4d5d6d7d8d9d10d11d12
r10.272727272727
r20.341034103410
r30.410341034103
r40.589658965896
r50.658965896589
r60.727272727272
r70.896589658965
r80.965896589658
r90.034103410341
r100.103410341034
d*0.????????????
Ready
Go deeper:Cantor’s Diagonal Argument

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.

Hilbert's Hotel

Choose a scenario — one new guest, infinitely many guests, or infinite buses — then press Animate to watch a full hotel make room.

Hilbert's Hotel

A hotel with infinitely many rooms, all full -- yet there is always room for more

All rooms are occupied. A new guest arrives...
#1G1
#2G2
#3G3
#4G4
#5G5
#6G6
#7G7
#8G8
#9G9
#10G10
#11G11
#12G12
#13G13
#14G14
#15G15
#16G16
#17G17
#18G18
#19G19
#20G20
... and infinitely more rooms beyond
Go deeper:Hilbert’s Hotel

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.

Key Takeaways

  • Countable vs uncountable -- two fundamentally different sizes of infinity
  • Aleph-naught -- the cardinality of the natural numbers, the smallest infinity
  • Diagonal argument -- Cantor's proof that the reals are uncountable, one of the most elegant arguments in mathematics
  • Infinite arithmetic is strange -- adding to or doubling a countably infinite set does not change its size

Spot a mistake or have an idea?

Search