Cantor's Diagonalization: Why Some Infinities Are Bigger Than Others

Terminology

What & Why

In 1891, Georg Cantor proved something that defied centuries of mathematical intuition: not all infinities are the same size. The set of real numbers is strictly larger than the set of natural numbers, even though both are infinite. His proof technique, diagonalization, is one of the most elegant and influential arguments in all of mathematics.

Before Cantor, "infinity" was treated as a single concept. Cantor showed that infinity comes in a hierarchy of sizes. The natural numbers, integers, and rationals all have the same cardinality (\aleph_0), but the reals are fundamentally larger. This discovery created an entirely new branch of mathematics (set theory) and provoked fierce controversy. Some mathematicians, notably Leopold Kronecker, rejected Cantor's work entirely.

For computer scientists, diagonalization is not just a historical curiosity. Turing used the same technique to prove the halting problem is undecidable. It appears in complexity theory (the time hierarchy theorem), in the proof that certain languages are not regular, and in showing that the set of all programs is countable while the set of all functions is not. Understanding diagonalization is understanding one of the most powerful proof tools in the field.

How It Works

Countable Sets: Surprisingly Many Things Are the Same Size

A set is countable if you can list its elements as a sequence: first, second, third, and so on. The natural numbers \{0, 1, 2, 3, \ldots\} are the prototype. Surprisingly, the integers and even the rationals are also countable, despite seeming "bigger."

The rationals are countable because you can arrange them in a grid and traverse it diagonally, hitting every fraction exactly once (after skipping duplicates). This zig-zag enumeration shows |\mathbb{Q}| = |\mathbb{N}| = \aleph_0.

The Diagonal Argument: Reals Are Uncountable

Cantor proved |\mathbb{R}| > |\mathbb{N}| by contradiction. Suppose someone claims to have a complete list of all real numbers between 0 and 1. Write each number as an infinite decimal:

Cantor constructs a new real number d by looking at the diagonal: the n-th digit of d differs from the n-th digit of the n-th number in the list. For example, if the diagonal digits are 5, 6, 4, 1, 7, then d could use 6, 7, 5, 2, 8 (adding 1 to each, wrapping 9 to 0).

This number d is a real number between 0 and 1, but it cannot be anywhere in the list. It differs from the first number in the first digit, from the second number in the second digit, and so on. Every position in the list is ruled out. This contradicts the assumption that the list was complete. Therefore, no such list exists, and |\mathbb{R}| > |\mathbb{N}|.

Cantor's Theorem: The Power Set Is Always Bigger

Cantor generalized this result. For any set S, the power set \mathcal{P}(S) (the set of all subsets) has strictly greater cardinality:

This creates an infinite hierarchy of infinities: |\mathbb{N}| < |\mathcal{P}(\mathbb{N})| < |\mathcal{P}(\mathcal{P}(\mathbb{N}))| < \cdots

The Continuum Hypothesis

Cantor conjectured that there is no set with cardinality strictly between |\mathbb{N}| and |\mathbb{R}|. This is the Continuum Hypothesis (CH). In 1940, Gödel showed CH is consistent with ZFC set theory. In 1963, Paul Cohen showed its negation is also consistent. CH is independent of ZFC: it can be neither proved nor disproved from the standard axioms. This is incompleteness in action.

Complexity Analysis

The critical insight for CS: the set of all programs is countable (each program is a finite string), but the set of all functions \mathbb{N} \to \mathbb{N} is uncountable. Therefore, most functions are not computable. There are uncountably many problems but only countably many algorithms.

Implementation

ALGORITHM DiagonalConstruct(listOfReals)
INPUT: listOfReals: a proposed complete list of reals in (0,1),
       each represented as an infinite decimal sequence
OUTPUT: a real number NOT in the list
BEGIN
  newDigits <- empty list

  FOR i FROM 0 TO LENGTH(listOfReals) - 1 DO
    diagonalDigit <- listOfReals[i].digit(i)  // i-th digit of i-th number
    // Choose a different digit (avoid 0 and 9 to prevent 0.999... = 1.000... issues)
    IF diagonalDigit = 5 THEN
      newDigit <- 6
    ELSE
      newDigit <- 5
    END IF
    APPEND newDigit TO newDigits
  END FOR

  RETURN "0." + JOIN(newDigits)
  // This number differs from every listed number at the diagonal position
END

ALGORITHM EnumerateRationals()
INPUT: none
OUTPUT: a sequence listing every positive rational exactly once
BEGIN
  // Traverse the grid of (numerator, denominator) pairs diagonally
  seen <- empty set
  sequence <- empty list

  FOR diagonal FROM 2 TO INFINITY DO
    FOR numerator FROM 1 TO diagonal - 1 DO
      denominator <- diagonal - numerator
      fraction <- REDUCE(numerator, denominator)
      IF fraction NOT IN seen THEN
        ADD fraction TO seen
        APPEND fraction TO sequence
        YIELD fraction
      END IF
    END FOR
  END FOR
END

ALGORITHM Cantorian_PowerSet_Proof(S, f)
INPUT: S: a set, f: a proposed bijection from S to P(S)
OUTPUT: a subset of S not in the range of f (proving f is not surjective)
BEGIN
  // Construct the "anti-diagonal" set
  D <- empty set

  FOR EACH element x IN S DO
    IF x NOT IN f(x) THEN
      ADD x TO D
    END IF
  END FOR

  // D differs from f(x) at element x for every x in S
  // Therefore D is not equal to f(x) for any x
  RETURN D
END

Real-World Applications

• Diagonalization proves the halting problem is undecidable: the set of programs is countable, but the "halting function" would require deciding membership in an uncountable set of behaviors
• In complexity theory, the time hierarchy theorem uses diagonalization to show that more time strictly increases computational power: $\text{DTIME}(n) \subsetneq \text{DTIME}(n^2)$
• The countability of programs versus uncountability of functions proves that most real numbers are not computable, most languages are not decidable, and most functions have no algorithm
• In formal language theory, diagonalization shows that the set of all languages over an alphabet is uncountable while the set of regular (or context-free) languages is countable
• Cantor's ideas underpin modern set-theoretic foundations used in type theory, which influences programming language design (Haskell, Agda, Lean)
• In data compression, the pigeonhole principle (a counting argument related to cardinality) proves that no lossless compression algorithm can compress all inputs

Key Takeaways

• Cantor's diagonal argument proves the real numbers are uncountable: no list can contain every real, because a new real can always be constructed by differing from each listed number at one digit
• The natural numbers, integers, and rationals all have the same cardinality $\aleph_0$, but the reals have strictly greater cardinality $2^{\aleph_0}$
• Cantor's theorem generalizes this: for any set $S$, the power set $\mathcal{P}(S)$ is strictly larger, creating an infinite hierarchy of infinities
• The Continuum Hypothesis (no cardinality between $\aleph_0$ and $2^{\aleph_0}$) is independent of ZFC, meaning it can be neither proved nor disproved from standard axioms
• For computer science, the key consequence is that programs are countable but functions are uncountable, so most functions have no algorithm
• Diagonalization is a universal proof technique that appears throughout CS: the halting problem, hierarchy theorems, and impossibility results all use it