🪴 GoDeep
Search
← University Challenge
Portrait of Cantor's diagonal argument

Science · Mathematics

Cantor's diagonal argument

1891

Mathematics — set theory and infinity

Georg Cantor's proof of 1891 that the real numbers cannot be put into a one-to-one correspondence with the natural numbers, and so that some infinities are strictly bigger than others. Suppose you list every real number between 0 and 1; then build a new number whose first digit differs from the first digit of the first number, whose second differs from the second digit of the second, and so on down the diagonal. The new number is on no line of the list, so no list can be complete. The reals are uncountable; the rationals and the algebraic numbers are not.

How to spot them

  • ▸The proof that not all infinities are the same size
  • ▸Runs down the diagonal of a supposed complete list, changing every digit
  • ▸Proves the real numbers uncountable, while the rationals are countable
  • ▸Cantor's 'I see it, but I don't believe it' — in a letter to Dedekind
  • ▸The same trick reappears in Russell's paradox, Gödel's theorems and Turing's halting problem

Key facts

The 1891 proof that no list of real numbers can be complete (1891)

Published in the Jahresbericht of the German Mathematical Society

The Hebrew letter aleph with a subscript, used to name the sizes of infinite sets

Aleph-null is the cardinality of the natural numbers

The hypothesis that there is no set larger than the naturals and smaller than the reals (1878)

The continuum hypothesis, first of Hilbert's 23 problems of 1900

Hilbert's hotel with infinitely many occupied rooms that can still take another guest (1924)

David Hilbert's parable of the paradoxes of countable infinity

The theorem that a set's power set is always strictly larger than the set itself (1891)

Cantor's theorem, giving an unending tower of infinities

Turing's 1936 proof that no machine can decide whether an arbitrary program halts (1936)

The halting problem, which reuses exactly the same diagonal trick

A rearrangement of the rationals into a single infinite list, showing them countable

Cantor's pairing or zig-zag enumeration — the counterpoint to the uncountability of the reals

Key ideas

  • Two sets are the same size if their members can be paired off exactly. On that definition the even numbers are the same size as all the whole numbers — a shock that Cantor accepted and his critics could not.
  • The real numbers are 'uncountable': there are strictly more of them than there are counting numbers. Almost all of them are transcendental.
  • Nonstandard analysis produces 'hyperreal' numbers, a field containing infinitesimals and infinite quantities, developed by Abraham Robinson in the 1960s.

Quick-fire facts

  • •Georg Cantor (1845–1918) was born in Saint Petersburg and spent his career at the University of Halle
  • •He first proved the reals uncountable in 1874 by a different, nested-intervals argument; the diagonal version dates from 1891
  • •He introduced the Hebrew letter aleph for infinite cardinals; aleph-null is the cardinality of the natural numbers
  • •In 1877 he wrote to Dedekind, of a different result, 'I see it, but I don't believe it'
  • •The continuum hypothesis was the first of the 23 problems David Hilbert posed in Paris in 1900
  • •Gödel showed in 1940 that the continuum hypothesis cannot be disproved from the standard axioms; Paul Cohen showed in 1963 that it cannot be proved either, winning the Fields Medal in 1966
  • •Cantor's theorem shows the power set of any set is strictly larger, so there is no largest infinity
  • •Leopold Kronecker opposed the work bitterly; Hilbert defended it, saying no one would drive mathematicians from the paradise Cantor had created
  • •Cantor suffered repeated bouts of depression and died in a sanatorium in Halle in 1918
  • •The middle-thirds Cantor set is uncountable yet has zero length — another of his constructions

Drill it — 8 cards

1 / 8new card

Sources