Cantor Diagonal Method — Definition, Formula & Examples

The Cantor Diagonal Method is a proof technique that constructs a new element not in a given list by changing the diagonal entries, most famously used to show that the set of real numbers is uncountable.

Given any function $f: \mathbb{N} \to S$ from the natural numbers to a set $S$ of infinite sequences (or real numbers), diagonalization constructs an element $d \in S$ that differs from $f(n)$ in the $n$ -th position for every $n \in \mathbb{N}$ , thereby proving $f$ cannot be surjective and hence $S$ is uncountable.

How It Works

Suppose someone claims to have a complete list of all real numbers between 0 and 1, written as infinite decimal expansions. You examine the first digit of the first number, the second digit of the second number, the third digit of the third number, and so on — forming a "diagonal" sequence. Then you construct a new number by changing every digit along this diagonal (for instance, replacing each digit

d

with

d+1 \mod 10

, avoiding 0 and 9 to prevent issues with dual representations). This new number differs from the

n

-th listed number in its

n

-th decimal place, so it cannot appear anywhere in the list. Since this works for any proposed list, no list can contain all real numbers, proving the reals are uncountable.

Example

Problem: Suppose someone lists real numbers in (0,1) as infinite decimals. Show a number missing from the list.

Step 1: Write out the proposed list, focusing on the diagonal digits (the n-th digit of the n-th number).

f(1) = 0.\mathbf{3}1415\ldots \quad f(2) = 0.7\mathbf{2}360\ldots \quad f(3) = 0.81\mathbf{8}28\ldots \quad f(4) = 0.141\mathbf{5}9\ldots

Step 2: Read the diagonal: the 1st digit of f(1) is 3, 2nd digit of f(2) is 2, 3rd digit of f(3) is 8, 4th digit of f(4) is 5. The diagonal sequence begins 3, 2, 8, 5, ...

\text{Diagonal} = 3,\, 2,\, 8,\, 5,\, \ldots

Step 3: Construct a new number by replacing each diagonal digit: add 1 to each (using mod 10, but avoiding 0 and 9). So 3→4, 2→3, 8→7, 5→6.

d = 0.4376\ldots

Answer: The number

d = 0.4376\ldots

differs from

f(n)

in its

n

-th decimal place for every

n

, so

d

cannot appear anywhere in the list. The list is necessarily incomplete.

Why It Matters

This method is the foundation for understanding different sizes of infinity, a central topic in real analysis and set theory courses. It also underlies the Halting Problem proof in computer science, which shows no algorithm can decide whether an arbitrary program will halt. Diagonalization arguments appear throughout mathematical logic, computability theory, and the study of cardinality.

Common Mistakes

Mistake: Assuming the method only works for decimal representations and failing to see it as a general technique.

Correction: Diagonalization applies to any countable list of infinite sequences — binary strings, functions from N to N, etc. The key idea is systematic disagreement along the diagonal, not the specific number base.