Countable and uncountable

A set is countable when its members can be listed in full against the counting numbers; the great discovery of set theory is that some infinite sets cannot be listed at all.

The test for countability is pairing, not finishing. The even numbers pair with all counting numbers by the rule n ↔ 2n; the integers pair by zig-zagging outward from zero through 1, −1, 2, −2 and every later pair; the rationals pair by snaking through an infinite grid of fractions and skipping repeats. Each pairing is a proof that the set, however sparse or dense it looks, has exactly the size ℵ₀.

Cantor asked in 1874 whether every infinite set is countable, and answered no: the real numbers cannot be listed. His 1891 diagonal argument makes the reason visible. Take any proposed list of reals between 0 and 1, written as decimals; construct a number whose first digit differs from the first digit of the first entry, whose second digit differs from the second digit of the second entry, and so on down the diagonal.

The constructed number is a perfectly good real between 0 and 1, yet it differs from every entry of the list in at least one decimal place. So the list was incomplete — and because the argument works for any list whatsoever, no complete list exists. The reals are uncountable, with cardinal 2^ℵ₀, strictly greater than ℵ₀.

'Bigger' here has an exact meaning: set A is bigger than set B when no one-to-one pairing from B onto A exists. Cantor's theorem generalizes the diagonal idea to show that the power set of any set — the set of all its subsets — is always bigger than the set itself. Starting from the counting numbers, this generates an endless hierarchy of infinities with no largest member.

Two subtleties complete the picture. First, many sets that look much larger than the line are not: the plane and all of three-dimensional space still have cardinal 2^ℵ₀, because interleaving decimal digits pairs points of the line with points of space. Second, whether any cardinal sits strictly between ℵ₀ and 2^ℵ₀ — the continuum hypothesis — was shown by Gödel and Cohen to be undecidable from the standard axioms.

• Countable: naturals, integers, rationals, algebraic numbers — all of size ℵ₀.
• Uncountable: reals, points of the plane, subsets of the naturals — all of size 2^ℵ₀.
• The diagonal argument turns 'cannot be listed' from a suspicion into a theorem.
• Cantor's theorem: every set is strictly smaller than the set of its subsets.

Further reading

• Two kinds of infinity
• Paradoxes of the infinite