Cantor's Diagonal Argument: Why Some Infinities Are Bigger Than Others

Introduction

In 1891, Georg Cantor published a short paper that contained one of the most elegant and devastating proofs in the history of mathematics. In just a few pages, he demonstrated that the set of real numbers is strictly larger than the set of natural numbers, that infinity comes in different sizes, and that there is no way to list all real numbers in a sequence, no matter how clever your enumeration. The idea was so radical, so offensive to the mathematical establishment of his time, that it made Cantor genuine enemies. Leopold Kronecker called him a “corrupter of youth.” Henri Poincare described his work as a “disease” from which mathematics would one day recover. The hostility, combined with bouts of depression, contributed to Cantor spending the final years of his life in a sanatorium.

They were wrong, and he was right. Cantor's diagonal argument is now a cornerstone of modern mathematics, and the hierarchy of infinities he discovered underpins set theory, logic, topology, and theoretical computer science. It is also one of the most beautiful proofs I have ever encountered. The first time I saw it, as a sophomore working through a discrete math textbook, I felt the floor shift under my understanding of what “infinite” means. I want to walk you through it carefully, from the foundations to the furthest implications, because this proof changes how you think.

Countable Infinity

Before we can talk about uncountable sets, we need to be precise about what it means for a set to be countable. A set $S$ is countable if its elements can be placed in a one-to-one correspondence (a bijection) with the natural numbers $\mathbb{N} = \{1, 2, 3, \ldots\}$. In other words, you can list the elements of $S$ as $s_1, s_2, s_3, \ldots$ such that every element appears exactly once. The set is “listable.” You can write a program that, given enough time, will eventually print any element you name.

The natural numbers themselves are obviously countable (the identity function is the bijection). But what about the integers $\mathbb{Z}$? The integers extend in both directions: $\ldots, -3, -2, -1, 0, 1, 2, 3, \ldots$ It seems like there are “twice as many” integers as natural numbers. But Cantor showed this intuition is wrong. We can interleave the non-negative and negative integers into a single list:

This gives the enumeration $0, -1, 1, -2, 2, -3, 3, \ldots$ Every integer appears exactly once. So $|\mathbb{Z}| = |\mathbb{N}| = \aleph_0$. The integers are countable.

What about the rational numbers $\mathbb{Q}$? This is even more surprising. The rationals are dense: between any two rationals, there is another rational. Between 0 and 1, there are infinitely many. Between 0 and 0.001, there are infinitely many. It seems impossible that the rationals could be countable. But Cantor found a way, using the famous zigzag argument through an infinite grid.

Arrange all positive fractions $\frac{p}{q}$ in a two-dimensional grid where row $p$ and column $q$ correspond to the fraction $\frac{p}{q}$. Then traverse the grid along successive anti-diagonals, skipping any fraction that has already been listed in reduced form. This produces a sequence that hits every positive rational exactly once. Formally, Cantor used the pairing function:

This maps each pair $(p, q) \in \mathbb{N} \times \mathbb{N}$ to a unique natural number, establishing that $\mathbb{N} \times \mathbb{N}$ is countable. Since every rational can be written as $\frac{p}{q}$ with $p \in \mathbb{Z}$ and $q \in \mathbb{N}$, and since $\mathbb{Z} \times \mathbb{N}$ is countable (a countable union of countable sets is countable), it follows that:

The rationals, despite being dense in the real line, are countable. This is already deeply counterintuitive. But it sets the stage for Cantor's real discovery: that the real numbers are fundamentally different.

The Power Set and Cardinality

The cardinality of a set $A$, written $|A|$, is a measure of its size. For finite sets, cardinality is just the number of elements: $|\{a, b, c\}| = 3$. For infinite sets, Cantor defined cardinality through bijections: two sets have the same cardinality if and only if there exists a one-to-one correspondence between them.

The cardinality of the natural numbers is called aleph-null, written $\aleph_0$. It is the smallest infinite cardinal. Every countably infinite set has cardinality $\aleph_0$. As we have seen:

Now the central question: what is the cardinality of the real numbers $\mathbb{R}$? Is $|\mathbb{R}| = \aleph_0$? Can we list all real numbers? Cantor's diagonal argument shows that the answer is no, and it does so with a proof of breathtaking economy.

The Diagonal Argument

This is the core of the post. I will present the proof carefully, step by step, because every detail matters.

Setup: Proof by Contradiction

Assume for contradiction that the set of real numbers in the interval $[0, 1]$ is countable. Then there exists a bijection $f: \mathbb{N} \to [0, 1]$, meaning we can list every real number in $[0, 1]$ as an infinite sequence:

where every real number in $[0, 1]$ appears somewhere in this list. Write each number in its decimal expansion:

where each $d_{ij}$ is a digit from 0 to 9, and $d_{ij}$ denotes the $j$-th decimal digit of the $i$-th number in our list. This gives us an infinite matrix of digits. Now look at the diagonal: the sequence of digits $d_{11}, d_{22}, d_{33}, d_{44}, \ldots$

