ratiocin — Interactive Math Wiki

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}

Interactive Visualization

Diagonal Argument Explorer

Explore the argument step by step. 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.

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

1

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

2

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

3

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

4

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: Power Set Argument

Power Set Diagonal Explorer

Explore Cantor's Theorem with a finite set. Toggle memberships in the grid, then watch the rogue set construction unfold.

4

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)?