Why the real numbers can't be listed

Can you write every real number in one list?

No. For any list you write, a number can be built that differs from every row, so some number is always missing. The page shows this first for sequences of 0s and 1s, then for real numbers.

Before you start · 3 quick checks on functions and maps, about 2 min

Definitions

\(\mathbb N=\{1,2,3,\dots\}\).

A set \(A\) is countable if \(A\) is empty or there is a surjection \(f:\mathbb N\to A\). A set that is not countable is uncountable.

\(\{0,1\}^{\mathbb N}\) is the set of infinite binary sequences \(s=(s(1), s(2), s(3), \dots)\) with each \(s(n)\in\{0,1\}\).

Fine print: lists, repeats and the empty set

For a nonempty set \(A\), this is equivalent to a list \(a_1, a_2, a_3, \dots\) in which every element of \(A\) appears; repeats are allowed.

Formally, such a sequence is a function \(s:\mathbb N\to\{0,1\}\).

This page works with binary sequences instead of decimal expansions of real numbers, because some reals have two expansions (\(0.4999\ldots=0.5\)), while two binary sequences that differ in one position are different objects by definition.

1 See

Beat the diagonal

Try to list every infinite sequence of 0s and 1s. Edit the first 8 digits of the first 8 rows. The page constructs the first 8 digits of \(t\), guaranteeing that \(t\) differs from each displayed row. Stage 3 extends the construction to every row of an infinite list.

Click a digit to flip it, or focus it and press Enter or Space. Arrow keys move between digits.

Only the first 8 digits of \(t\) are determined by the 8 rows shown. Digit 9 of \(t\) comes from row 9, which is off screen.

Start from a random list

Seed

Watch the construction step by step

The grid shows the start of a list \(s_1, s_2, \dots, s_8\) of binary sequences, 10 digits of each. The list and every row continue forever. The highlighted cells form the diagonal: digit 1 of row 1, digit 2 of row 2, and so on.

Press Step to build a new sequence \(t\) by the rule \(t(n)=1-s_n(n)\): flip digit \(n\) of row \(n\). After step \(n\), \(t\) and \(s_n\) disagree at digit \(n\), so \(t\) is not \(s_n\).

Key point Flipping digit \(n\) of row \(n\) gives a sequence that differs from every row. Adding that sequence to the list only produces a new missing one.

2 Try

Adding t, and listing the rationals

Adding the missing sequence

Listing the positive rationals

Diagonalizing a list of rationals

Key point The positive rationals can be listed by walking the grid of fractions, so a dense set can be countable. A diagonal number gives a contradiction only when it belongs to the set being listed.

3 Prove

The binary sequences are uncountable, and so are the reals

The idea in three steps

Suppose some list \(s_1, s_2, s_3, \dots\) contains every sequence of 0s and 1s.
Flip digit \(n\) of row \(n\), for every \(n\), to get a new sequence \(t\).
\(t\) differs from row \(n\) at digit \(n\), for every \(n\). So \(t\) is not on the list, and the list was not complete.

Theorem 1

\(\{0,1\}^{\mathbb N}\) is uncountable.

Setting: \(\mathbb N=\{1,2,3,\dots\}\); \(\{0,1\}^{\mathbb N}\) is the set of all functions \(\mathbb N\to\{0,1\}\); countable means empty or the image of a surjection from \(\mathbb N\). Method: proof by contradiction.

Theorem 2: \([0,1]\) and \(\mathbb R\) are uncountable (5 lines)

Theorem 2 (corollary)

\([0,1]\) and \(\mathbb R\) are uncountable.

Uses: Theorem 1; the comparison test for series of nonnegative terms, with \(\sum_{n\ge1}10^{-n}=\tfrac19\); a subset of a countable set is countable; \(\mathbb N=\{1,2,3,\dots\}\).

Scratch work, not part of the proof. The map uses base 10 with digits 0 and 1 only. In base 2 the sequences \(0111\ldots\) and \(1000\ldots\) both give \(\tfrac12\), so a base-2 map would fail to be injective. In base 10 the tail after the first difference is at most \(10^{-m}/9\), which is smaller than the gap \(10^{-m}\). For example, \(\varphi(1000\ldots)=0.1\) and \(\varphi(0111\ldots)=0.0111\ldots=\tfrac1{90}\).

Going further: Cantor's theorem

The same idea works for any set \(A\). Given a function \(g\) from \(A\) to the set of all subsets of \(A\), form \(T=\{a\in A : a\notin g(a)\}\). For each \(a\), the sets \(T\) and \(g(a)\) disagree about whether \(a\) belongs to them, just as \(t\) and \(s_n\) disagree at digit \(n\). So no set maps onto its power set. Taking \(A=\mathbb N\) and matching each subset with its 0/1 indicator sequence gives Theorem 1.

Key point No surjection from \(\mathbb N\) onto the 0/1 sequences exists. Sending each sequence to a number in \([0,1]\) one-to-one then shows that \([0,1]\) and \(\mathbb R\) are uncountable.

4 Apply