Constructing the Forbidden Number

Define a new real number $x = 0.x_1 x_2 x_3 x_4 \ldots$ by choosing each digit $x_n$ to be different from the diagonal digit $d_{nn}$. Specifically, define:

We choose 6 and 7 (rather than, say, 0 and 9) deliberately to avoid the edge case where $0.999\ldots = 1.000\ldots$. By restricting our constructed digits to 6 and 7, the number $x$ has a unique decimal representation and cannot be equal to any number that differs from it in even a single digit.

The Contradiction

Now compare $x$ with every number in our supposedly complete list.

Therefore $x$ is not equal to any number in our list. But $x \in [0, 1]$ (it is a real number between 0 and 1, since all its digits are 6 or 7). This contradicts our assumption that the list contains every real number in $[0, 1]$.

The assumption that $[0, 1]$ is countable leads to a contradiction. Therefore:

Since $[0, 1] \subseteq \mathbb{R}$, it follows immediately that:

Cantor's Theorem: The Generalization

The diagonal argument for $\mathbb{R}$ is a special case of a far more general result. Cantor proved that for any set $S$, the power set $\mathcal{P}(S)$ (the set of all subsets of $S$) has strictly greater cardinality than $S$ itself:

The Proof

Suppose for contradiction that there exists a bijection $f: S \to \mathcal{P}(S)$. For every element $s \in S$, $f(s)$ is a subset of $S$. Now define the diagonal set:

The set $D$ contains exactly those elements of $S$ that are not members of their own image under $f$. Now, $D \subseteq S$, so $D \in \mathcal{P}(S)$. If $f$ is a bijection, then there must exist some $d \in S$ such that $f(d) = D$. We ask: is $d \in D$?

Both cases lead to contradiction, so no such bijection $f$ can exist. Therefore:

And since the function $g: S \to \mathcal{P}(S)$ defined by $g(s) = \{s\}$ is an injection (mapping each element to its singleton), we have $|S| \leq |\mathcal{P}(S)|$. Combined with inequality, this gives us:

The Infinite Tower

This theorem has a staggering consequence. Apply it iteratively starting from $\mathbb{N}$:

There is no largest infinity. For any infinite set, you can always construct a strictly larger one by taking its power set. The hierarchy of infinities does not terminate. It extends without end, an infinity of infinities.

For the specific case of the reals, it can be shown (through a construction involving characteristic functions and binary representations) that:

where $\mathfrak{c}$ is called the cardinality of the continuum. The real numbers have the same cardinality as the power set of the natural numbers. This is why the diagonal argument works on $\mathbb{R}$: listing the reals is equivalent to listing all subsets of $\mathbb{N}$, which Cantor's theorem says is impossible.

The Continuum Hypothesis

We now know that $\aleph_0 < 2^{\aleph_0} = |\mathbb{R}|$. But this raises a natural question: is there a cardinality strictly between $\aleph_0$ and $2^{\aleph_0}$? Does there exist an infinite set that is larger than the natural numbers but smaller than the reals?

Cantor believed the answer was no. He conjectured that there is no intermediate cardinality, that $2^{\aleph_0} = \aleph_1$, where $\aleph_1$ is defined as the next cardinal after $\aleph_0$. This is the Continuum Hypothesis (CH):

Cantor spent years trying to prove this and never succeeded. It turns out he could not have succeeded, for reasons that go to the very foundations of mathematics.

The Continuum Hypothesis is independent of ZFC. It can be neither proved nor disproved from the standard axioms of set theory. This is not a gap in our knowledge that further cleverness might close. It is a fundamental feature of the axiomatic system. The standard axioms do not contain enough information to determine the answer. You can build perfectly consistent mathematical universes where CH is true and equally consistent universes where it is false.

This connects directly to Godel's incompleteness theorems, which I wrote about in my post on Godel's incompleteness. Godel showed that any sufficiently powerful formal system contains statements that are true but unprovable. The Continuum Hypothesis is a concrete, natural example of exactly this phenomenon in the wild. It is not some artificial sentence constructed through Godel numbering. It is a genuine mathematical question about the size of the real number line, and the axioms we use cannot settle it.

Computational Implications

As someone who builds AI systems, this is where Cantor's theorem becomes personal. The diagonal argument is not just a fact about abstract set theory. It has direct, concrete consequences for what computers can and cannot do.

Most Functions Are Not Computable

Consider the set of all computer programs. Every program is a finite string over a finite alphabet (say, Unicode characters). The set of all finite strings over a finite alphabet is countable (enumerate them by length, then lexicographically within each length). Therefore:

Now consider the set of all functions from natural numbers to natural numbers, $\mathbb{N}^{\mathbb{N}}$. Each such function can be identified with an infinite sequence of natural numbers $(f(1), f(2), f(3), \ldots)$. By an argument analogous to the diagonal argument (or by noting that $|\mathbb{N}^{\mathbb{N}}| = |\mathbb{R}| = 2^{\aleph_0}$), this set is uncountable:

