Парадокс Гильберта в Гранд Отеле - Hilbert's paradox of the Grand Hotel

Парадокс Гильберта о Grand Hotel ( разговорном : Бесконечный Отель Paradox или отеле Гильберта ) является мысленным экспериментом , который иллюстрирует противоречащее свойство бесконечных множеств. Показано, что полностью занятый отель с бесконечно большим количеством номеров может принимать дополнительных гостей, даже бесконечно много, и этот процесс может повторяться бесконечно часто. Идея была представлена Дэвидом Гильбертом в лекции 1924 года «Über das Unendliche», перепечатанной в ( Hilbert 2013 , p.730), и была популяризирована в книге Джорджа Гамова 1947 года « Один, два, три ... бесконечность» .

Парадокс

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

Конечно много новых гостей

Предположим, прибывает новый гость и желает разместиться в отеле. Мы можем (одновременно) переместить гостя, который сейчас находится в комнате 1, в комнату 2, гостя, который сейчас находится в комнате 2, в комнату 3 и так далее, перемещая каждого гостя из их текущей комнаты n в комнату n +1. После этого комната 1 пуста, и нового гостя можно переместить в эту комнату. Повторяя эту процедуру, можно освободить место для любого конечного числа новых гостей. В общем, предположим, что k гостей ищут комнату. Мы можем применить ту же процедуру и переместить каждого гостя из комнаты n в комнату n + k . Аналогичным образом, если k гостей хотят покинуть отель, каждый гость переходит из комнаты n в комнату n - k .

Бесконечно много новых гостей

Также возможно разместить счетное бесконечное количество новых гостей: просто переместите человека, занимающего комнату 1, в комнату 2, гостя, занимающего комнату 2, в комнату 4, и, как правило, гостя, занимающего комнату n, в комнату 2 n (2 раз n ), и все комнаты с нечетными номерами (которые являются счетно бесконечными) будут свободны для новых гостей.

Бесконечно много тренеров с бесконечно большим количеством гостей каждый

Можно разместить бесконечно много вагонов со счетно бесконечным количеством пассажиров в каждом, используя несколько различных методов. Большинство методов зависят от того, что места в вагонах уже пронумерованы (или используют аксиому счетного выбора ). Как правило, для решения этой проблемы можно использовать любую функцию сопряжения . Для каждого из этих методов рассмотрим номер места пассажира в автобусе, номер его вагона , а затем числа и вводятся в два аргумента функции сопряжения . ${\ displaystyle n}$${\ displaystyle c}$${\ displaystyle n}$${\ displaystyle c}$

Метод основных степеней

Освободите комнаты с нечетными номерами, отправив гостя из комнаты в комнату , затем поместите груз первого тренера в комнаты , груз второго тренера в комнаты ; в качестве номера вагона мы используем номера, в которых - нечетное простое число . Это решение оставляет некоторые комнаты пустыми (что может быть полезно для отеля, а может и нет); в частности, все нечетные числа, не являющиеся степенями простого числа , такие как 15 или 847, больше не будут заняты. (Таким образом, строго говоря, это показывает, что количество прибывших меньше или равно количеству созданных вакансий. Легче показать независимыми средствами, что количество прибывших также больше или равно количеству вакансий и, таким образом, они равны , чем модифицировать алгоритм до точного соответствия.) (Алгоритм работает одинаково хорошо, если поменять местами и , но какой бы выбор ни был сделан, он должен применяться единообразно повсюду.) ${\ displaystyle i}$${\ Displaystyle 2 ^ {я}}$${\ displaystyle 3 ^ {n}}$${\ displaystyle 5 ^ {n}}$${\ displaystyle c}$${\ displaystyle p ^ {n}}$${\ displaystyle p}$${\ displaystyle c}$${\ displaystyle n}$${\ displaystyle c}$

Метод факторизации простых чисел

