Парадокс Гільберта
З Вікіпедії, вільної енциклопедії
З Вікіпедії, вільної енциклопедії
Парадокс Гільберта про Grand Hotel (великий готель) — це математичний достовірний парадокс (несуперечливе припущення, що є дуже нелогічним) про нескінченні множини, що його представив німецький математик Давид Гільберт (1862—1943). Давид Гільберт розробив цей парадокс в 1920-х роках, щоб проілюструвати таємничі властивості нескінченності. Парадокс полягає в тому, що в повністю заселений нескінченно великий готель можна додатково заселити нескінченну кількість гостей.
Розглянемо гіпотетичний готель зі зліченно нескінченною кількістю номерів, кожен з яких зайнятий — тобто кожен номер містить гостя. Можна подумати, що готель не в змозі вмістити нових гостей, як було б у випадку зі скінченним числом кімнат.
Нехай новий гість прибуває і хоче бути розміщеним в готелі. Оскільки готель має нескінченно багато кімнат, ми можемо переселити гостя, що займає номер 1, у номер 2, гостя з номера 2 у номер 3 і так далі, і поселити нового гостя в номері 1. Повторюючи цю процедуру, можна звільнити місце для будь-якого зліченного числа нових гостей.
Також можливо розмістити «зліченно нескінченне» число нових гостей: просто перемістити гостя, який займає номер 1 у номер 2, гостя, що займає номер 2 в номер 4, гостя з номера 3 в номер 6 і так далі з номера n в номер 2*n, тоді всі непарні номери будуть вільними для нових гостей.
Можна розмістити у цьому готелі зліченну нескінченність завантажених автобусів, в кожному з яких зліченна нескінченність пасажирів. Можливість зробити це залежить від місць у автобусах, що вже пронумеровані (як альтернативу, менеджер готелю повинен мати аксіому зліченного вибору). Спочатку треба звільнити непарні номери, як зазначено вище, а потім розмістити пасажирів з першого автобуса в кімнати 3n для n = 1, 2, 3, …, пасажирів з другого автобуса в кімнати 5 n для n = 1, 2, … і так далі; для автобуса з номером i ми використовуємо кімнати рN, де р є (i + 1)-ше просте число.
Також можна вирішити задачу за допомогою номерних знаків автобусів і номерів місць для пасажирів (якщо місця не пронумеровані, то потрібно їх пронумерувати). Вважаємо готель у ролі автобуса № 0, а початкові номери кімнат як номери місць у цьому автобусі. Прочергуємо цифри номерів автобусів та номери місць, щоб отримати номери кімнат для гостей. Початковий гість готелю (автобуса № 0) на сидінні (початковий номер) номер 1729 переїжджає до кімнати 01070209 (тобто кімнати 1070209). Те саме робимо для новоприбулих гостей. Пасажир на сидінні 4935 автобуса 198 йде до кімнати 4199385 у готелі.
Загалом будь-яку нумерацію Кантора можна використати для вирішення цієї задачі. Ще один спосіб наблизитися до цього є присвоєння кожному пасажиру номера n, і номера автобуса c в якому він перебуває. Ті, хто вже в готелі, перейдуть до кімнати номер (n2+n)/2, який є n-ним трикутним числом. Ті, що в автобусі номер с перейдуть до кімнати номер ((c+n)2+cn)/2, який є (c+n-1)-ним трикутним числом, плюс (c+n). Таким чином, всі кімнати будуть заповнені одним, і тільки одним гостем (по 1 гостю на кімнату).
Ці випадки показують парадокс не в тому сенсі, що вони демонструють логічне протиріччя, а в тому сенсі, що вони демонструють нелогічний результат, який є правильним через доведення: ситуації «є гість для кожної кімнати» і «надалі гості не можуть розміститися» не є еквівалентними, якщо існує нескінченно багато кімнат (аналогічна ситуація представлена в діагональному доказі Кантора).
Дехто вважає, що такий стан речей є дуже нелогічним. Властивості нескінченних «зібрань речей» істотно відрізняються від скінченних зібрань. Парадокс Grand Hotel Гільберта можна зрозуміти за допомогою теорії Кантора про трансфінітні числа. У звичайному (скінченному) готелі з більш ніж однією кімнатою, число непарних кімнат, очевидно, менше, ніж загальна кількість кімнат. Тим не менш, Гільберт, влучно назвавши готель Grand (великий), показав що кількість непарних кімнат не менша, ніж загальне «число» кімнат. У математичних термінах, потужність підмножини, що містить непарні номери така ж, як потужність множини всіх номерів. Дійсно, нескінченні множини характеризуються як множини, які мають власні підмножини тієї ж потужності. Для зліченних множин, ця потужність називається (алеф-нуль).
Якщо перефразувати, то для будь-якої зліченно нескінченної множини існує бієктивна функція, яка встановлює відповідність між кожним елементом зліченно нескінченної множини й кожним елементом множини натуральних чисел, навіть якщо зліченно нескінченна множина містить натуральні числа. Наприклад, множина раціональних чисел (це ті числа, які можна записати у вигляді відношення цілих чисел) містить натуральні числа як підмножину, але не є більшою, ніж множина натуральних чисел, оскільки раціональні числа є зліченними. Існує бієкція з натуральних в раціональні числа.
Ще одну історію про Grand Hotel можна використати, щоб показати, що математична індукція працює тільки починаючи з бази індукції.
Припустимо, що у великому готелі не дозволяють курити, і жодну сигару не можна пронести до готелю. Незважаючи на це, гість з номера 1 йде до гостя в номері 2, щоб отримати сигару. Гість з номера 2 йде до кімнати 3, щоб отримати дві сигари: одну для себе, іншу для гостя в номері 1. Загалом, гість з кімнати n йде в кімнату (n+1), щоб отримати N сигар. Кожен з них повертається, викурює сигару і віддає сигари, що в нього залишились гостю з номера (n-1). Таким чином, попри те, що жодна сигара не була принесена в готель, кожен гість може курити сигару у своїй кімнаті.
Помилковість цієї історії випливає з того факту, що немає ніякої індуктивної точки (базового випадку), з якої можна отримати індукцію. Хоча показано, що якщо гість з кімнати n має n сигар, то і він, і всі гості з меншим номером кімнати можуть палити, не доведено, що будь-який з гостей насправді має сигари, отже, не випливає, що будь-який гість може викурити сигару в готелі. Той факт, що сигари заборонено проносити до готелю, призначений щоб підкреслити помилковість. Хоча, оскільки існує нескінченне число кімнат у готелі, і кожен гість (n) повинен йти до гостя (n+1) за своєю сигарою, цей процес переходу до наступної кімнати ніколи не зупиняється, і взагалі жоден гість не викурює сигару.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
