Countable vs Uncountable Sets: Cantor's Diagonal Argument in Plain Steps

How do you compare the sizes of two infinite sets? Counting fails, because neither count ever ends. Georg Cantor's answer was to compare by matching: two sets are the same size if their elements can be paired off one-to-one, with nothing left over on either side. That single idea leads to some genuinely surprising results, including the fact that some infinite sets are larger than others.

Same size means a bijection

Two sets have the same cardinality when there is a bijection between them, a pairing that is one-to-one and onto.

Applied Discrete Structures defines a countable set as one that is finite or has the same cardinality as the positive integers. MathWorld uses the same split: countable means finite or denumerable. A countably infinite set is one whose elements can be listed as a first, second, third, … with every element appearing at some finite position and none repeated.

A set that is infinite but not countable is uncountable.

Surprising countable sets

Infinite sets that look bigger than the positive integers need not be.

The even numbers. Pair n with 2n: 1 ↔ 2, 2 ↔ 4, 3 ↔ 6, … Every positive integer gets exactly one even partner and vice versa. A set can have the same size as a proper subset of itself; that is one way to define being infinite.

All the integers. List them as 0, 1, −1, 2, −2, 3, −3, … Every integer appears, at a finite position. As a formula, the nth term is n/2 when n is even and −(n − 1)/2 when n is odd, starting from n = 1 giving 0.

Pairs of positive integers. Arrange ℙ × ℙ, the Cartesian product of the positive integers with itself, as a grid, then walk it along diagonals: (1,1); (1,2), (2,1); (1,3), (2,2), (3,1); … Each diagonal is finite, so every pair is reached. Applied Discrete Structures uses exactly this example of a "seemingly larger" countable set.

The rational numbers. A positive fraction p/q is a pair (p, q), so the diagonal walk lists every positive rational too, skipping repeats such as 2/4. Applied Discrete Structures reproduces Cantor's listing, 0, 1, 1/2, 2, 3, 1/3, 1/4, 2/3, 3/2, 4, …, and then interleaves the negatives. So the rationals, which sit densely between any two reals, are no more numerous than the positive integers.

All finite strings over a finite alphabet. List them by length, then alphabetically within each length. Every string has some finite length, so it appears. In particular, the set of all computer programs, which are finite strings, is countable.

Cantor's diagonal argument: the reals are uncountable

Here is the proof that no list can contain every real number between 0 and 1. It is a proof by contradiction.

Step 1: assume a complete list exists. Suppose r₁, r₂, r₃, … lists every real number in (0, 1), each written as an infinite decimal:

Step 2: build a new number from the diagonal. Look at the bold digits, the nth digit of rₙ. Construct x = 0.d₁d₂d₃… by choosing each dₙ to differ from that diagonal digit. A simple rule: dₙ = 4 if the diagonal digit is 5, and dₙ = 5 otherwise. Here the diagonal digits are 5, 3, 8, 4, so x = 0.4555…

Step 3: x is not on the list. It differs from r₁ in the first decimal place, from r₂ in the second, and from every rₙ in the nth place. So x ≠ rₙ for every n.

Step 4: contradiction. The list was supposed to contain every real in (0, 1), but x is a real in (0, 1) that it misses. So no such list exists, and the reals are uncountable. ∎

The rule uses only the digits 4 and 5 for a reason. Some numbers have two decimal expansions, such as 0.1999… = 0.2000…, and a constructed x ending in repeated 0s or 9s could secretly equal a listed number. Avoiding 0 and 9 rules that out.

MathWorld calls this the Cantor diagonal method and stresses that it is completely general.