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

Теорема

Множество вещественных чисел $\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$