Диагональный аргумент Кантора: почему вещественные числа нельзя перечислить
Представьте, что вам вручают список. Он бесконечный, и тот, кто его составил, утверждает: в нём содержится каждое вещественное число между 0 и 1. Не выборка, не подборка: каждое единственное число, аккуратно пронумерованное как r1, r2, r3, и так далее, уходя в бесконечность.
Ответ Георга Кантора в 1891 году был таков: какой бы список вы мне ни принесли, я могу назвать число, которого в нём нет. Описание конструкции занимает около тридцати секунд. Осмысление следствий заняло у математиков десятилетия, потому что оно означает: бесконечность бывает более чем одного размера.
Счёт и перечисление
Прежде чем перейти к диагональному ходу, стоит уточнить, что именно означает «счётный». Множество счётно, если каждому его элементу можно назначить уникальный натуральный номер: первый элемент, второй, третий, и так далее, не оставив ничего. Натуральные числа счётны по определению. Целые числа тоже (перечислим их как 0, 1, -1, 2, -2, ...) и даже рациональные, хотя перечисление каждой дроби требует хитрого зигзагообразного обхода.
Аргумент Кантора показывает, что вещественные числа между 0 и 1 подлинно иные: никакой нумерации не существует, как бы вы ни старались. Это не провал воображения. Это доказательство того, что задача невозможна.
Допустим, список существует
Аргумент является доказательством от противного. Начнём с того, что дадим оппоненту всё, что он хочет: предположим, что полный список каждого вещественного числа в (0, 1) действительно существует. Запишем каждое число в виде бесконечного десятичного разложения.
Список может начинаться примерно так:
- r1 = 0,14159265...
- r2 = 0,73205080...
- r3 = 0,00000000...
- r4 = 0,27182818...
- r5 = 0,91415926...
- ...
Каждый элемент уходит в бесконечность. Список уходит в бесконечность. И по нашему предположению каждое вещественное число между 0 и 1 присутствует где-то в нём.
Теперь посмотрим, что происходит, когда вы читаете по диагонали.
Читаем диагональ
Возьмите первую десятичную цифру числа r1, вторую десятичную цифру числа r2, третью числа r3 и так далее. В примере выше эти диагональные цифры: 1, 3, 0, 2, 9, ...
Теперь построим новое число d, цифра за цифрой. Правило: для каждой диагональной цифры выбирайте другую цифру, специально избегая 0 и 9.
| r₁ | 0 | . | 1 | 4 | 1 | 5 | 9 | |
| r₂ | 0 | . | 3 | 3 | 3 | 3 | 3 | |
| r₃ | 0 | . | 5 | 0 | 0 | 0 | 0 | |
| r₄ | 0 | . | 7 | 1 | 8 | 2 | 8 | |
| r₅ | 0 | . | 6 | 0 | 2 | 5 | 9 | |
| new | 0 | . | 2 | 4 | 1 | 3 | 8 | … |
Each highlighted digit sits on the diagonal. The new number changes every one of them (1 3 0 2 9 becomes 2 4 1 3 8), so it cannot equal any row in the list.
Диагональные цифры: 1, 3, 0, 2, 9. Применяя правило, получаем 2, 4, 1, 3, 8. Значит, d = 0,24138...
Избегание 0 и 9 это небольшая, но необходимая защита. Некоторые вещественные числа имеют два десятичных представления: 0,4999... и 0,5000... обозначают одну и ту же точку на числовой оси. Изменив цифру на 0 или 9, можно попасть на «второе имя» числа, уже присутствующего в списке, что замутило бы аргумент. Оставаясь в диапазоне от 1 до 8 для каждой изменённой цифры, мы гарантируем, что у числа d ровно одно десятичное разложение, и сравнение ниже остаётся чистым.
Новое число отличается от каждого элемента списка
Вот итог.
d отличается от r1 в первом десятичном знаке
Первая цифра числа d была выбрана так, чтобы отличаться от первой цифры r1. Значит, d не равно r1. Они различаются в позиции 1.
d отличается от r2 во втором десятичном знаке
Вторая цифра числа d была выбрана так, чтобы отличаться от второй цифры r2. Значит, d не равно r2. Они различаются в позиции 2.
d отличается от rn в n-м десятичном знаке, для любого n
По построению n-я цифра числа d отличается от n-й цифры числа rn. Поскольку два числа, различающиеся хотя бы в одной позиции, не равны, d не равно rn ни для какого n.
В этом и состоит диагональный ход: d был специально построен так, чтобы конфликтовать с каждым элементом списка в том единственном месте, где каждый элемент наиболее уязвим, в его собственной диагональной позиции.
d является вещественным числом между 0 и 1, но его нет в списке
Число d = 0,24138... явно является вещественным числом из интервала (0, 1). Но мы только что показали, что оно отличается от r1, от r2, от r3, от каждого элемента. Если бы список был полным, d должно было бы где-то в нём появиться. Его там нет. Значит, список неполный.
Противоречие острое: мы предположили, что список полный, и при этом получили вещественное число, которого в нём нет. Предположение неверно. Никакого полного списка вещественных чисел между 0 и 1 не существует.
Что это на самом деле означает
Математики говорят, что натуральные числа имеют мощность алеф-ноль (записывается с помощью еврейской буквы алеф: первый трансфинитный кардинал). Вещественные числа имеют строго большую мощность, которую иногда записывают как c или как 2 в степени алеф-ноль. Аргумент Кантора именно то, что устанавливает: эти две бесконечности не одного размера.
Это вызвало острые споры, когда Кантор опубликовал результат. Некоторые коллеги отмахивались от него как от курьёза или ошибки. Это ни то ни другое. Он лежит в основании того, как математики думают о множествах, мощности и структуре числовой прямой, и напрямую связан с вопросами о том, что можно и что нельзя вычислить (см. также доказательство в теореме Гудстина, где нечто доказуемо истинное упирается в пределы формальных систем).
Почему диагональ работает
Элегантность аргумента в его конкретности. Вы не угадываете отсутствующее число и не апеллируете к расплывчатой интуиции о том, насколько велики вещественные числа. Вы точно считываете, какие позиции в списке контролирует каждый элемент, и затем строите число, которое ускользает от каждого элемента ровно в этой позиции.
Сам список говорит вам, куда смотреть. Каждый элемент списка передаёт вам одну координату, свою собственную диагональную цифру, а конструкция превращает эти координаты в число, которое список не может содержать.
Простота здесь обманчива. Ничто в этом аргументе не требует знания того, что именно стоит в списке. Не важно, какие числа в нём, в каком порядке и как они выбраны. Аргумент универсален: возьмите любой список вещественных чисел, и диагональная конструкция найдёт вещественное число, которого в этом списке нет.
Дзен этого
Диагональный аргумент Кантора стоит в длинной традиции математических результатов, которые кажутся невозможными. Вы смотрите на доказательство и ждёте трюка, скрытого допущения, места, где логика скользит. Его нет. Доказательство ровно столь же просто, сколь оно выглядит.
Что оно просит вас принять, странее самого доказательства: что «бесконечный» не является единственным пунктом назначения. Целые числа и вещественные числа оба бесконечны, но они бесконечны принципиально разными способами. Диагональный аргумент и есть разделительная черта.
Для более глубокого ощущения того, как бесконечные объекты могут вести себя странно, стоит следующим обратиться к бесконечным десятичным дробям или к тому, как работают пределы, когда последовательности вечно приближаются к значению, не достигая его. Диагональный аргумент принадлежит той же семье: точный, терпеливый взгляд на то, что происходит на краю бесконечного, где интуиции нужно доказательство, чтобы оставаться честной.
Бесконечность не одна. Вот и новость. Аргумент, который её доносит, умещается на полстраницы.
Частые вопросы
- Что доказывает диагональный аргумент Кантора?
- Он доказывает, что вещественные числа между 0 и 1 несчётны: ни один список, каким бы искусным образом он ни был составлен, не может содержать каждое вещественное число из этого интервала. Вещественных чисел попросту больше, чем позиций в любом списке.
- Что означает «несчётный»?
- Множество счётно, если можно сопоставить каждому его элементу натуральное число (1, 2, 3, ...) так, чтобы ничего не осталось за бортом. Натуральные числа, целые числа и даже рациональные числа счётны. Вещественные числа нет: их слишком много, чтобы установить подобное взаимно однозначное соответствие.
- Почему нельзя просто добавить пропущенное число в список?
- Можно, но тогда диагональный аргумент применяется снова к новому, более длинному списку и находит очередное отсутствующее число. Аргумент работает для любого списка, сколь угодно длинного или хитроумно устроенного, так что залатать список до полноты не получится.
- Почему при изменении цифр нужно избегать 0 и 9?
- Некоторые вещественные числа имеют два десятичных представления: 0,4999... и 0,5000... это одно и то же число. Если изменить цифру на 0 или 9, можно случайно попасть на «второе имя» числа, уже присутствующего в списке. Избегание 0 и 9 обходит эту техническую тонкость и сохраняет доказательство чистым.
- Рациональные числа тоже несчётны?
- Нет. Рациональные числа счётны: можно систематически перечислить каждую дробь p/q и присвоить ей натуральный номер, не пропустив ничего. Диагональный аргумент Кантора направлен против вещественных чисел, а не рациональных.
Понравилось разбираться?
Math Zen превращает такую интуицию в ежедневную практику: адаптивные задачи по 24 темам математики.