Вы можете поместить каждого человека, занимающего определенное место, и тренера в комнату (предполагая, что c = 0 для людей, уже находящихся в отеле, 1 для первого тренера и т. Д. ...). Поскольку каждое число имеет уникальное разложение на простые множители , легко увидеть, что у всех людей будет комната, в то время как никакие два человека не окажутся в одной комнате. Например, человек в комнате 2592 ( ) сидел в 4-м вагоне на 5-м месте. Как и метод простых степеней, это решение оставляет некоторые комнаты пустыми. ${\ displaystyle s}$${\ displaystyle c}$${\ displaystyle 2 ^ {s} 3 ^ {c}}$${\ displaystyle 2 ^ {5} 3 ^ {4}}$

Этот метод также можно легко расширить для бесконечных ночей, бесконечных входов и т. Д. ... ( ) ${\ displaystyle 2 ^ {s} 3 ^ {c} 5 ^ {n} 7 ^ {e}}$

Метод чередования

Для каждого пассажира сравните длину и в любой позиционной системе счисления , например в десятичной . (Считайте, что каждый житель отеля находится в автобусе №0.) Если какое-либо число короче, добавляйте к нему ведущие нули, пока оба значения не будут иметь одинаковое количество цифр. Чередуйте цифры, чтобы получить номер комнаты: его цифры будут [первая цифра номера тренера] - [первая цифра номера места] - [вторая цифра номера тренера] - [вторая цифра номера места] и т. Д. Гость отеля (вагон №0) из номера 1729 переезжает в номер 01070209 (т. Е. Номер 1 070 209). Пассажир на месте 1234 в автобусе 789 идет в комнату 01728394 (т. Е. В комнату 1 728 394). ${\ displaystyle n}$${\ displaystyle c}$

В отличие от решения Prime Powers, это решение полностью заполняет отель, и мы можем восстановить оригинальный автобус и кресло гостя, изменив процесс чередования в обратном порядке. Сначала добавьте начальный ноль, если в комнате нечетное количество цифр. Затем разделите номер на два числа: номер тренера состоит из нечетных цифр, а номер места - из четных. Конечно, исходная кодировка произвольна, и роли двух чисел можно поменять местами (нечетное место и четное место), если оно применяется последовательно.

Метод треугольных чисел

Те, кто уже находится в отеле, будут перемещены в номер или в -й треугольный номер . Те, кто в вагоне, будут в комнате , или треугольное число плюс . Таким образом, все комнаты будут заполнены одним и только одним гостем. ${\ Displaystyle (п ^ {2} + п) / 2}$${\ displaystyle n}$${\ Displaystyle ((с + п-1) ^ {2} + с + п-1) / 2 + п}$${\ Displaystyle (с + п-1)}$${\ displaystyle n}$

Эту функцию сопряжения можно продемонстрировать визуально, построив отель в виде пирамиды бесконечно высокой высоты высотой в одну комнату . Самый верхний ряд пирамиды - это отдельная комната: комната 1; его второй ряд - комнаты 2 и 3; и так далее. Столбец, образованный множеством крайних правых комнат, будет соответствовать треугольным числам. После того, как они будут заполнены (перераспределенными жителями отеля), оставшиеся пустые комнаты образуют форму пирамиды, точно идентичную первоначальной форме. Таким образом, процесс может повторяться для каждого бесконечного множества. Выполнение этого по одному для каждого тренера потребует бесконечного количества шагов, но, используя предыдущие формулы, гость может определить, какой будет его комната, когда его тренер будет достигнут в процессе, и может просто пойти туда. немедленно.

Метод произвольного перебора

Пусть . счетно, так как счетно, поэтому мы можем перечислить его элементы . Теперь, если назначить th гостя th тренера в th комнату (считать гостей, уже находящихся в отеле, как гостей th тренера). Таким образом, у нас есть функция, назначающая каждого человека комнате; кроме того, это задание не пропускает никакие комнаты. ${\ Displaystyle S: = \ {(a, b) \ mid a, b \ in \ mathbb {N} \}}$${\ displaystyle S}$${\ Displaystyle \ mathbb {N}}$${\ displaystyle s_ {1}, s_ {2}, \ dots}$${\ Displaystyle s_ {п} = (а, б)}$${\ displaystyle b}$${\ displaystyle a}$${\ displaystyle n}$${\ displaystyle 0}$

