Парадокс Хильберта в Гранд Отеле - Hilberts paradox of the Grand Hotel - Wikipedia

Отель Гильберта

Парадокс Гильберта в Гранд Отеле (разговорный: Бесконечный отель Paradox или же Отель Гильберта) это мысленный эксперимент который иллюстрирует нелогичный свойство бесконечных множеств. Показано, что в полностью занятом отеле с бесконечно большим количеством номеров могут по-прежнему проживать дополнительные гости, даже бесконечно много, и этот процесс может повторяться бесконечно часто. Идея была представлена Дэвид Гильберт в лекции 1924 г. "Über das Unendliche", перепечатанной в (Гильберт 2013, стр.730), и была популяризирована через Георгий Гамов книга 1947 года Один, два, три ... бесконечность.^[1][2]

Парадокс

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

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

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

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

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

Бесконечно много тренеров, в каждом бесконечно много гостей

Дальнейшая информация: Функция сопряжения

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

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

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

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

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

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

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

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

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

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

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

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

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

Позволять ${\displaystyle S:=\{(a,b)\mid a,b\in \mathbb {N} \}}$. ${\displaystyle S}$ счетно, поскольку ${\displaystyle \mathbb {N} }$ счетно, поэтому мы можем перечислить его элементы ${\displaystyle s_{1},s_{2},\dots }$. Сейчас если ${\displaystyle s_{n}=(a,b)}$назначьте ${\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}}$.^[3]

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

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

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

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

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

Рекомендации

1. Краг, Хельге (2014). "Правдивая (?) История бесконечного отеля Гильберта". arXiv:1403.0059.
2. Гамов, Джордж (1947). Один, два, три ... бесконечность: факты и предположения науки. Нью-Йорк: Viking Press. п. 17.
3. Ракер, Руди (1984) [1982]. Бесконечность и разум. Наука и философия бесконечного. Паладин. С. 73–78. ISBN  0-586-08465-7.
4. https://www.imdb.com/title/tt0443537/

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

внешняя ссылка

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