Диагональный аргумент Кантора¶
Диагональный аргумент Кантора — это математический метод доказательства, разработанный Георгом Кантором в 1891 году, который демонстрирует, что множество действительных чисел (континуум) является несчётным, то есть его мощность строго больше мощности множества натуральных чисел. Этот аргумент стал одним из фундаментальных результатов в теории множеств и теории вычислимости, показав существование бесконечностей разных размеров.
¶История возникновения
Георг Кантор, немецкий математик, в 1870-х годах начал систематическое исследование бесконечных множеств. В 1874 году он опубликовал первую работу, доказывающую несчётность действительных чисел, используя более сложный метод, основанный на свойствах последовательностей. Однако в 1891 году Кантор предложил элегантное и простое доказательство, которое получило название «диагональный аргумент» из-за способа построения противоречия — по диагонали таблицы.
Диагональный аргумент был опубликован в статье «Über eine elementare Frage der Mannigfaltigkeitslehre» (Об одном элементарном вопросе учения о многообразиях). Этот метод впоследствии стал широко применяться в различных областях математики и логики, включая теорию вычислимости, теорию алгоритмов и математическую логику.
¶Суть аргумента
Диагональный аргумент Кантора доказывает, что не существует взаимно однозначного соответствия (биекции) между множеством натуральных чисел и множеством действительных чисел на отрезке [0,1]. Доказательство проводится от противного.
¶Основная идея
Предположим, что множество действительных чисел на отрезке [0,1] счётно. Это означает, что все эти числа можно выписать в бесконечную последовательность: r1, r2, r3, …, rn, … . Каждое действительное число можно представить в виде бесконечной десятичной дроби (например, 0,12345…). Для удобства доказательства используется представление в двоичной системе счисления или в десятичной с исключением чисел, имеющих конечное представление (например, 0,5000… вместо 0,4999…).
¶Построение диагонального числа
Пусть все числа rn записаны в виде десятичных дробей:
r1 = 0, a11 a12 a13 a14 … r2 = 0, a21 a22 a23 a24 … r3 = 0, a31 a32 a33 a34 … … rn = 0, an1 an2 an3 an4 … …
Здесь aij — цифры от 0 до 9. Теперь построим новое число d, которое не входит в этот список. Цифра d на позиции i (после запятой) выбирается так, чтобы она отличалась от aii (диагонального элемента). Например, если aii = 5, то берём 6; если aii = 6, то берём 5. Таким образом, d = 0, d1 d2 d3 …, где di ≠ aii для всех i.
¶Противоречие
Число d является действительным числом на отрезке [0,1]. По предположению, оно должно быть равно какому-то rk в исходном списке. Но по построению d отличается от rk в k-м разряде (после запятой). Следовательно, d не может быть равно ни одному из чисел списка. Полученное противоречие означает, что исходное предположение о счётности множества действительных чисел на отрезке [0,1] ложно. Таким образом, это множество несчётно.
¶Обобщения и варианты
Диагональный аргумент Кантора имеет несколько важных обобщений и вариантов, применяемых в разных областях математики.
¶Теорема Кантора о мощности множества подмножеств
Кантор также использовал диагональный аргумент для доказательства того, что мощность множества всех подмножеств любого множества A (обозначается как 2^A) строго больше мощности самого A. Доказательство строится аналогично: предполагается существование биекции f: A → 2^A, а затем строится множество B = {x ∈ A | x ∉ f(x)}, которое не может быть образом никакого элемента из A.
¶Диагональный аргумент в теории вычислимости
В теории алгоритмов диагональный аргумент применяется для доказательства неразрешимости некоторых проблем. Например, с его помощью доказывается неразрешимость проблемы остановки (halting problem) для машин Тьюринга. Алан Тьюринг в 1936 году использовал диагональный аргумент, чтобы показать, что не существует алгоритма, который бы для любой программы и входных данных определял, завершится ли она.
¶Диагональный аргумент в теории чисел
В теории чисел диагональный аргумент используется для доказательства существования трансцендентных чисел. Например, Лиувилль в 1844 году построил первое трансцендентное число, используя похожий метод, но Кантор показал, что множество алгебраических чисел счётно, а множество действительных чисел несчётно, следовательно, существуют трансцендентные числа (и их «большинство»).
¶Критика и философские аспекты
Диагональный аргумент Кантора вызвал значительные споры среди математиков и философов конца XIX — начала XX века.
¶Интуиционизм и конструктивизм
Представители интуиционизма (например, Л. Э. Я. Брауэр) и конструктивизма критиковали диагональный аргумент за использование актуальной бесконечности и неконструктивного построения. Они утверждали, что доказательство существования несчётных множеств не даёт способа явно построить такое множество, и что понятие «всех» действительных чисел не имеет конструктивного смысла. В конструктивистской математике диагональный аргумент принимается, но интерпретируется как доказательство того, что не существует эффективного перечисления действительных чисел.
¶Парадокс Рассела
Диагональный аргумент Кантора послужил прообразом для парадокса Рассела (1901), который выявил противоречие в наивной теории множеств. Рассел рассмотрел множество всех множеств, не содержащих себя в качестве элемента, и показал, что это приводит к логическому противоречию. Этот парадокс стимулировал развитие аксиоматической теории множеств (Цермело-Френкеля, фон Неймана-Бернайса-Гёделя).
¶Континуум-гипотеза
Диагональный аргумент показал, что существует бесконечность разных размеров: счётная (алеф-0) и континуум (c). Кантор сформулировал континуум-гипотезу: не существует множества, мощность которого строго между мощностью натуральных чисел и мощностью континуума. Эта гипотеза была доказана как независимая от аксиом ZFC (Цермело-Френкеля с аксиомой выбора) в работах Курта Гёделя (1940) и Пауля Коэна (1963).
¶Применение в современной математике
Диагональный аргумент Кантора является одним из основных инструментов в современной математике:
- Теория множеств: доказательство несчётности континуума, теорема Кантора о мощности множества подмножеств.
- Теория вычислимости: доказательство неразрешимости проблемы остановки, теорема Райса, теорема о неполноте (Гёдель использовал диагонализацию).
- Теория чисел: доказательство существования трансцендентных чисел.
- Функциональный анализ: доказательство неполноты некоторых пространств функций.
- Логика: доказательство неразрешимости логики первого порядка.
¶Интересные факты
- Диагональный аргумент Кантора был опубликован в 1891 году, но сам Кантор использовал более сложное доказательство несчётности ещё в 1874 году.
- Аргумент не зависит от выбора системы счисления: он работает как в десятичной, так и в двоичной системе, но в двоичной требуется осторожность из-за чисел с двумя представлениями (например, 0,0111… = 0,1000…).
- Диагональный аргумент часто называют «диагонализацией» и используют в различных контекстах, от теории игр до квантовой механики.
- В 2015 году математик Джоэл Дэвид Хэмкинс показал, что диагональный аргумент можно применить к любому бесконечному множеству, не обязательно счётному, для доказательства существования множества большей мощности.
¶Источники
- Кантор Г. «Über eine elementare Frage der Mannigfaltigkeitslehre» (1891)
- Курант Р., Роббинс Г. «Что такое математика?» (1941)
- Успенский В. А. «Теорема Гёделя о неполноте» (1982)
- Эндертон Г. «Элементы теории множеств» (1977)
- Тьюринг А. «On Computable Numbers, with an Application to the Entscheidungsproblem» (1936)