Многие научные теории постулированы в результате философских размышлений и дискуссий над парадоксальными вопросами. Таких вопросов с самых древнейших времен накопилось огромное количество, и многие из них без дополнительных условий действительно являются парадоксальными. Некоторые из них привели к серьезным научным открытиям.
Достоверно неизвестно, когда именно появилась такая категория человеческого мышления как бесконечность, но уже в дошедших до нас сочинениях Древнего мира имеются упоминания этого термина. Однако большая часть современных представлений базируется на открытиях интересных аспектов бесконечности, впервые обнаруженных в 19 веке, благодаря новаторским работам Георга Кантора. Многие его открытия намного опережали своё время. Одним из них было определение строгого способа сравнения различных бесконечных множеств, в результате которого он неожиданно обнаружил, что одни бесконечности больше других.
В то время теория Кантора вызвала не просто возмущение, а агрессивное сопротивление. Анри Пуанкаре, один из ведущих математиков того времени, назвал это «канторовской болезнью». Однако некоторые математики, в том числе Давид Гильберт, увидели в этом опередившее свое время открытие.
Цель статьи в том, чтобы достаточно просто рассказать об этом открытии. Сегодня не будет сложных формул или зубодробительных формулировок. Вместо этого попробуем следовать подходу, предложенному самим Гильбертом. Странность и чудо теории Кантора отлично описывается мысленным экспериментом, иллюстрирующим парадоксальную природу реальных бесконечностей, ныне известном как «Парадокс Гильберта о Гранд‑отеле». Формулировка парадокса очень проста:
Отель Hilbert всегда забронирован, но в нём всегда есть свободные места.
По условиям эксперимента в отеле не просто сотни номеров — их актуальная бесконечность. К тому же довольно странная система размещения гостей. Всякий раз, когда прибывает новый гость, администратор «сдвигает» всех уже заселившихся в отель людей, т. е. переводит обитателя номера 1 в номер 2, номера 2 в номер 3 и так далее, таким образом освобождая первый номер для новичка.
Теперь предположим, что к ресепшену прибывает бесконечно много новых уставших и раздражительных гостей. Ну что же, без проблем. Невозмутимый администратор переводит обитателя номера 1 в номер 2, номера 2 в номер 4, номера 3 в номер 6 и так далее. Такой трюк с удвоением освобождает все нечётные номера, а так как их бесконечно много — все новые гости с успехом размещаются.
Позже и, возможно, той же ночью к парадному входу отеля подъезжает бесконечная колонна туристических автобусов. Автобусов бесконечно много, и каждый из них плотненько набит бесконечным количеством ещё более уставших и раздражительных людей, требующих, чтобы отель соответствовал своему правилу: деятельность на территории Континенталя запрещена «В отеле Hilbert всегда есть места».
Администратор сталкивался с этой проблемой раньше и принимает её совершенно спокойно. Для этого он использует второй трюк, переселяющий текущих гостей в номера с чётными номерами. Все номера с нечётными номерами убраны и готовы к заселению гостей — хорошее начало, потому что теперь у него опять бесконечное количество доступных номеров. Но достаточно ли этого? Действительно ли достаточно нечётных номеров, чтобы вместить такое количество новых гостей? На первый взгляд кажется маловероятным, поскольку есть что‑то вроде «бесконечности в квадрате» людей, требующих размещения (в каждом из бесконечного числа автобусов — бесконечное количество людей).
Вот здесь логика бесконечности становится немного странной. Чтобы понять, как администратор собирается решить проблему, полезно визуализировать людей, которых он должен обслужить, в некое подобие матрицы.
Конечно, нельзя показать буквально всех посетителей, однако идеальная версия картины понятна. Дело в том, что любой конкретный пассажир автобуса обязательно появится где-нибудь на рисунке, если мы включим достаточное количество строк и столбцов матрицы. В этом смысле учитываются все в каждом автобусе. Вы называете пассажира, и он наверняка будет изображён на некотором конечном числе шагов от левого верхнего угла матрицы.
Задача администратора состоит в том, чтобы найти способ систематически работать с этой матрицей. Ему нужно разработать схему распределения номеров таким образом, чтобы каждый в конце концов получил ключ от номера, после того, как будет обслужено конечное число других людей.
К сожалению, в определённый момент отсутствия администратора, когда появился аналогичный поток гостей, воцарился хаос. Персонал гостиницы, пытаясь линейно обслужить всех людей в первом автобусе, так и не смог добраться до следующего автобуса. Такая стратегия распределения неверна и показана ниже.
Однако когда вернулся администратор, порядок был восстановлен. Вместо того чтобы заниматься только одним автобусом, он зигзагом ходит по матрице, начав с обслуживания первого пассажира первого автобуса.
Первый пассажир первого автобуса получает ключи от первого свободного номера. Второй пустой номер достаётся второму пассажиру в первом автобусе, за которым последует первый пассажир второго автобуса. Оба изображены на второй диагонали от угла матрицы. Обслужив их, администратор переходит к третьей диагонали и выдаёт набор ключей от номера первому пассажиру третьего автобуса, второму пассажиру второго автобуса и третьему пассажиру первого автобуса. Таким образом, алгоритм действий администратора позволяет обслужить любого конкретного пассажира за конечное число шагов.
Аргумент, который я только что представил, известен в теории бесконечных множеств, основоположником которой и является Георг Кантор. Он использовал его, чтобы доказать, что положительных дробей (отношений A/B целых положительных чисел A и B) ровно столько, сколько натуральных чисел (1, 2, 3, 4, …). А это гораздо более сильное утверждение, чем утверждение, что оба множества бесконечны. То есть между ними может быть установлено однозначное соответствие.
Это соответствие можно представить как парную систему, в которой каждое натуральное число сочетается с некоторой положительной дробью, и наоборот. Существование такой системы кажется совершенно несовместимым со здравым смыслом и напоминает софизм. Вот эта кажущаяся логическая ошибка и заставила Пуанкаре и многих других корифеев науки крайне отрицательно отнестись к теории Кантора. Ведь это бы значило, что можно составить исчерпывающий список всех положительных дробей, даже если наименьшей из них не существует.
Такое кажется немыслимым, но такой список уже есть. Если дробь A/B соотнести с пассажиром A в автобусе B, то список размещения гостей и будет этим списком. Каждой из дробей можно поставить в пару некоторое натуральное число, заданное гостиничным номером пассажира в отеле Hilbert. Такой вот математический парадокс о бесконечных множествах, предполагающий гостиницу с актуальной бесконечностью номеров.
Притча наглядно иллюстрирует, что утверждение «все комнаты заняты» вовсе не означает, что «больше нет места для новых гостей». Это действительно странно, хотя, строго говоря, не является парадоксом в логическом смысле. Однако это настолько противоречит обычному житейскому смыслу и заставляет предполагать, что исчисляемые фактические бесконечности не принадлежат реальному миру, в котором мы живем.
Kontrollschuss или Coup de Grace
Кантор доказал, что некоторые бесконечные множества больше, чем другие. В частности, множество вещественных чисел от 0 до 1 несчётно, и его нельзя поставить во взаимно однозначное соответствие с натуральными числами. Для гостиничного бизнеса это означает, что если бы все эти числа (гости) появились на стойке регистрации, то мест на всех не хватило бы, даже в таком грандиозном отеле, как Hilbert.
Доказательство от противного. Предположим, что каждому вещественному числу может быть отведён отдельный номер. Тогда список постояльцев, идентифицированный их десятичными разложениями и перечисленный по номеру комнаты, будет выглядеть примерно так:
№ комнаты |
Постоялец |
1 |
0.9879615875… |
2 |
0.1235765925… |
3 |
0.7647915602… |
4 |
0.5432189852… |
... |
Предполагается, что каждое действительное число от 0 до 1 появляется где-то, в каком-то конечном месте списка.
Кантор показал, что многие числа отсутствуют в любом таком списке, а это серьёзное противоречие. Например, чтобы составить число, которого нет нигде в приведенном списке, пройдите по диагонали и составьте новое число из цифр, выделенных жирным шрифтом:
№ комнаты |
Постоялец |
1 |
0.9879615875… |
2 |
0.1235765925… |
3 |
0.7647915602… |
4 |
0.5432189852… |
… |
Сгенерированное таким образом десятичное число равно 0.9242…
Следующий шаг — взять эту десятичную дробь и изменить все её цифры, заменив каждую из них любой другой цифрой от 1 до 8. Например, можно изменить 9 на 6, 2 на 4, 4 на 5, а 2 на 8, и так далее. Этот новый посетитель 0.6458… просто «убийца» системы. Его точно нет в первом номере, так как у него другая цифра в первом десятичном разряде. Также он не может находиться во втором номере и т.д. В общем случае оно отличается от любого i-го числа в j-м десятичном разряде. «Его нет в списке администратора, КАРАУЛ! Дайте жалобную книгу!» Следовательно, напрашивается вывод, что отель не может вместить всех гостей, обозначенных действительными числами {0, 1}. Их просто намного больше.
С 1970-х годов отель Hilbert использовался в самых различных областях науки. Долгое время оставалось неизвестным, правда ли Давид Гильберт предложил этот мысленный эксперимент или это просто математический фольклор. Оказалось, что Гильберт действительно представил свой отель в Гёттингене в неопубликованных лекциях зимнего семестра 1924-1925 гг. Эти лекции были опубликованы только в 2013 году.
Гильберт воспользовался случаем, чтобы превознести достоинства канторовской теории множеств, отметив, что Кронекер сделал все возможное для борьбы с ней. «Когда я был приват-доцентом, — говорил он, — к тем, кто верил в Кантора, относились с презрением. Даже сегодня выдающиеся математики продолжают сопротивляться теории Кантора».
Противоречивый отель стал более известен только в 1947 году, после публикации Георгием Гамовым своей книги «Раз, два, три… бесконечность» (One, Two, Three, ..., Infinity). Потребовалось еще почти три десятилетия, прежде чем этот мысленный эксперимент вызвал широкий интерес в научных и философских контекстах.
НЛО прилетело и оставило здесь промокод для читателей нашего блога:
— 15% на все тарифы VDS (кроме тарифа Прогрев) — HABRFIRSTVDS.
Комментарии (44)
maximw
00.00.0000 00:00+1Помню, в универе это сначало слегка взрывало мозг, а потом удивляло красотой.
Алеф0 - мощность множества натуральных чисел. Или множества конечномерных векторов с натуральными значениями.
Алеф1 - мощность множества вещественных чисел. Или множества конечномерных векторов с вещественными значениями.
Не читал про алеф2, но думал что бы это могло быть. И придумал, что это либо мощность множества бесконечномерных векторов с натуральными значениями (но не факт, что это не алеф1), либо мощность множества бесконечномерных векторов с вещественными значениями.
Alexandroppolus
00.00.0000 00:00алеф2 вроде бы множество всех возможных функций от вещественных аргументов, хотя точно сказать не могу
victor_1212
00.00.0000 00:00+3алеф (N+1) грубо говоря множество всех подмножеств алеф N,
более точно см. https://en.wikipedia.org/wiki/Successor_cardinal
к сожалению практически все что написано в статье про Пуанкаре не соответствует действительности, на самом деле его идеи по поводу бесконечности были ближе к работам Геделя, типа формальные системы подобные построениям Кантора не являются логически полными, что и было доказано позже,
ps
основная логическая проблема - могут ли аксиомы вообще использовать понятие бесконечности
Sergey_Kovalenko
00.00.0000 00:00+2Предположение о равенстве мощностей множества всех действительных чисел и множества всех подмножеств натурального ряда называют "Континуум гипотезой". Ходит байка, что Кантор сошел с ума пытаясь ее доказать. Позже, когда были формализованы некоторые подходы к определению понятия множества Гильберту и Коэну удалось доказать, что Континуум гипотеза независима от остальных аксиом типичных теорий множеств, т.е внутри этих теорий ее нельзя ни доказать, ни опровергнуть.
Аксиомам совсем не обязательно оперировать понятием бесконечности, чтобы ее подразумевать. Например для системы аксиом
1.для всяк. x сущ. y т.ч. y=x+1
2.сущ. x т.ч. x != (x+1)
3. для всяк. x: x+1>x.
4.для всяк x, y: если x>y, то x+1 > y
всякое множество, которое наделено отношениями =, > и отображением +, может удовлетворять 1.-4. только если оно бесконечно.Sergey_Kovalenko
00.00.0000 00:00надо добавить
5. для всяк. x, y если x>y, то x!=y.
без 5 аксиомам 1-4 удовлетворяет, например, множество остатков от деления целых чисел, скажем, на 3, где +1 - это прибавление по модулю 3, а отношение > истинно для всех пар элементов.
victor_1212
00.00.0000 00:00+1> Аксиомам совсем не обязательно оперировать понятием бесконечности
если говорить об аргументации Пуанкаре и др. в отношении работ Кантора, то имелось ввиду несколько иное, предположим система не полна, и принципиально не может быть полной, упрощенно это означает, что для ее описания необходимо бесконечно много аксиом, какой смысл для нас живя в конечном мире может быть в исследовании такой системы, если даже ее описание не помещается в нашей вселенной, см. Henri Poincaré, Science and Method -
"... For my part I think, and I am not alone in so thinking, that the important thing is never to introduce any entities but such as can be completely defined in a finite number of words .... "
shuhray
00.00.0000 00:00+3Совсем не так, равенство мощностей множества всех действительных чисел и множества всех подмножеств натурального ряда доказывается легко. Смотрите мой комментарий чуть ниже за правильной формулировкой (вопрос сложный, ошибку делают часто).
Sergey_Kovalenko
00.00.0000 00:00+1Да, вы конечно же правы. Континуум гипотеза - это вопрос о равенстве именно первой несчетной мощности и множества всех действительных чисел. Видите, моя память за древностию лет сделала "ошибку Кантора". Конечно двоичная дробь вида 0,10110... кодирует по правилу "взять - не взять" некоторое подмножество натурального ряда и наоборот, поэтому множество действительных чисел интервала (0,1) равномощно множеству всех подмножеств на натуральных чисел.
wormball
00.00.0000 00:00> алеф (N+1) грубо говоря множество всех подмножеств алеф N,
нет ru.wikipedia.org/wiki/Бет-число
CaptainFlint
00.00.0000 00:00Гораздо интереснее вопрос, а есть ли промежуточные мощности между алеф0 и алеф1. :)
shuhray
00.00.0000 00:00+1Не совсем так. Мощность множества вещественных чисел - это два в степени алеф0, она же мощность множества подмножеств натурального ряда. А алеф1 - это самая маленькая несчётная мощность (его можно описать содержательнее, но надо знать, что такое "ординал", это мощность множества всех счётных ординалов). Равны ли алеф1 и два в степени алеф0 или алеф1 строго меньше - сложный вопрос (континуум-гипотеза утверждает, что равны, Кантор спятил, пытаясь её доказать).
wormball
00.00.0000 00:00> Алеф1 — мощность множества вещественных чисел
не обязательно ru.wikipedia.org/wiki/Континуум-гипотеза
nin-jin
00.00.0000 00:00-1Гильберт воспользовался случаем, чтобы превознести достоинства канторовской теории множеств, отметив, что Кронекер сделал все возможное для борьбы с ней. «Когда я был приват-доцентом, — говорил он, — к тем, кто верил в Кантора, относились с презрением. Даже сегодня выдающиеся математики продолжают сопротивляться теории Кантора».
amkartashov
00.00.0000 00:00+1Зачем давать ссылку на статью, автор которой не осилил даже нормально формулировку теоремы Гёделя о неполноте понять? Цитирую:
... первую теорему Гёделя о неполноте. Суть её сводится к тому, что в любой непротиворечивой системе утверждений существует такое правдивое утверждение, которое невозможно доказать
Вообще-то её суть сводится к тому, что в для любой непротиворечивой системы утверждений (аксиом) всегда найдётся утверждение, которое нельзя ни доказать, ни опровергнуть (ещё одна аксиома).
nin-jin
00.00.0000 00:00-2amkartashov
00.00.0000 00:00+1И дальше что? Отношение же, а не эквивалентность. Дальнейшее общение в виде тоже в виде ссылок будет?
jasiejames
00.00.0000 00:00-1Преклонение перед авторитетами в его самом характерном для современности виде, что тут поделаешь?
amkartashov
00.00.0000 00:00+2Сейчас я вижу ошибку в своём комментарии, но уже не могу поправить. Тем не менее, https://page.hyoo.ru/#!=ixy44o_3oga48 - чел лезет со своим бытовым пониманием и наивными рассуждениями. При этом допускает логические прорехи, достойные шизофреника.
Для обоснования приводится выражение вида "это выражение невозможно доказать"
Нет. Там всё сложнее, чем доказательство через рекурсивное высказывание.
Также умиляет опровержение доказательства теоремы Кантора о несчётности вещественных чисел:
доказательство Кантора выглядит так: ... нарушили один из основных принципов доказательства от противного
Не все доказательства этой теоремы Кантора являются доказательством от противного.
введём в рассмотрение Санту - некоторое вещественное число, которое по построению не соответствует ни одному натуральному. А в рамках исходной гипотезы, в которой мы не сомневаемся, пока она не опровергнута, его определение эквивалентно следующему: "Санта - это такое вещественное число, которое не равно.. никакому вещественному числу".
непонятно, как от "не соответствует ни одному натуральному" автор перепрыгнул к "не равно.. никакому вещественному числу"
nin-jin
00.00.0000 00:00-2Там всё сложнее
Просто пыль в глаза.
доказательство через рекурсивное высказывание.
Через самоотрицание. Проблема не в рекурсии самой по себе.
Не все доказательства этой теоремы Кантора являются доказательством от противного.
Спасибо за ссылку.
непонятно, как от "не соответствует ни одному натуральному" автор перепрыгнул к "не равно.. никакому вещественному числу"
Исходная гипотеза: "любому вещественному числу соответствует натуральное".
amkartashov
00.00.0000 00:00+2я посмотрел на твой блог, там в комментариях тебя уже пытались переубедить. Извини, не хочу тратить время на очередного шизофреника изобретателя-вечного-двигателя сторонника-торсионных-полей опровергателя-ОТО и вот теперь канторо-разоблачителя.
amkartashov
00.00.0000 00:00про "спасибо за ссылку". Если ты опровергатель доказательства Кантора, то ты наверняка знаешь, где найти как он её доказал.
Daddy_Cool
00.00.0000 00:00А приведите пожалуйста пример практической задачи где используется что-то в духе алгоритма зачеленяи отеля?
Задачу знаю давно, но вот как она соотносится с жизнью?
chebo
00.00.0000 00:00+1Мы вот когда в 80-х приезжали на Эльбрус/Чегет кататься на лыжах, заселялись в местные отели именно по такому алгоритму.
lllamnyp
00.00.0000 00:00Скажите, пожалуйста, что такое "актуальная бесконечность"? Это похоже на неточный перевод с английского "Hilbert's doesn't have merely hundreds of rooms, it's got an actual infinity". Правильнее перевести "у него их в действительности бесконечность".
Однако, в статье не указано, что это перевод. Добавлю ссылку для читателей, которые предпочитают оригинал: https://archive.nytimes.com/opinionator.blogs.nytimes.com/2010/05/09/the-hilbert-hotel/
jasiejames
00.00.0000 00:00Однако, в статье не указано, что это перевод.
Потому что это не перевод статьи Строгаца.
chebo
00.00.0000 00:00А если приплывает бесконечное число паромов, на палубах которых бесконечное число автобусов, в каждом из которых бесконечное число пассажиров - их тоже всех можно разместить в отеле Гильберта?
nin-jin
00.00.0000 00:00+1Бесконечность - это буквально отсутствие конца. Что бы ты в неё ни засунул, конца у неё от этого не появится.
CaptainFlint
00.00.0000 00:00+1Если каждая из этих бесконечностей счётная, то да, можно. Тем же диагональным методом, только применённым дважды.
jasiejames
00.00.0000 00:00Основная, и мне кажется самая важная, идея бесконечности отеля заключается в том, что она "расширяющаяся", чем больше пытаешься в неё впихнуть, тем больше влезет. Как то так. Если обыденными словами.
avshkol
Эту задачу можно представить в более практичной формулировке:
Если вместо отеля мы представим всю доступную человечеству свободную дисковую память всех электронных устройств (увеличивающуюся благодаря постоянно растущему производству новых дисков и флеш-накопителей, а также методам сжатия), а вместо клиентов - записи всех интересных событий, происходящих с человечеством, разделённых на “автобусы” - людей и локации, то… здесь два варианта: память либо когда-то закончится, либо не закончится никогда…
jasiejames
Ну вы даёте)))
Это почти как, "всё будет хорошо, в крайнем случае - нет"