Диагональ Кантора: несчётность вещественных чисел

Оказывается, бесконечности бывают разного размера — и вещественных чисел «больше», чем натуральных.

Несчётное множество — бесконечное множество, элементы которого нельзя занумеровать натуральными числами.

Мы видели, что рациональные числа счётны. Естественно ожидать, что и все числа на отрезке $[0,1]$ тоже можно занумеровать. Георг Кантор в 1891 году доказал обратное — и сделал это потрясающе простым «диагональным» приёмом. Так родилось понятие разных бесконечностей.

Диагональный аргумент

Предположим, что все вещественные числа отрезка $[0,1]$ удалось выписать в список — по одному на каждое натуральное число. Запишем их десятичными дробями. Теперь построим число $d$, которое не может быть в списке: его $k$-ю цифру после запятой возьмём отличной от $k$-й цифры $k$-го числа списка. Например, по правилу:

$$d_k = \begin{cases} 5, & \text{если } k\text{-я цифра } k\text{-го числа} \neq 5, \\ 6, & \text{иначе}. \end{cases}$$

Тогда $d$ отличается от первого числа в первой цифре, от второго — во второй, от $k$-го — в $k$-й. Значит, $d$ не совпадает ни с одним числом списка — но это вещественное число из $[0,1]$! Список оказался неполным, противоречие.

# Допустим, кто-то выписал такой "список" чисел из [0,1]
table = [
    "0.13579246...",
    "0.24680135...",
    "0.55555555...",
    "0.31415926...",
    "0.71828182...",
]

# Строим диагональное число, отличное от каждого
diag = "0."
for k, row in enumerate(table):
    digit = row[2 + k]   # k-я цифра после запятой
    diag += "6" if digit == "5" else "5"

print("Диагональные цифры берём по позициям:")
for k, row in enumerate(table):
    print(f"  число {k + 1}: {k}-я цифра = {row[2 + k]}")
print("Построенное число:", diag + "...")
print("Оно отличается от КАЖДОГО числа списка -> список неполон")

Вывод:

Диагональные цифры берём по позициям:
  число 1: 0-я цифра = 1
  число 2: 1-я цифра = 4
  число 3: 2-я цифра = 5
  число 4: 3-я цифра = 1
  число 5: 4-я цифра = 8
Построенное число: 0.55655...
Оно отличается от КАЖДОГО числа списка -> список неполон

Как работает под капотом

Гениальность в том, что какой бы список нам ни предъявили, мы всегда построим «беглеца», пройдя по диагонали и изменив каждую цифру. Третья цифра нашего числа — 6 (потому что у третьего числа на диагонали стояла 5), остальные — 5. Это гарантирует, что число отличается от $k$-го хотя бы в $k$-й позиции. Вывод: вещественных чисел «строго больше», чем натуральных, — их бесконечность несчётна. Так Кантор открыл, что бесконечности образуют целую иерархию: счётная (как у $\mathbb{N}$) — самая «маленькая», а у континуума $\mathbb{R}$ мощность больше.

Частые ошибки

Диагональное число должно отличаться так, чтобы избежать неоднозначности дробей (вроде $0{,}4999\ldots = 0{,}5$): поэтому выбирают цифры подальше от 0 и 9, например 5 и 6. Не думайте, что метод «нумерует» вещественные — наоборот, он доказывает невозможность нумерации. И помните: несчётность $\mathbb{R}$ не отменяет счётности $\mathbb{Q}$ — рациональные всё ещё счётны.

Итог

• Вещественные числа несчётны (теорема Кантора).
• Диагональный метод строит число вне любого списка.
• $k$-я цифра беглеца отличается от $k$-го числа.
• Бесконечности бывают разного размера: $|\mathbb{R}| \gt |\mathbb{N}|$.