Дальнейшие слои бесконечности

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

Метод разложения на простые множители можно применить, добавив новое простое число для каждого дополнительного слоя бесконечности ( с паромом). ${\ displaystyle 2 ^ {s} 3 ^ {c} 5 ^ {f}}$${\ displaystyle f}$

Решение для мощности простых чисел может применяться с дальнейшим возведением в степень простых чисел, что приводит к очень большому количеству комнат даже при небольших входных данных. Например, пассажир на втором месте третьего автобуса на втором пароме (адрес 2-3-2) повысит 2-е нечетное простое число (5) до 49, что является результатом того, что третье нечетное простое число (7) окажется возведен в степень своего сиденья номер (2). В этом номере комнаты должно быть более тридцати десятичных цифр.

Метод чередования можно использовать с тремя чередующимися «нитями» вместо двух. Пассажир с адресом 2-3-2 перейдет в комнату 232, а пассажир с адресом 4935-198-82217 - в комнату № 008,402,912,391,587 (ведущие нули можно удалить).

Предвидя возможность любого количества уровней бесконечного количества гостей, отель может пожелать назначить комнаты таким образом, чтобы ни одному гостю не приходилось переезжать, независимо от того, сколько гостей прибудет позже. Одно из решений состоит в том, чтобы преобразовать адрес каждого прибытия в двоичное число, в котором единицы используются в качестве разделителей в начале каждого уровня, в то время как число внутри данного уровня (например, номер тренера гостя) представлено таким количеством нулей. Таким образом, гость с предыдущим адресом 2-5-1-3-1 (пять бесконечных уровней) перейдет в комнату 10010000010100010 (десятичное число 295458).

В качестве дополнительного шага в этом процессе можно удалить один ноль из каждой части номера; в этом примере номер новой комнаты гостя - 101000011001 (2585 в десятичной системе). Это гарантирует, что каждая комната может быть заполнена гипотетическим гостем. Если не прибывает бесконечное множество гостей, то будут заняты только комнаты, которые являются степенью двойки.

Бесконечные слои вложенности

Хотя комнату можно найти для любого конечного числа вложенных бесконечностей людей, это не всегда верно для бесконечного числа слоев, даже если на каждом уровне существует конечное число элементов.

Анализ

Парадокс Гильберта - это достоверный парадокс : он приводит к противоречащему интуиции результату, который доказуемо верно. Утверждения «есть гость в каждой комнате» и «гости не могут быть размещены» не эквивалентны, когда комнат бесконечно много.

Поначалу такое положение вещей может показаться нелогичным. Свойства «бесконечных наборов вещей» сильно отличаются от свойств «конечных наборов вещей». Парадокс Гранд Отеля Гильберта можно понять, используя теорию трансфинитных чисел Кантора . Таким образом, в обычной (конечной) гостинице с более чем одним номером количество нечетных номеров явно меньше общего количества номеров. Однако в удачно названном Гранд-отеле Гильберта количество комнат с нечетными номерами не меньше общего «количества» комнат. В математических терминах, то мощность из подмножества , содержащего нечетные номера такой же , как о мощности множества всех номеров. Действительно, бесконечные множества характеризуются как множества, у которых есть собственные подмножества одинаковой мощности. Для счетных множеств (множеств с той же мощностью, что и натуральные числа ) эта мощность равна . ${\ displaystyle \ aleph _ {0}}$

Перефразируя, для любого счетно бесконечного множества существует биективная функция, которая отображает счетно бесконечное множество в множество натуральных чисел, даже если счетное бесконечное множество содержит натуральные числа. Например, набор рациональных чисел - тех чисел, которые можно записать как частное целых чисел - содержит натуральные числа как подмножество, но не больше, чем набор натуральных чисел, поскольку рациональные числа счетны: существует взаимно однозначное соответствие от от натурального к рациональному.

