Uncountable Sets and Cantor's Diagonal Argument

Cantor's diagonal argument is far more than a historical curiosity confined to set theory: its logical shape — assume a complete enumeration exists, construct an object diagonally escaping every entry, contradict completeness — recurs throughout mathematics and computer science. In mathematical logic, Gödel's incompleteness theorems use a diagonal construction (the diagonal lemma) to build a self-referential sentence asserting its own unprovability. In computability theory, the undecidability of the Halting Problem is proved by an essentially identical diagonal argument over Turing machines: assuming a machine could decide halting for all programs leads to a self-contradictory machine run on its own code. In complexity theory, diagonalization separates complexity classes (e.g., the time hierarchy theorem). In real analysis and measure theory, the uncountability of $\mathbb{R}$ underlies the existence of transcendental numbers (Cantor's original 1874 argument showed algebraic numbers are countable, so almost every real number is transcendental, without exhibiting a single one). In probability and statistics, cardinality distinctions justify why one cannot assign a positive probability to every point of a continuous sample space uniformly. In cryptography and information theory, diagonal-style counting arguments bound how many distinct short descriptions or keys can exist, informing pigeonhole-based security arguments.

Ask the tutor: How does the Schröder–Bernstein Theorem let us prove $|\mathbb{R}| = |\mathcal{P}(\mathbb{N})|$ using two separate injections instead of one direct bijection?

Imagine trying to list all real numbers between $0$ and $1$ in an infinite table, one number per row, written as an infinite decimal expansion. Cantor's insight is almost embarrassingly simple once seen: look down the diagonal of the table, read off the $n$-th digit of the $n$-th row, and change every single one of those digits. The new decimal number you build cannot equal any row of the table — it disagrees with row $n$ specifically at decimal place $n$. Since this holds for every row, the new number was left off the list. But the list was supposed to contain every real number in $(0,1)$. Contradiction: no such complete list can exist. The same idea, stripped of decimal digits and rebuilt with set membership, proves something even more general: no set surjects onto its own power set. Given any proposed correspondence $f$ from $A$ to subsets of $A$, define a new subset $D$ by the rule "$x \in D$ exactly when $x \notin f(x)$." This $D$ is a legitimate subset of $A$, yet it cannot equal $f(a)$ for any $a \in A$ — because asking whether $a \in D$ produces a direct contradiction with asking whether $a \in f(a)$. This is precisely the same diagonal disagreement, now expressed through the language of sets rather than digits.

Now we turn to the second, classical incarnation: the real numbers themselves.

Example 1 (decimal diagonalization with an explicit, asymmetric list). Suppose someone claims the following list enumerates all real numbers in $(0,1)$ (we deliberately choose an irregular, asymmetric list rather than a suspiciously clean pattern):

(Each row continues infinitely; we only need the boldfaced diagonal digits $d_{n,n}$ to run the construction, though of course a genuine list would need every digit specified. Here we only need finitely many rows to illustrate the mechanism; the full proof runs this over all of $\mathbb{N}$.) Read the diagonal digits: $d_{1,1} = 3$, $d_{2,2} = 9$, $d_{3,3} = 5$, $d_{4,4} = 0$, $d_{5,5} = 5$. Apply the rule $e_n = 5$ if $d_{n,n}\ne 5$, else $e_n = 6$:

• $d_{1,1} = 3 \ne 5 \Rightarrow e_1 = 5$
• $d_{2,2} = 9 \ne 5 \Rightarrow e_2 = 5$
• $d_{3,3} = 5 \Rightarrow e_3 = 6$
• $d_{4,4} = 0 \ne 5 \Rightarrow e_4 = 5$
• $d_{5,5} = 5 \Rightarrow e_5 = 6$

So the diagonal number begins

(continuing with 5's and 6's according to further diagonal digits, which we haven't been given but which the construction handles identically for every subsequent row). Check disagreement directly:

• $y$ vs. $x_1 = 0.30710\ldots$: digit 1 is $5$ vs. $3$ — differ. So $y \ne x_1$.
• $y$ vs. $x_2 = 0.49189\ldots$: digit 2 is $5$ vs. $9$ — differ. So $y \ne x_2$.
• $y$ vs. $x_3 = 0.27503\ldots$: digit 3 is $6$ vs. $5$ — differ. So $y \ne x_3$.
• $y$ vs. $x_4 = 0.14009\ldots$: digit 4 is $5$ vs. $0$ — differ. So $y \ne x_4$.
• $y$ vs. $x_5 = 0.66635\ldots$: digit 5 is $6$ vs. $5$ — differ. So $y \ne x_5$.

Every row is refuted at its own diagonal slot, exactly as the proof of Uncountability of $\mathbb{R}$ guarantees for an infinite list. No finite check can complete the proof — that requires the general argument over all $n \in \mathbb{N}$ — but this shows concretely how the abstract construction turns into an actual, checkable number that dodges every listed row.

Example 2 (the power-set version, worked with a genuinely infinite, "generic" function). Let $A = \mathbb{N} = \{0, 1, 2, 3, \dots\}$ and suppose we're given the specific function $f : \mathbb{N} \to \mathcal{P}(\mathbb{N})$ defined by

the set of proper divisors of $n$ together with $n^2$ (for $n = 0$, every nonzero natural number divides $0$, so to keep things well-defined we set $f(0) = \{0\}$ by convention — the exact rule for $f$ doesn't matter for what follows, we just need some concrete function to test). Let's compute a few values:

• $f(1) = \varnothing \cup \{1\} = \{1\}$ (1 has no proper divisors, $1^2=1$).
• $f(2) = \{1\} \cup \{4\} = \{1,4\}$.
• $f(3) = \{1\} \cup \{9\} = \{1,9\}$.
• $f(4) = \{1,2\} \cup \{16\} = \{1,2,16\}$.
• $f(6) = \{1,2,3\} \cup \{36\} = \{1,2,3,36\}$.

Now apply the diagonal construction from the proof of Cantor's Theorem:

Check membership for small $x$, using the computed values above (and $f(0) = \{0\}$):

• $x = 0$: is $0 \in f(0) = \{0\}$? Yes. So $0 \notin D$.
• $x = 1$: is $1 \in f(1) = \{1\}$? Yes. So $1 \notin D$.
• $x = 2$: is $2 \in f(2) = \{1,4\}$? No. So $2 \in D$.
• $x = 3$: is $3 \in f(3) = \{1,9\}$? No. So $3 \in D$.
• $x = 4$: is $4 \in f(4) = \{1,2,16\}$? No. So $4 \in D$.
• $x = 6$: is $6 \in f(6) = \{1,2,3,36\}$? No. So $6 \in D$.

So far $D \supseteq \{2,3,4,6,\dots\}$ and excludes $0,1$; a full description of $D$ would require checking every $n$, but we don't need to finish that computation. What matters is the abstract guarantee: whatever $D$ turns out to be exactly, it cannot equal $f(a)$ for any particular $a \in \mathbb{N}$. For instance, could $D = f(2) = \{1,4\}$? We already showed $2 \in D$, but $2 \notin f(2) = \{1,4\}$ — so indeed $D \ne f(2)$, matching the theorem's guarantee. The same style of check would refute $D = f(a)$ for any candidate $a$, by testing whether $a \in D$ versus $a \in f(a)$ exactly as the general proof shows. This example illustrates that the abstract proof isn't just an existence argument in a vacuum — for any concrete $f$ you can name, you can concretely verify, case by case, that the diagonal set $D$ escapes the range of $f$.