Capstone: cardinality, countability and Cantor's diagonal argument

How many natural numbers are there? How many real numbers? 'Infinitely many' is the obvious answer to both, and for most of history it was assumed to be the only answer. In 1874 Georg Cantor proved that it is not: there are more real numbers than natural numbers, in a precise sense, and infinite sets come in different sizes. This capstone lesson develops that theory using everything in the course. The definitions are built from functions (lesson 10), the comparison of sizes behaves like an equivalence relation (lesson 11), the key arguments are proofs by contradiction (lesson 5) and constructions on sets (lesson 9), and induction (lesson 7) handles the finite case. The result is one of the most striking pieces of mathematics ever discovered, and every step of it is within reach.

Same size means a bijection

For finite sets, counting is a bijection with \(\{1, 2, \ldots, n\}\), and two finite sets have the same number of elements exactly when there is a bijection between them. Cantor's idea was to take this as the definition for all sets. Sets \(A\) and \(B\) have the same cardinality, written \(|A| = |B|\), if there is a bijection \(f : A \to B\). Write \(|A| \le |B|\) if there is an injection \(A \to B\), and \(|A| < |B|\) if \(|A| \le |B|\) but \(|A| \ne |B|\).

Same cardinality behaves like an equivalence relation. Every set has the identity bijection with itself; the inverse of a bijection is a bijection; and the composition of bijections is a bijection, all proved in lesson 10. (It is not literally a relation on a set, since there is no set of all sets, which is Russell's paradox from lesson 9 again; but the three properties hold.)

The definition immediately produces surprises. The map \(f(n) = 2n\) is a bijection from \(\mathbb{N} = \{1, 2, 3, \ldots\}\) to the even positive integers, so there are as many even numbers as natural numbers, even though the evens are a proper subset. Galileo noticed this in 1638 for the squares, \(n \mapsto n^2\), and concluded that comparisons of size do not apply to infinite collections. Cantor concluded instead that being in bijection with a proper subset is what it means to be infinite. For finite sets it is impossible, by the pigeonhole principle of lesson 10.

Hilbert's hotel

David Hilbert's illustration makes the point vivid. A hotel has rooms numbered \(1, 2, 3, \ldots\), all occupied. A new guest arrives. The manager asks every guest to move from room \(n\) to room \(n + 1\); everyone still has a room and room 1 is free. That is the bijection \(n \mapsto n + 1\) from \(\mathbb{N}\) to \(\mathbb{N} \setminus \{1\}\). A coach with infinitely many new guests arrives. Now the manager moves each guest from room \(n\) to room \(2n\), freeing all the odd rooms, and puts the \(k\)th new guest in room \(2k - 1\). The full hotel had room for infinitely many more.

Countable sets

A set is countably infinite if it has the same cardinality as \(\mathbb{N}\), and countable if it is finite or countably infinite. A bijection \(f : \mathbb{N} \to A\) is the same thing as a list \(f(1), f(2), f(3), \ldots\) in which every element of \(A\) appears exactly once. So a set is countable when its elements can be listed, with each one appearing at some finite position.

Two useful facts follow from the definition. Every subset of a countable set is countable: list the elements of the big set and strike out those not in the subset. And if there is a surjection from \(\mathbb{N}\) onto a set \(A\), then \(A\) is countable: the list \(g(1), g(2), \ldots\) may contain repeats, but deleting each element after its first appearance leaves a list with each element exactly once. A list with repeats is good enough to prove countability.

The rationals are countable

The rational numbers are dense: between any two there are infinitely many more. It seems they must outnumber the integers. They do not. Arrange the positive fractions \(p/q\) in a grid with \(p\) along the rows and \(q\) along the columns. Each row is infinite, so listing row by row would never reach the second row. Instead, list by diagonals: first the fractions with \(p + q = 2\), then \(p + q = 3\), then \(p + q = 4\), and so on. Each diagonal is finite, so every fraction \(p/q\) is reached at a finite stage, the diagonal \(p + q\).

The list begins \(\frac{1}{1}, \frac{1}{2}, \frac{2}{1}, \frac{1}{3}, \frac{3}{1}, \frac{1}{4}, \frac{2}{3}, \frac{3}{2}, \frac{4}{1}, \ldots\), skipping \(\frac{2}{2}\) and other fractions not in lowest terms so that each rational appears once. So \(\mathbb{Q}^{+}\) is countable. Interleaving \(0\), the positive rationals and their negatives as was done for \(\mathbb{Z}\) shows \(\mathbb{Q}\) is countable too. The same diagonal idea proves that \(\mathbb{N} \times \mathbb{N}\) is countable, and an explicit bijection is the Cantor pairing function \(\pi(a, b) = \frac{(a + b)(a + b + 1)}{2} + b\) from pairs of non-negative integers to non-negative integers.

Theorem. A countable union of countable sets is countable. Proof sketch: if \(A_1, A_2, \ldots\) are listed as \(A_i = \{a_{i1}, a_{i2}, \ldots\}\), then \((i, j) \mapsto a_{ij}\) is a surjection from \(\mathbb{N} \times \mathbb{N}\), which is countable, onto the union. The proof quietly uses the choice of a list for each \(A_i\), an infinite sequence of choices; this is one of the places where the axiom of choice enters mathematics. With this theorem, the set of all finite strings over a finite alphabet is countable (a union over lengths), and so is the set of algebraic numbers, the roots of polynomials with integer coefficients.

The real numbers are uncountable

Theorem (Cantor). The interval \((0, 1)\) is uncountable. Hence \(\mathbb{R}\) is uncountable.

Proof. Suppose for contradiction that \((0, 1)\) is countable. It is infinite, so there is a list \(x_1, x_2, x_3, \ldots\) containing every real number in \((0, 1)\). Write each in decimal, \(x_n = 0.d_{n1} d_{n2} d_{n3} \ldots\), choosing the expansion that does not end in an infinite string of 9s (so \(0.5\) is written \(0.5000\ldots\), not \(0.4999\ldots\)). Now define a new number \(y = 0.e_1 e_2 e_3 \ldots\) digit by digit: \(e_n = 5\) if \(d_{nn} \ne 5\), and \(e_n = 4\) if \(d_{nn} = 5\). The number \(y\) lies in \((0, 1)\), and its expansion uses only the digits 4 and 5, so it is the unique decimal expansion of \(y\) and does not end in 9s. For each \(n\), \(y\) differs from \(x_n\) in the \(n\)th digit, since \(e_n \ne d_{nn}\). Two numbers with different expansions of this kind are different, so \(y \ne x_n\) for every \(n\). Thus \(y\) is a number in \((0, 1)\) missing from the list, contradicting the assumption that the list contains every such number. \(\blacksquare\)

Three details make the proof watertight. First, the argument does not assume any particular list: it shows that every list misses something, which is what 'no surjection from \(\mathbb{N}\)' means. Second, the choice of digits 4 and 5 avoids the one subtlety of decimals, that \(0.4999\ldots = 0.5000\ldots\); a construction using 0 and 9 could produce a second name for a listed number. Third, adding \(y\) to the list does not help, because the argument applies to the new list and produces another missing number.

Since \((0, 1) \subseteq \mathbb{R}\) and subsets of countable sets are countable, \(\mathbb{R}\) is uncountable. In fact \(|(0, 1)| = |\mathbb{R}|\), via the bijection \(x \mapsto \tan\big(\pi(x - \tfrac{1}{2})\big)\). Combined with the countability of algebraic numbers, Cantor's theorem gives a famous corollary: transcendental numbers exist, and indeed almost all real numbers are transcendental. Joseph Liouville had constructed the first explicit transcendental number in 1844 by delicate analysis; Cantor's proof shows they are everywhere without exhibiting a single one.

Cantor's theorem: power sets are bigger

The diagonal idea works far beyond decimals. Theorem (Cantor, 1891). For every set \(A\), \(|A| < |\mathcal{P}(A)|\).

Proof. The map \(a \mapsto \{a\}\) is an injection from \(A\) to \(\mathcal{P}(A)\), so \(|A| \le |\mathcal{P}(A)|\). Now suppose for contradiction that some \(f : A \to \mathcal{P}(A)\) is surjective. Each \(f(a)\) is a subset of \(A\), which may or may not contain \(a\). Define \(D = \{a \in A : a \notin f(a)\}\). This is a subset of \(A\), so by surjectivity \(D = f(d)\) for some \(d \in A\). Is \(d \in D\)? If \(d \in D\), then by the definition of \(D\), \(d \notin f(d) = D\), a contradiction. If \(d \notin D\), then \(d \notin f(d)\), so \(d\) satisfies the condition for membership in \(D\), and \(d \in D\), a contradiction. Either way we have a contradiction, so no surjection exists, and in particular no bijection. \(\blacksquare\)

For a finite set with \(n\) elements this says \(n < 2^n\), a one-line induction in the style of lesson 7: \(1 < 2\), and if \(n < 2^n\) then \(n + 1 < 2^n + 2^n = 2^{n+1}\). For infinite sets it gives an endless ladder: \(|\mathbb{N}| < |\mathcal{P}(\mathbb{N})| < |\mathcal{P}(\mathcal{P}(\mathbb{N}))| < \cdots\), with no largest infinity. One can show \(|\mathcal{P}(\mathbb{N})| = |\mathbb{R}|\) by matching subsets of \(\mathbb{N}\) with binary expansions. The set \(D\) is the same trick as the diagonal number \(y\): it differs from each \(f(a)\) at the element \(a\). It is also the same trick as Russell's paradox, which asks whether the set of sets not containing themselves contains itself; and in 1931 Kurt Gödel used a diagonal construction to prove his incompleteness theorem, and in 1936 Alan Turing used one to prove that no program can decide whether every program halts.

Comparing sizes without bijections

Building an explicit bijection can be awkward. The Schröder–Bernstein theorem says it is never necessary: if there are injections \(A \to B\) and \(B \to A\), then there is a bijection \(A \to B\). So \(|A| \le |B|\) and \(|B| \le |A|\) imply \(|A| = |B|\), as the notation suggests. Cantor stated it; Ernst Schröder and Felix Bernstein gave proofs in the late 1890s. The proof builds the bijection by tracing chains of back-and-forth images and is a good extended exercise after this course.

The continuum hypothesis

Cantor proved \(|\mathbb{N}| < |\mathbb{R}|\) and asked whether there is a set of intermediate size: an uncountable subset of \(\mathbb{R}\) that is not in bijection with \(\mathbb{R}\). He conjectured there is none, the continuum hypothesis, and could not prove it. It was the first problem on Hilbert's famous list of 1900. The answer, when it came, was unexpected. Gödel showed in 1940 that the continuum hypothesis cannot be disproved from the standard axioms of set theory, and Paul Cohen showed in 1963 that it cannot be proved from them either. It is independent: the axioms do not settle it. Proof, the subject of this course, has limits, and proof is how those limits were discovered.

A finite diagonal argument

No program can carry out Cantor's argument on an infinite list, but the construction is completely concrete and can be run on any finite list. The code below generates eight random decimal strings, builds the diagonal number using the digits 4 and 5, and confirms that it differs from each listed number in the expected place. It then checks Cantor's theorem for a small set by brute force: for every function \(f\) from a 3-element set to its power set, the diagonal set \(D\) is missed.

import random
from itertools import combinations, product
random.seed(12)

rows = ["".join(random.choice("0123456789") for _ in range(8)) for _ in range(8)]
y = "".join("4" if rows[n][n] == "5" else "5" for n in range(8))
for n, r in enumerate(rows):
    mark = r[:n] + "[" + r[n] + "]" + r[n + 1:]
    print(f"x{n + 1} = 0.{mark:10s}  y differs at digit {n + 1}: {y[n] != r[n]}")
print("y  = 0." + y, "  y in list:", y in rows)

A = [0, 1, 2]
subsets = [frozenset(c) for k in range(4) for c in combinations(A, k)]
missed = 0
for images in product(subsets, repeat=len(A)):
    f = dict(zip(A, images))
    D = frozenset(a for a in A if a not in f[a])
    missed += D not in f.values()
print(f"{len(subsets)} subsets, {len(subsets) ** len(A)} functions f, D missed by all of them: {missed == len(subsets) ** len(A)}")

x1 = 0.[7]4852605  y differs at digit 1: True
x2 = 0.7[4]793809  y differs at digit 2: True
x3 = 0.27[5]25309  y differs at digit 3: True
x4 = 0.318[5]6100  y differs at digit 4: True
x5 = 0.8316[7]162  y differs at digit 5: True
x6 = 0.85982[0]82  y differs at digit 6: True
x7 = 0.816969[7]7  y differs at digit 7: True
x8 = 0.9680134[5]  y differs at digit 8: True
y  = 0.55445554   y in list: False
8 subsets, 512 functions f, D missed by all of them: True

Looking back

This lesson used every technique of the course. The definition of cardinality rests on bijections. Countability proofs are constructions, often with a surjection standing in for a bijection. The uncountability of \(\mathbb{R}\) and Cantor's theorem are proofs by contradiction built on a diagonal construction. Same cardinality is checked to behave as an equivalence relation, and the finite case \(n < 2^n\) is an induction. That is what learning to prove things buys you: a short list of reliable methods that combine to settle questions that intuition cannot. From here, MATH-241 applies the same methods to limits and continuity, MATH-322 to groups and rings, MATH-351 to the integers, and MATH-447 to the geometry of open sets and continuous maps.