Cantor's diagonal argument

Before we can talk about whether a problem is "computable," we need to know whether there are even enough programs to solve all possible problems. Cantor's 1891 diagonal argument answers that with a definitive no: there are fundamentally more languages than there are programs.

So even before you've seen the halting problem or A_TM, you already know undecidable problems must exist. The diagonal argument is the original proof that "computer scientists have something to do" — there will always be limits.

Real-world analogy

Imagine you tried to list every infinite-digit decimal number 0.d₁d₂d₃… no matter how cleverly you order them. Cantor's argument says: take the i-th digit of the i-th number, add 1 to it (mod 10), and concatenate. The resulting number disagrees with every number on your list at at least one digit. So your list missed at least one real number — and by extension, cannot be exhaustive.

Let 2^ℕ = {f : ℕ → {0, 1}} denote the set of all functions from the natural numbers to {0, 1}. Equivalently: infinite binary strings.

Vocabulary refresher

• Countable: can be put in 1-to-1 correspondence with ℕ. Example: integers, rationals, finite strings, Turing machines.
• Uncountable: NOT countable. Example: real numbers, infinite binary strings, all subsets of ℕ.
• Surjection: a function f : A → B is surjective ("onto") if every b ∈ B has some a ∈ A with f(a) = b.
• Enumeration: a list f₁, f₂, … i.e. a surjective f : ℕ → S.

The proof strategy is proof by contradiction: assume an enumeration exists, then construct a specific function g that cannot be in any position of the list.

Suppose for contradiction that 2^ℕ were countable. Then we could list all its elements:

Picture the list as an infinite table. Row i shows f_i's values: f_i(0), f_i(1), f_i(2), …

        col 0   col 1   col 2   col 3   …
f₁  →   f₁(0)   f₁(1)   f₁(2)   f₁(3)   …
f₂  →   f₂(0)   f₂(1)   f₂(2)   f₂(3)   …
f₃  →   f₃(0)   f₃(1)   f₃(2)   f₃(3)   …
f₄  →   f₄(0)   f₄(1)   f₄(2)   f₄(3)   …
 ⋮       ⋮       ⋮       ⋮       ⋮

The diagonal consists of the underlined cells f_i(i−1): f₁(0), f₂(1), f₃(2), … Now define a new function:

That is, take the (n+1)-th row's n-th entry and flip it.

Why g is not in the list

Suppose, for further contradiction, that g = f_k for some specific k ≥ 1. Then in particular g(k−1) = f_k(k−1). But by our construction:

Combining: f_k(k−1) = 1 − f_k(k−1). But a Boolean value cannot equal its own negation. Contradiction. So no such k exists. ∎

The single key insight

g only needs to disagree at one cell per row. By targeting the diagonal, g is guaranteed to differ from row k at column k−1, no matter what row k contains. The diagonal acts as a "uniform target" — one cell per supposed-listed function.

Let's do this with concrete numbers. Suppose someone claims they've listed every binary sequence and gives us these 4 as the first four entries:

        n=0   n=1   n=2   n=3   n=4   n=5  …
f₁  →    0     1     0     1     1     0
f₂  →    1     1     0     0     1     0
f₃  →    0     0     1     1     0     0
f₄  →    1     0     0     0     1     1

The bold cells are the diagonal: f₁(0)=0, f₂(1)=1, f₃(2)=1, f₄(3)=0.

Now construct g by flipping each diagonal bit:

g(0) = 1 − f₁(0) = 1 − 0 = 1
g(1) = 1 − f₂(1) = 1 − 1 = 0
g(2) = 1 − f₃(2) = 1 − 1 = 0
g(3) = 1 − f₄(3) = 1 − 0 = 1
…

So g starts 1, 0, 0, 1, ... Compare with each row:

• g vs f₁: g(0) = 1, f₁(0) = 0. Different at index 0 ⇒ g ≠ f₁.
• g vs f₂: g(1) = 0, f₂(1) = 1. Different at index 1 ⇒ g ≠ f₂.
• g vs f₃: g(2) = 0, f₃(2) = 1. Different at index 2 ⇒ g ≠ f₃.
• g vs f₄: g(3) = 1, f₄(3) = 0. Different at index 3 ⇒ g ≠ f₄.

