Chapter 1 · Sets — medium

Cantor's Diagonal Argument

Proof that the real numbers are uncountable — there is no bijection between ℕ and ℝ.

Setup

Consider the real numbers in the interval $[0, 1]$ . Each can be written as an infinite binary expansion:

r = 0.b_1 b_2 b_3 \ldots \quad \text{where } b_i \in \{0, 1\}

Assume for contradiction that we can enumerate all such reals in a list:

\begin{aligned} s_1 &= 0.\,b_{1,1}\; b_{1,2}\; b_{1,3}\; \ldots \\ s_2 &= 0.\,b_{2,1}\; b_{2,2}\; b_{2,3}\; \ldots \\ s_3 &= 0.\,b_{3,1}\; b_{3,2}\; b_{3,3}\; \ldots \\ &\;\;\vdots \end{aligned}

Build the Missing Witness

Diagonal Witness Builder

Use the grid as a proposed complete list. The side panel extracts the diagonal, flips it into the witness $d$ , and records the exact row where each mismatch happens. Click any cell to modify a digit, then press Play to watch the proof unfold.

6×6

The grid shows 6 binary sequences — each row is a real in [0,1] written in binary. We want to prove no list can contain all of them.

Edit cells or resize with ±. Press Play to watch the diagonal argument.

Binary decimal prefixes

0.b₁b₂... is a real in [0,1]

s₁ = 0.010101₂≈ 0.3281

s₂ = 0.101010₂≈ 0.6563

s₃ = 0.010101₂≈ 0.3281

s₄ = 0.101010₂≈ 0.6563

s₅ = 0.010101₂≈ 0.3281

s₆ = 0.101010₂≈ 0.6563

After the diagonal is flipped, the witness d is another binary decimal prefix.

Witness Builder

d escapes the list

The grid is only the source. The proof is the witness: read one diagonal digit from each row, flip it, then keep one mismatch certificate per row.

Diagonal tapeb_i,i

b_1,1·

b_2,2·

b_3,3·

b_4,4·

b_5,5·

b_6,6·

Anti-diagonal witnessd_i = 1 - b_i,i

d₁·flip

d₂·flip

d₃·flip

d₄·flip

d₅·flip

d₆·flip

Mismatch certificatesone per row

·s₁wait for digit 1

·s₂wait for digit 2

·s₃wait for digit 3

·s₄wait for digit 4

·s₅wait for digit 5

·s₆wait for digit 6

d = 0.······

Press Play to turn the diagonal into a missing sequence.

Note

How to read it: the proof is not the colored grid. The grid supplies diagonal facts; the witness panel turns those facts into $d$ and then into one certificate for every row: $d$ differs from $s_i$ at digit $i$ .

Another View: Binary Addresses

Nested Interval Microscope

The matrix is not the only way to see the trick. A binary expansion is also an address inside $[0,1]$ : each digit chooses the left or right half of the current interval. The construction of $d$ can be viewed as repeatedly choosing the opposite half from row $s_i$ at digit $i$ .

Binary address microscope

Nested interval view

Flip one address digit, then zoom in

current prefix

0.110101

digit 1

row s₁ has 0; d chooses 1

certificate kept

digit 2

row s₂ has 0; d chooses 1

certificate kept

digit 3

row s₃ has 1; d chooses 0

certificate kept

digit 4

row s₄ has 0; d chooses 1

certificate kept

digit 5

row s₅ has 1; d chooses 0

certificate kept

digit 6

row s₆ has 0; d chooses 1

certificate kept

Less Conventional Examples

Other Ways to Break a List

The diagonal proof is the central result here, but the educational examples do not have to be literal diagonals. One route uses length instead of self-disagreement; other routes keep the anti-list idea while replacing binary decimals with everyday yes/no objects.

Not diagonal

Length-budget proof

If a list were countable, wrap item n in an interval with a rapidly shrinking length. The total cover can be made smaller than the whole unit interval, so it cannot cover every real.

Same anti-list move, no grid required

disagree once per listed object

Questionnaire

row n is one person's yes/no answer sheet

make a new sheet that answers question n opposite person n

the new sheet cannot be any listed person

Feature Flags

row n is a product build with infinite on/off flags

set flag n to the opposite of build n

the ghost build is absent from every release list

Access Codes

row n is a binary unlock code from a catalog

choose digit n to disagree with code n

the constructed code is guaranteed uncataloged

The Diagonal Construction

Define a new number $\tip{d — the number we construct by flipping the diagonal}{d} = 0.\,d_1\, d_2\, d_3 \ldots$ by flipping the diagonal:

\tip{d_i — the i-th digit of our constructed number}{d_i} = \begin{cases} 1 & \text{if } b_{i,i} = 0 \\ 0 & \text{if } b_{i,i} = 1 \end{cases}

In other words, $d_i \neq b_{i,i}$ for every $i$ .

The Contradiction

Proof

Assume a complete enumeration $s_1, s_2, s_3, \ldots$ of all reals in $[0,1]$ exists.

Construct $d$ by flipping the diagonal: set $d_i = 1 - b_{i,i}$ .

For every $n \in \mathbb{N}$ , the number $d$ differs from $s_n$ at position $n$ , so $d \neq s_n$ .

But $d \in [0,1]$ , so $d$ should be in the list — contradiction.

Result

Conclusion: There is no surjection $f: \mathbb{N} \to [0,1]$ . The set of real numbers is uncountable: $|\mathbb{R}| > |\mathbb{N}|$ .

We write $|\mathbb{N}| = \aleph_0$ and $|\mathbb{R}| = \mathfrak{c} = 2^{\aleph_0}$ .

Cantor's Theorem

From Reals to Power Sets

Proof

Cantor's Theorem. For any set $A$ , there is no surjection $f: A \to \mathcal{P}(A)$ .

Define the rogue set $\tip{R — the rogue set: all elements of A not contained in their own image under f}{R} = \left\{\, a \in A : a \notin f(a) \,\right\}$ . Then $R \neq f(x)$ for every $x$ : if $x \in R$ then $x \notin f(x) = R$ , and if $x \notin R$ then $x \in f(x) = R$ — either way a contradiction. Flipping membership ( $\in$ vs $\notin$ ) plays the same role as flipping bits.

Interactive: Rogue Set Argument

Rogue Set Builder

Explore Cantor's Theorem with a finite set. The grid is only a membership lookup table; the right panel builds the rogue set $R = \{a \in A : a \notin f(a)\}$ and compares it against every proposed image. Toggle memberships, then press Play.

Set up a mapping f: A → P(A) where A = {1,…,4}. Each row i shows which elements belong to f(i). We'll prove no such map can be surjective.

Toggle cells to change membership. Resize with ±, then press Play.

Rogue Set R

R = { a ∈ A : a ∉ f(a) }

?Is 1 ∈ f(1)?

?Is 2 ∈ f(2)?

?Is 3 ∈ f(3)?

?Is 4 ∈ f(4)?

Cantor's Diagonal Argument

Setup

Build the Missing Witness

Diagonal Witness Builder

d escapes the list

Another View: Binary Addresses

Nested Interval Microscope

Less Conventional Examples

Other Ways to Break a List

The Diagonal Construction

The Contradiction

∎Proof

Cantor's Theorem

From Reals to Power Sets

Interactive: Rogue Set Argument

Rogue Set Builder

Rogue Set R

Proof