Диагональный аргумент Кантора: ℝ несчётно

Теорема

Множество вещественных чисел $\mathbb{R}$ несчётно. Не существует сюръекции из $\mathbb{N}$ в $\mathbb{R}$.

Доказательство (диагональный аргумент Кантора, 1891)

Предположим противное: все вещественные числа из $[0, 1)$ можно выписать в бесконечную последовательность $r_1, r_2, r_3, \ldots$

Запишем каждое $r_i$ десятичной дробью:

$r_i = 0.d_{i1}d_{i2}d_{i3}\ldots$

Построим новое число $x = 0.x_1 x_2 x_3 \ldots$, у которого каждая цифра $x_i$ отличается от $d_{ii}$ — от диагональной цифры:

$x_i \neq d_{ii}$

Тогда $x$ отличается от каждого $r_i$ по меньшей мере в $i$-м десятичном знаке. Значит, $x$ нет в нашем списке — а мы предполагали, что выписали все вещественные числа. Противоречие. $\blacksquare$

Одна тонкость, которую обычно пропускают

У некоторых чисел два десятичных представления: $0{,}4999\ldots = 0{,}5000\ldots$ Если строить $x$ неосторожно, можно получить число, которое записано иначе, чем каждое $r_i$, но равно одному из них.

Лечится это ограничением выбора цифр: берите $x_i$ из множества $\{4, 5\}$, скажем $x_i = 4$ при $d_{ii} = 5$ и $x_i = 5$ иначе. Такое число не содержит ни хвоста из девяток, ни хвоста из нулей, поэтому его представление единственно, и «отличается по записи» означает «отличается как число».

Сам аргумент шире, чем вещественные числа. В той же форме он доказывает теорему Кантора: для любого множества $A$ мощность $2^A$ строго больше мощности $A$. Диагональ здесь — это множество тех элементов, которые не принадлежат собственному образу.

Nikolay Eremeev, Senior Data Infrastructure Engineer. Пишет о том, что строит в продакшене. CV ·hi@nikolay-eremeev.com