Ссылки в художественной литературе

• BBC Learning Zone неоднократно демонстрировала одноразовую образовательную документальную драму 1996 года « Отель Гильберт», действие которой происходило в отеле глазами молодой гостьи Фионы Найт, ее имя - игра слов на языке конечного. Программа была разработана, чтобы познакомить зрителей с концепцией бесконечности.
• Роман Белого свет от математик / научной фантастики писателя Рюкер включает в себя отель , основываясь на парадоксе Гильберта, и где главный герой рассказа встречает Георг Кантор .
• В научно-фантастическом романе Стивена Бакстера « Трансцендент» содержится краткое обсуждение природы бесконечности с объяснением, основанным на парадоксе, модифицированном для использования солдат, а не отелей.
• В рассказе Джеффри А. Лэндиса « Туманность» « Рябь в море Дирака » гостиница Гильберта используется как объяснение того, почему бесконечно полное море Дирака все же может принимать частицы.
• В романе Питера Хёга «Чувство снега» «Мисс Смилла» главная героиня размышляет о том, что для менеджера и гостей отеля достойно приложить все эти хлопоты, чтобы опоздавший мог иметь свою комнату и немного уединения.
• В детском романе Ивара Экланда « Кот в стране чисел » «мистер Гильберт» и его жена управляют бесконечным отелем для всех целых чисел. История развивается по треугольному методу рациональных чисел.
• В романе Уилла Уайлса The Way Inn о бесконечно большом мотеле злодея зовут Гильберт.
• В романе Реджинальда Хилла «Чужой дом» персонаж Сэм обращается к парадоксу отеля «Гильберт».
• Рассказ Наума Я. Виленкин «Необыкновенный отель» (часто ошибочно приписываемый Станиславу Лему ) показывает, каким образом гранд-отель Гильберта может быть перетасован, когда прибывает бесконечное количество новых хозяев.
• Джон Родерик и Кен Дженнингс обсуждали отель в своем подкасте Omnibus в эпизоде The Hilbert Hotel Entry .
• Сага по комиксам «Буря» из серии « Лига выдающихся джентльменов » Алана Мура и Кевина О'Нила показывает злодея по имени Бесконечность. В рассказе предполагается, что злодей отправляется в отель на основе парадокса Гильберта. Упоминается также Георг Кантор .

Смотрите также

• Список парадоксов
• Парадокс Банаха – Тарского
• Парадокс Галилея
• Парадоксы теории множеств
• Принцип голубятни

использованная литература

• Гильберт, Дэвид (2013), Эвальд, Уильям; Зиг, Вильфрид (ред.), Лекции Дэвида Гильберта по основам арифметики и логики 1917-1933 гг. , Гейдельберг: Springer-Verlag, DOI : 10.1007 / 978-3-540-69444-1 , ISBN 978-3-540-20578-4

внешние ссылки

• Бесконечный отель Гильберта . М. Хазевинкель. Энциклопедия математики , Springer. Доступ 25 мая 2007 г.
• Нэнси Кейси, добро пожаловать в отель Infinity!  - Парадокс, рассказанный как юмористический рассказ о владельце отеля и строительном подрядчике, основан на враждующих математиках XIX века Георге Канторе и Леопольде Кронекере.
• Стивен Строгац, The Hilbert Hotel , NY Times, 9 мая 2010 г.
• Бесконечный отель Гильберта , h2g2
• Отель Гильберт - презентация на YouTube
• "За гранью"
• см. песню на стр. 704 Американского математического ежемесячника за октябрь 2006 г. или стр. 177 журнала Journal of Mathematics and the Arts за декабрь 2011 г.
• Бесконечный парадокс отеля - Джефф Декофски - Уроки TED-Ed