There are uncountably many functions but only countably many programs. Therefore, almost all functions from natural numbers to natural numbers are not computable by any program. The computable functions are a vanishingly small subset of all functions. In a precise measure-theoretic sense, if you pick a function “at random,” the probability that it is computable is zero.

This is a staggering fact. Almost all of mathematics is unreachable by algorithm. The computable world is an infinitesimal sliver of the mathematical universe.

The Halting Problem as Diagonalization

The undecidability of the Halting Problem, Turing's most famous result, is itself a diagonal argument in disguise. Suppose a program halts(P, x) could decide whether program $P$ halts on input $x$. Construct a new program $D$ that, on input $P$, does the opposite of what halts(P, P) predicts. Then $D(D)$ leads to contradiction. The structure is identical to Cantor's: you take the diagonal and flip it.

A Finite Illustration

Here is a Python implementation that demonstrates the diagonal construction on a finite list of decimal expansions. It takes a list of numbers in $[0, 1]$ and constructs a number that differs from each one at the corresponding decimal position, exactly mimicking Cantor's argument on a finite scale.

# Cantor's Diagonal Argument — finite illustration

# Demonstrates the construction on a list of real numbers in [0, 1]


def get_decimal_digits(x, num_digits):
    """Extract decimal digits of x in [0, 1]."""
    digits = []
    for _ in range(num_digits):
        x *= 10
        digit = int(x)
        digits.append(digit)
        x -= digit
    return digits

def cantors_diagonal(numbers):
    """Construct a number not in the list using diagonalization."""
    n = len(numbers)
    digit_matrix = [get_decimal_digits(x, n) for x in numbers]

    # Print the matrix with diagonal highlighted

    print("Decimal expansion matrix:")
    print("-" * 40)
    for i, (num, digits) in enumerate(zip(numbers, digit_matrix)):
        row = ""
        for j, d in enumerate(digits):
            if i == j:
                row += f"[{d}]"  # diagonal digit

            else:
                row += f" {d} "
        print(f"  r{i+1} = 0.{row}")

    # Construct the anti-diagonal number

    diagonal_digits = [digit_matrix[i][i] for i in range(n)]
    new_digits = [6 if d != 6 else 7 for d in diagonal_digits]

    print(f"\nDiagonal digits:      {diagonal_digits}")
    print(f"Anti-diagonal digits: {new_digits}")

    new_number = sum(d * 10 ** (-(i + 1)) for i, d in enumerate(new_digits))
    print(f"\nConstructed x = 0.{''.join(map(str, new_digits))}...")
    print(f"x = {new_number:.10f}")

    # Verify x differs from every listed number

    print(f"\nVerification:")
    for i in range(n):
        print(f"  x != r{i+1}: digit {i+1} is {new_digits[i]} != {diagonal_digits[i]}")

    return new_number

# Example: try to "list" some reals in [0, 1]

reals = [0.14159265, 0.71828182, 0.30258509, 0.44948974, 0.64872127]
x = cantors_diagonal(reals)
print(f"\nNo matter how long your list, x is NOT on it.")

Run this and you will see the diagonal argument in action. The key insight is that this construction works for any list, no matter how long. Even an infinite list would have a number that escapes it. That is the proof.

Conclusion

Cantor's diagonal argument proves, in a few lines, that the real numbers cannot be listed. That $|\mathbb{R}| > |\mathbb{N}|$. That infinity is not one thing but a vast hierarchy of ever-larger magnitudes. His generalized theorem proves that for any set $S$, we have $|\mathcal{P}(S)| > |S|$, so the hierarchy never terminates. There is no ceiling on infinity.

The implications cascade outward. The Continuum Hypothesis shows that even basic questions about this hierarchy are independent of our axioms. The computational consequences show that almost all mathematical functions are forever beyond the reach of any algorithm. The diagonal method itself became a universal tool, reappearing in Godel's incompleteness theorems, Turing's undecidability results, and throughout complexity theory.

I keep coming back to this proof because it captures something I find deeply motivating about mathematics. Cantor was attacked, marginalized, and driven to despair for pursuing an idea that turned out to be correct and foundational. The mathematical establishment rejected his work not because it was wrong but because it was too radical, too strange, too far ahead of the intuitions of his time. And yet the proof itself is so simple that any careful reader can follow it. The truth was right there on the page, waiting for people to accept it.

As someone who studies both medicine and computer science, I find Cantor's work a constant reminder that the limits of our current tools are not the limits of reality. The computable functions are a measure-zero subset of all functions. The provable theorems are a subset of the true theorems. The models we build are finite approximations of structures that may be, in a precise Cantorian sense, inexhaustibly larger than anything we can represent. That is not a reason for despair. It is a reason for humility, and a reason to keep building.