g disagrees with EVERY row at exactly one cell. So g is not in the list, contradicting the assumption of exhaustiveness.

Diagonalization is so prevalent that any time you see "for every algorithm X, here's an input that escapes it", you should suspect a diagonal argument is hiding behind it.

Why it works only for the right things

Diagonalization needs three ingredients:

1. An enumeration of the things you want to show miss something (functions, TMs, programs in time bound).
2. A way to simulate each item from its description (for TMs: the universal TM).
3. A way to flip the answer (for {0,1} functions: subtract from 1; for TMs: swap accept and reject).

These are the same ingredients that make P ≠ NP famously HARD to prove — flipping the answer of an NP machine isn't obviously possible while staying in NP.

• Pitfall 1 · "But what if we list g too?"
  If g is appended as f_m+1 to your list, diagonalize again on the extended list — you'll produce g′ that flips the new (m+1)-th diagonal cell. The argument adapts. No countable list can be closed under diagonalization.
• Pitfall 2 · "g is a function — what does 'in the list' mean exactly?"
  "In the list" means there exists some specific index k with f_k = g as functions: ∀ n, f_k(n) = g(n). The contradiction shows that for ANY k, there is at least one n (namely n = k−1) where they disagree.
• Pitfall 3 · "Doesn't this depend on which diagonal we pick?"
  No. We could flip any cell per row, as long as we pick a different column per row. The diagonal is just the most convenient choice. Any function π : ℕ → ℕ that's a bijection works as a target.
• Pitfall 4 · "Cantor proved this 130+ years ago — what's modern about it?"
  Cantor proved sets have different sizes. We use the same proof PATTERN to prove computational limits. The reapplication to TMs is the conceptual leap that founded computer science.
• Pitfall 5 · "Couldn't we have a 'super-clever' enumeration that avoids diagonalization?"
  No. The proof targets ANY purported enumeration. There's no escape: as long as you commit to a specific ordering (any ordering), the diagonal argument constructs an escape function relative to that ordering.

• Q1. Why is the flipped function g not in the list?
  Because g disagrees with row i at column i−1, for every i ≥ 1. So g ≠ f_i for every i in the list.
• Q2. Why does Cantor's theorem matter for computability?
  There are only countably many Turing machines (each is a finite description). So the languages recognized by TMs form a countable set. But there are uncountably many languages. Therefore most languages are not Turing-recognizable.
• Q3. Is this the same as the A_TM diagonalization (Problem 3)?
  Same technique, different setting. Here, rows are arbitrary functions; in Problem 3, rows are Turing machines and we flip "accepts" / "rejects" instead of bits.
• Q4. Doesn't this depend on the order of listing?
  No. We don't need the list in any particular order. We just need an enumeration f₁, f₂, … — any surjection ℕ → 2^ℕ. The diagonal trick works against any such enumeration.
• Q5. Bonus: prove that the reals between 0 and 1 are uncountable.
  Each real x ∈ [0,1) has a binary expansion 0.x₀x₁x₂… which is exactly a function ℕ → {0, 1}. So |[0,1)| = |2^ℕ|. Cantor's theorem applies. (Caveat: dyadic numbers have two expansions; that quirk doesn't break the proof, only complicates the bijection.)

1. State the theorem (1 min): "There are more binary sequences than natural numbers."
2. Real-world hook (1 min): "You will see this proof technique 5 more times this semester. Watch carefully."
3. Reset the widget; explain rows and columns (1 min).
4. Step through 5 rows manually; point out diagonal cells (2 min).
5. Flip the diagonal; show how g escapes each row (2 min).
6. Walk through the worked example for n = 4 with concrete bits (3 min).
7. State the consequence: most languages are not Turing-recognizable (1 min).
8. Q&A (3-5 min): expect "what about g?", "does ordering matter?", "what if we listed g too?".