Диагональный аргумент Кантора (Cantor's Diagonal Argument) - Доказательство того, что действительных чисел «подавляюще больше», чем рациональных

Введение: Бывают ли у бесконечности разные «размеры»?

Концепция «бесконечности», о которой мы думаем в повседневной жизни, в буквальном смысле означает «отсутствие конца». Натуральные числа ($1, 2, 3, \dots$) можно считать бесконечно долго, поэтому их количество бесконечно. С другой стороны, действительные числа (все точки на числовой прямой) также существуют в бесконечном количестве.

Интуитивно мы склонны думать, что «бесконечность есть бесконечность, и обе они одинаково безграничны», но математик 19 века Георг Кантор (Georg Cantor) доказал удивительный факт: «бесконечности имеют разную величину (мощность)» .

В этой статье мы подробно объясним, почему множество действительных чисел «подавляюще больше» множества натуральных чисел, используя диагональный аргумент (Diagonal Argument) — революционный метод доказательства, изобретенный Кантором.

Теория множеств Кантора и «Мощность» (Cardinality)

Кантор ввел концепцию мощности (Cardinality) для сравнения «количества» элементов в множествах. Для конечных множеств мощность — это просто количество элементов. Но как сравнить размеры бесконечных множеств?

Кантор использовал идею биекции (Bijection) . Он определил, что если между двумя множествами $A$ и $B$ можно установить взаимно-однозначное соответствие (биекцию), то эти два множества «имеют одинаковую мощность» .

Одинакова ли мощность натуральных и четных чисел?

Например, давайте рассмотрим множество натуральных чисел $\mathbb{N}$ и множество положительных четных чисел $E$.

$$ \mathbb{N} = \{1, 2, 3, 4, \dots\} $$$$ E = \{2, 4, 6, 8, \dots\} $$

Интуитивно кажется, что четных чисел существует ровно вполовину меньше, чем натуральных. Однако, используя функцию $f(n) = 2n$, мы можем создать идеальное взаимно-однозначное соответствие между натуральным числом $n$ и четным числом $2n$.

  graph LR
    subgraph "Натуральные числа (N)"
        N1("1")
        N2("2")
        N3("3")
        N4("4")
        Ndots("...")
    end
    
    subgraph "Четные числа (E)"
        E1("2")
        E2("4")
        E3("6")
        E4("8")
        Edots("...")
    end
    
    N1 -->|"f(n)=2n"| E1
    N2 -->|"f(n)=2n"| E2
    N3 -->|"f(n)=2n"| E3
    N4 -->|"f(n)=2n"| E4
    Ndots -->|"..."| Edots

Таким образом, бесконечные множества обладают странным свойством: «часть имеет тот же размер, что и целое». Бесконечное множество, которое можно поставить во взаимно-однозначное соответствие с натуральными числами, называется счетным (Countably infinite) или обладающим мощностью алеф-нуль ($\aleph_0$) .

Удивительно, но было доказано, что рациональные числа ($\mathbb{Q}$), которые можно представить в виде дробей, также имеют ту же мощность, что и натуральные числа (являются счетно-бесконечными).

Действительные числа «невозможно сосчитать»: Теорема Кантора

Натуральные числа, четные числа и рациональные числа — все их можно «пересчитать по порядку». Но можно ли установить взаимно-однозначное соответствие с натуральными числами для действительных чисел ($\mathbb{R}$) , которые представляют все точки на числовой прямой?

Ответ Кантора был «Нет» . Он показал, что действительные числа имеют строго бóльшую мощность, чем натуральные числа, то есть они несчетны (Uncountably infinite) .

В этом доказательстве использовался диагональный аргумент , который называют одним из самых красивых доказательств в истории математики.

Доказательство с помощью диагонального аргумента

Здесь мы рассмотрим не все действительные числа, а ограничимся только действительными числами от 0 до 1 (интервал $(0, 1)$). Если действительных чисел даже в этом интервале больше, чем натуральных чисел, то, разумеется, всех действительных чисел тоже больше, чем натуральных чисел.

Предположение для доказательства от противного

В доказательстве используется доказательство от противного (Proof by contradiction) . Сначала мы предполагаем, что «все действительные числа от 0 до 1 могут быть поставлены во взаимно-однозначное соответствие с натуральными числами (= могут быть перечислены в виде списка)».

Другими словами, мы предполагаем, что все действительные числа от 0 до 1 можно представить в виде бесконечных десятичных дробей и составить из них список: первое, второе и так далее, как показано ниже.

$$ r_1 = 0 . \mathbf{d_{11}} d_{12} d_{13} d_{14} \dots $$$$ r_2 = 0 . d_{21} \mathbf{d_{22}} d_{23} d_{24} \dots $$$$ r_3 = 0 . d_{31} d_{32} \mathbf{d_{33}} d_{34} \dots $$$$ \vdots $$

Здесь $d_{ij}$ представляет цифру (от 0 до 9) в $j$-м десятичном разряде $i$-го действительного числа.

Построение нового действительного числа $x$

Кантор показал способ создания нового действительного числа $x$, которого абсолютно точно нет в списке , из этого «списка, который, как предполагалось, охватывает все действительные числа».

$$ x = 0 . x_1 x_2 x_3 x_4 \dots $$

Цифра $x_n$ в каждом разряде определяется на основе $d_{nn}$ — цифры в $n$-м десятичном разряде $n$-го числа в списке (цифры на диагонали). Правило очень простое.

$$ x_n = \begin{cases} 1 & \text{если } d_{nn} \neq 1 \\ 2 & \text{если } d_{nn} = 1 \end{cases} $$

То есть, если цифра на диагонали $d_{nn}$ не равна 1, мы делаем $x_n$ равным 1, а если она равна 1, мы делаем ее равной 2. (※ Чтобы избежать проблемы периодических дробей с повторяющимися девятками, мы используем только 1 и 2)

  graph TD
    %% "Процесс инверсии диагональных элементов"
    subgraph "Диагональные компоненты списка"
        D1("d_11")
        D2("d_22")
        D3("d_33")
    end
    
    subgraph "Компоненты нового действительного числа x"
        X1("x_1 ≠ d_11")
        X2("x_2 ≠ d_22")
        X3("x_3 ≠ d_33")
    end
    
    D1 -->|"Применить правило"| X1
    D2 -->|"Применить правило"| X2
    D3 -->|"Применить правило"| X3

Вывод противоречия

Построенное новое действительное число $x$ является действительным числом от 0 до 1. Согласно нашему предположению, в списке должны быть представлены «все действительные числа от 0 до 1», поэтому $x$ также должно находиться где-то в списке, например, на $k$-м месте ($r_k$).

Если $x = r_k$, то цифра $k$-го десятичного разряда $x_k$ числа $x$ должна быть равна цифре $k$-го десятичного разряда $d_{kk}$ числа $r_k$ ($x_k = d_{kk}$).

Однако, согласно определению $x$, $x_k$ намеренно создано так, чтобы оно было цифрой, отличной от $d_{kk}$ ($x_k \neq d_{kk}$) .

Это противоречие. Следовательно, первоначальное предположение о том, что «все действительные числа можно внести в список», было неверным.

В заключение было доказано, что множество действительных чисел нельзя поставить во взаимно-однозначное соответствие со множеством натуральных чисел, и действительных чисел «подавляюще больше» (их мощность строго больше) .

Путь к континуум-гипотезе (Continuum Hypothesis)

Диагональный аргумент Кантора показал, что внутри бесконечности существует «иерархия». Если мощность натуральных чисел обозначить как $\aleph_0$, а мощность действительных чисел как $\aleph_1$ или $2^{\aleph_0}$, то выполняется следующее соотношение:

$$ \aleph_0 < 2^{\aleph_0} $$

Здесь Кантор столкнулся с одним колоссальным вопросом: «Существует ли бесконечное множество с мощностью, промежуточной между $\aleph_0$ и $2^{\aleph_0}$?»

Гипотеза о том, что «промежуточной мощности не существует», называется континуум-гипотезой (Continuum Hypothesis, CH) . Кантор посвятил доказательству этого всю свою жизнь, но так и не смог его решить.

Позже Курт Гёдель (Kurt Gödel) и Пол Коэн (Paul Cohen) доказали, что континуум-гипотеза «не может быть ни доказана, ни опровергнута (независима) в современной системе аксиом математики (ZFC)» . Это одно из самых глубоких открытий в математике 20 века.

Заключение

Диагональный аргумент Кантора на первый взгляд кажется простой головоломкой, но за ним скрывается мощная логика, приближающаяся к «истине бесконечности».

Размеры бесконечных множеств можно сравнивать с помощью «взаимно-однозначного соответствия».
Рациональные числа имеют тот же размер, что и натуральные числа (счетная бесконечность).
Используя аргумент о создании нового числа путем сдвига диагонали, доказывается, что действительных чисел больше, чем натуральных (несчетная бесконечность).

Красота этой интуитивно непонятной, но абсолютно неоспоримой логики, пожалуй, и есть величайшая привлекательность науки математики. Диагональный аргумент впоследствии будет применен к теориям, составляющим основу информатики и математической логики, таким как проблема остановки Алана Тьюринга (Alan Turing) и доказательство теорем о неполноте Гёделя.