Хотелът на Хилберт — парадоксът на безкрайния хотел

📞 Онлайн уроци по математика за цялата страна◆ гл. ас. д-р Атанас Илчев◆ Индивидуални и групови уроци • Тел: 0883 375 433◆ Подготовка за НВО, ДЗИ, кандидатстудентски изпити◆ 📞 Онлайн уроци по математика за цялата страна◆ гл. ас. д-р Атанас Илчев◆ Индивидуални и групови уроци • Тел: 0883 375 433◆ Подготовка за НВО, ДЗИ, кандидатстудентски изпити◆

Любопитно от математиката

Хотелът на Хилберт —
където „няма места“ не значи, че няма място

Представете си хотел с безкрайно много стаи, в който всички стаи са заети. Пристига нов гост. В обикновен хотел това би било краят на разговора — но в хотела на Хилберт управителят само се усмихва. Този прочут мисловен експеримент разкрива най-странните и красиви свойства на безкрайността.

Д-р Атанас Илчев • Поредица: Любопитно от математиката

Безкрайният хотел на Хилберт — художествена интерпретация

Някои от най-дълбоките идеи в математиката се крият зад съвсем прости истории. Хотелът на Хилберт е точно такава — привидно детска гатанка за хотел и гости, зад която стоят строгите закони на безкрайността. Разказът е толкова нагледен, че се разбира без нито една формула, а въпреки това стига до самата основа на теорията на множествата.

Хотел с безкрайно много стаи

Нашият хотел не е обикновен. Стаите му са номерирани с естествените числа — стая 1, стая 2, стая 3, и така без край. За всяко естествено число има точно една стая. Тази вечер хотелът е напълно зает: във всяка стая има по един гост, така че на табелата отвън свети „Няма свободни места“.

В обикновен хотел с краен брой стаи това би означавало край. Ако сто стаи са заети от сто гости, сто и първият гост няма къде да отседне. Но безкрайността се подчинява на съвсем други правила.

Един нов гост

На рецепцията пристига уморен пътник и моли за стая. „Разбира се“, отвръща управителят. Той пуска съобщение до всички стаи с една проста инструкция: всеки гост да се премести в стаята със следващия номер. Гостът от стая 1 отива в стая 2, гостът от стая 2 — в стая 3, и така нататък. С други думи, гостът от стая \(n\) се мести в стая \(n+1\).

Тъй като стаите са безкрайно много, всеки гост има къде да отиде — никой не остава без стая. Но при цялото това разместване стая 1 се освобождава и новият гост се настанява в нея. Хотелът беше пълен, а въпреки това намери място. Ако вместо един пристигнат сто нови гости, управителят просто премества всеки досегашен гост сто стаи напред: гостът от стая \(n\) отива в стая \(n+100\). Така стаи 1, 2, \(\dots\), 100 се освобождават за новодошлите.

Когато пристигне нов гост, всеки се премества с една стая напред (n → n+1)

Какво е изброима безкрайност Едно множество е изброимо безкрайно, ако елементите му могат да се подредят в списък, номериран с естествените числа \(1, 2, 3, \dots\) — тоест да се сложат в биекция (взаимно еднозначно съответствие) с множеството \(\mathbb{N}\). Стаите на хотела, гостите, местата в един безкраен автобус — всички те са изброими. Именно това е безкрайността, с която хотелът на Хилберт умее да се справя.

Цял автобус с безкрайно много гости

Сега пред хотела спира автобус с безкрайно много пътници — по един за всяко естествено число. Дали и те могат да се настанят? Триковете с изместване с една или сто стаи вече няма да свършат работа, защото новите гости не са краен брой.

Управителят намира по-хитро решение. Той моли всеки настанен гост да се премести в стаята с двойния номер: гостът от стая \(n\) отива в стая \(2n\). Така всички стари гости се озовават в стаите с четни номера — 2, 4, 6, 8… — а всички стаи с нечетни номера остават свободни. Нечетните числа са безкрайно много, затова има точно толкова свободни стаи, колкото са новодошлите. Пътникът от място 1 отива в стая 1, от място 2 — в стая 3, от място 3 — в стая 5, и така всеки получава своя стая.

Безкрайно много автобуси

Представете си, че пристигат изброимо безкрайно много автобуси, номерирани \(1, 2, 3, \dots\), а във всеки от тях пътуват изброимо безкрайно много пътници, също номерирани \(1, 2, 3, \dots\). На пръв поглед това изглежда като много по-голяма безкрайност. Оказва се обаче, че и всички тези хора могат да бъдат подредени в един безкраен списък.

Едно елегантно решение използва простите числа. Настанените гости отиват в стаите, чиито номера са степени на двойката: гостът от стая \(n\) се мести в стая \(2^n\). Пътниците от първия автобус се пращат в степените на тройката, тези от втория — в степените на петицата, от третия — в степените на седмицата, и така за всеки автобус се използва следващото просто число.

Защо това работи Простите числа са безкрайно много (това е доказал още Евклид), затова за всеки автобус има отделно просто число. А според основната теорема на аритметиката всяко естествено число се разлага на прости множители по единствен начин. Затова две различни степени на различни прости числа никога не дават една и съща стая — сблъсъци няма и всеки гост получава собствена стая.

И тук има още една изненада. След настаняването не просто няма недостиг на стаи — безкрайно много стаи изобщо не се използват. Например стая 15 остава празна, защото \(15 = 3 \cdot 5\) не е степен на едно-единствено просто число. Същото важи за безкрайно много други номера, като 6, 10 или 12. Така хотелът настанява изброимо безкрайно много автобуси с изброимо безкрайно много пътници и въпреки това остава с безкрайно много свободни стаи.

Същината на примера е, че всички двойки \((i, j) \in \mathbb{N} \times \mathbb{N}\), в които \(i\) е номерът на автобуса, а \(j\) — номерът на мястото в него, могат да бъдат подредени в един изброим списък. Следователно \(\lvert \mathbb{N} \times \mathbb{N} \rvert = \aleph_0\), или на езика на кардиналната аритметика

\[\aleph_0 \cdot \aleph_0 = \aleph_0.\]

„Пълно“ не значи „няма място“

Хотелът на Хилберт се нарича парадокс не защото води до логическо противоречие, а защото резултатът противоречи на интуицията ни, изградена върху крайни множества. В рамките на теорията на безкрайните множества всичко, което се случва в хотела, е напълно последователно.

За краен хотел изреченията „във всяка стая има гост“ и „не може да се настани нов гост“ означават едно и също. За безкрайния хотел те са две напълно различни неща. Хотелът наистина е пълен — всяка стая е заета — и въпреки това след разместване винаги се намира място. Ето аритметиката, която стои зад това, изразена чрез \(\aleph_0\) (алеф-нула) — символа за размера на изброимата безкрайност:

Странната аритметика на безкрайното \(\aleph_0 + 1 = \aleph_0\) — един нов гост не променя размера на безкрайността.
\(\aleph_0 + \aleph_0 = \aleph_0\) — цял безкраен автобус също.
\(\aleph_0 \times \aleph_0 = \aleph_0\) — безкрайно много автобуси с по безкрайно много места.
Затова при безкраен хотел „всички стаи са заети“ не означава, че след подходящо пренареждане не може да се освободи място за още гости.

Математическата идея зад хотела Свойството, което прави триковете на Хилберт възможни, може да се формулира строго. Едно множество се нарича Дедекиндово безкрайно, ако може да бъде поставено в биекция със свое собствено подмножество, което е различно от цялото множество. Например съответствието \(n \mapsto 2n\) свързва всички естествени числа \(\mathbb{N}\) само с четните — а четните са само част от \(\mathbb{N}\), но са „точно толкова много“ в смисъла на Канторовата теория на мощностите. Именно това се случва, когато старите гости се преместват в стаите с четни номера. Хотелът на Хилберт е тази абстрактна идея, превърната в история за стаи и гости. Рихард Дедекинд въвежда тази характеристика на безкрайното множество през 1888 г.

А рационалните числа побират ли се? Да. На пръв поглед рационалните числа изглеждат много повече от естествените — между всеки две различни рационални числа има безкрайно много други. Въпреки това те могат да бъдат подредени в един списък, тоест \(\lvert \mathbb{Q} \rvert = \aleph_0\). Един начин да се види това е да разглеждаме дробите \(\frac{p}{q}\) с \(p \in \mathbb{Z}\) и \(q \in \mathbb{N}\). Всяко рационално число се задава от поне една такава двойка \((p, q)\), а множеството \(\mathbb{Z} \times \mathbb{N}\) е изброимо. Някои дроби се повтарят — например \(\tfrac{1}{2} = \tfrac{2}{4}\) — но това не пречи да подредим всички рационални числа в един списък. Освен това \(\mathbb{N} \subset \mathbb{Q}\), така че рационалните числа са безкрайно много — следователно те са изброимо безкрайно много. Затова, ако пред хотела пристигне по един гост за всяко рационално число, управителят все още може да ги настани. Истинската граница се появява едва при реалните числа.

Границата на хотела

Дали хотелът може да побере всеки вид безкрайност? Оказва се, че не.

Представете си, че пред хотела се извива опашка, в която има по един човек за всяко реално число между 0 и 1 — за всяка безкрайна десетична дроб. Тази опашка изглежда като предишните, но крие съществена разлика: реалните числа не могат да бъдат подредени в списък. Колкото и хитро да опитваме да ги номерираме с естествените числа, винаги ще останат реални числа извън списъка.

Това е прочутият диагонален аргумент на Георг Кантор. Ако допуснем, че сме съставили пълен списък на всички реални числа, Кантор построява ново число, което се различава от първото по първата цифра, от второто — по втората, от третото — по третата, и така нататък. Полученото число не съвпада с нито едно от списъка — значи списъкът не е бил пълен.

За да избегнем една техническа тънкост — че някои числа имат по две десетични представяния, например \(0{,}5000\dots = 0{,}4999\dots\) — можем да използваме следното правило: ако съответната диагонална цифра е 1, избираме 2, а във всички останали случаи избираме 1. Така новото число се различава от \(n\)-тото число поне по \(n\)-тата цифра за всяко \(n\), а същевременно не възниква проблем с опашки от деветки или нули.

Изводът е, че реалните числа са неизброимо много. Тяхната мощност се записва \(2^{\aleph_0}\), и този запис не е случаен. Всяко подмножество на естествените числа може да се закодира с безкрайна редица от нули и единици — пишем 1, ако дадено число принадлежи на подмножеството, и 0, ако не. Затова множеството на всички подмножества на \(\mathbb{N}\), означавано \(\mathcal{P}(\mathbb{N})\), има мощност

\[\lvert \mathcal{P}(\mathbb{N}) \rvert = 2^{\aleph_0},\]

а тези безкрайни двоични редици имат същата мощност като реалните числа. Оттук \(\lvert \mathbb{R} \rvert = 2^{\aleph_0}\) — строго повече от изброимата безкрайност \(\aleph_0\) на стаите.

С други думи, хотелът на Хилберт се справя блестящо с всяка изброима тълпа, но пред неизброимата безкрайност на реалните числа е безсилен. Тъкмо това откритие на Кантор — че съществуват различни по големина безкрайности — стои в основата на целия мисловен експеримент.

Още една изненада: алгебричните числа също се побират Не само рационалните числа са изброими. Изброими са дори всички алгебрични числа — тези, които са корени на ненулеви полиноми с цели коефициенти, като \(\sqrt{2}\), \(\sqrt[3]{5}\) или \(\frac{1+\sqrt{5}}{2}\). Причината е, че ненулевите полиноми с цели коефициенти са изброимо много, а всеки от тях има само краен брой корени; оттук \(\lvert \overline{\mathbb{Q}} \rvert = \aleph_0\). Но реалните числа са неизброими — значи неизброимо много от тях не са алгебрични, а трансцендентни. Именно по този път Кантор достига до първото си доказателство за неизброимостта през 1874 г.

Има ли най-голяма безкрайност? Не. Кантор доказва, че за всяко множество \(A\) множеството на всичките му подмножества \(\mathcal{P}(A)\) има строго по-голяма мощност: \(\lvert \mathcal{P}(A) \rvert > \lvert A \rvert\). Затова за всяка дадена безкрайна мощност може да се построи строго по-голяма: \[\aleph_0 < 2^{\aleph_0} < 2^{2^{\aleph_0}} < 2^{2^{2^{\aleph_0}}} < \cdots\] Реалните числа са прекалено много за хотела на Хилберт, но дори тяхната безкрайност далеч не е последната.

1924–25

лекционният курс, в който се появява хотелът

ℵ₀

изброимата безкрайност: стаите, гостите и всички автобуси

2^ℵ₀

по-голямата безкрайност на реалните числа, която не се побира

1888

годината, в която Дедекинд определя безкрайното множество

Хилберт не е първият

Още Галилео Галилей през XVII век обръща внимание на една особеност на безкрайните множества. Положителните цели числа могат да се съпоставят едно към едно със своите квадрати:

\[1 \leftrightarrow 1, \quad 2 \leftrightarrow 4, \quad 3 \leftrightarrow 9, \quad 4 \leftrightarrow 16, \quad \dots\]

Така множеството на всички квадрати има същата мощност като множеството на всички естествени числа, въпреки че е само негова част. Галилей вижда в това затруднение за обичайните понятия „по-голямо“, „по-малко“ и „равно“ и заключава, че те просто не се пренасят върху безкрайното. Два века и половина по-късно Кантор превръща именно биекцията в строг критерий за сравняване на мощности, а хотелът на Хилберт прави същото явление видимо чрез стаи и гости.

Откъде идва хотелът

Дейвид Хилберт (1862–1943)

Мисловният експеримент носи името на Дейвид Хилберт (1862–1943) — един от най-влиятелните математици на XX век. Хилберт представя примера с безкрайния хотел в полупопулярен лекционен курс в Гьотинген през зимния семестър 1924–1925 г., посветен на безкрайното в математиката, физиката и астрономията. Самият той не го публикува; примерът е запазен в записки от курса, подготвени от неговия асистент Лотар Нордхайм. Темата е тясно свързана с прочутата лекция на Хилберт „Über das Unendliche“ („За безкрайното“) от 1925 г., публикувана през 1926 г. — макар че самият пример с хотела не влиза в публикувания текст.

Широка известност хотелът получава едва през 1947 г., когато физикът Джордж Гамов го описва в книгата си „Едно, две, три… безкрайност“. Оттам нататък образът на безкрайния хотел се превръща в един от най-обичаните начини да се обясни безкрайността — използван в лекции, книги, а по-късно дори в спорове от космологията и философията.

Любопитно. Гамов не оставя примера само в математиката. В книгата си „The Creation of the Universe“ от 1952 г. Гамов отново използва хотела — този път за да обясни защо няма логическо противоречие в идеята за пространство, което е безкрайно и същевременно се разширява. Оттогава „Хотел Безкрайност“ вдъхновява не само математици и физици, но и писатели и музиканти — има дори песни, чийто рефрен описва как във вечно пълния хотел винаги се намира още едно място.

Хилберт и „истинската“ безкрайност

Любопитното е, че самият Хилберт е предпазлив към идеята за реално съществуваща безкрайност. За него безкрайността е преди всичко полезно математическо понятие, а не нещо, което срещаме в природата. В лекцията си от 1925 г. той заключава, че безкрайното не се среща никъде в действителността — то живее само в мисленето ни.

Същевременно Хилберт е пламенен защитник на теорията на множествата на Кантор срещу нейните критици. Прочута е неговата фраза, че никой не бива да ни прогони от „рая“, който Кантор е създал за математиката.

Никой няма да ни прогони от рая, който Кантор създаде за нас. — Дейвид Хилберт, за теорията на множествата

Този „рай“ обаче крие и въпроси без отговор. Естествено е да се запитаме дали съществува безкрайност, по-голяма от изброимата, но по-малка от тази на реалните числа. Континуум-хипотезата твърди, че такава междинна мощност няма. Ако означим с \(\aleph_1\) най-малката неизброима мощност, това може да се запише съвсем кратко:

\[2^{\aleph_0} = \aleph_1,\]

тоест мощността на реалните числа идва непосредствено след изброимата безкрайност. По-късно се установява нещо изумително: самата континуум-хипотеза е независима от стандартната аксиоматика на теорията на множествата (ZFC). Кърт Гьодел показва през 1938 г., че ZFC не може да опровергае континуум-хипотезата, а Пол Коен доказва през 1963 г., че ZFC не може и да я докаже. Ако ZFC е непротиворечива, тогава са непротиворечиви както приемането, така и отричането на хипотезата.

Защо е важно

Хотелът на Хилберт е нещо повече от забавна гатанка. Той е може би най-нагледното въведение в теорията на множествата: за няколко минути читателят усвоява идеите за биекция, за изброимост и за различните размери на безкрайността, без нито едно тежко определение. Не по-малко ценен е урокът по смирение — нашата интуиция, изградена върху крайни неща, е ненадежден водач в света на безкрайното.

Хотелът напомня и защо в теорията на множествата интуицията трябва да бъде заменена със строги определения. В началото на XX век наивната теория на множествата се сблъсква с истински противоречия, най-известното от които е парадоксът на Ръсел. Причината там не е самото наличие на безкрайни множества, а прекалено свободното допускане какви множества изобщо могат да бъдат образувани. Хотелът на Хилберт е питомната страна на същата тази безкрайност — онази, която повече очарова, отколкото плаши.

А в основата на всичко стои един прост образ: хотел, който е пълен, но никога не е затворен. Може би затова хотелът на Хилберт се разказва вече цял век — той превръща една от най-трудните идеи в математиката в история, която всеки може да предаде на приятел.

Кратка хронология

• Галилео Галилей описва парадокса за естествените числа и техните квадрати.
• Георг Кантор доказва, че реалните числа са неизброими.
• Рихард Дедекинд формулира характерното свойство на безкрайното множество.
• Кантор публикува прочутия диагонален аргумент.
• Хилберт използва примера с безкрайния хотел в лекционен курс в Гьотинген.
• Хилберт изнася лекцията „Über das Unendliche“.
• Кърт Гьодел показва, че ако ZFC е непротиворечива, то и ZFC заедно с континуум-хипотезата е непротиворечива.
• Джордж Гамов популяризира хотела в „Едно, две, три… безкрайност“.
• Пол Коен показва, че ако ZFC е непротиворечива, то и ZFC заедно с отрицанието на континуум-хипотезата е непротиворечива. Заедно с резултата на Гьодел това установява независимостта на CH от ZFC.

---

Източници

1. Encyclopædia Britannica. Infinite Hotel Paradox. britannica.com
2. Kragh, H. The True (?) Story of Hilbert's Infinite Hotel. arXiv:1403.0059
3. Hilbert, D. Über das Unendliche. Mathematische Annalen 95 (1926), 161–190.
4. Galilei, G. Discorsi e dimostrazioni matematiche intorno a due nuove scienze. 1638.
5. Dedekind, R. Was sind und was sollen die Zahlen? 1888.
6. Cantor, G. Ueber eine Eigenschaft des Inbegriffs aller reellen algebraischen Zahlen. Journal für die reine und angewandte Mathematik 77 (1874), 258–262.
7. Cantor, G. Über eine elementare Frage der Mannigfaltigkeitslehre. Jahresbericht der DMV, 1891.
8. Gödel, K. The Consistency of the Continuum Hypothesis. Princeton University Press, 1940.
9. Cohen, P. J. The Independence of the Continuum Hypothesis. Proceedings of the National Academy of Sciences, 1963–1964.
10. Gamow, G. One, Two, Three… Infinity. Viking Press, 1947.
11. Gamow, G. The Creation of the Universe. Viking Press, 1952.

Още от поредицата „Любопитно от математиката“

▶

Георг Кантор и различните размери на безкрайността

Човекът, който доказа, че някои безкрайности са по-големи от други — и създаде „рая“, който Хилберт така пламенно защитаваше.

Прочети статията →

---

Запишете урок

Индивидуални и групови онлайн уроци по математика за цялата страна

🎓 Подготовка за изпити

• ›НВО по математика след 7. клас
• ›НВО по математика след 10. клас
• ›Кандидатстудентски изпити по математика
• ›Подготовка по математика за ISEE, SAT и A Level

📚 Текущо обучение и студенти

• ›Усвояване на текущия учебен материал (всички класове)
• ›Студенти: математически анализ, линейна алгебра, аналитична геометрия, диференциални уравнения, теория на вероятностите, статистика и др.

✆ 0883 375 433 ☎ Viber

Харесва ли ви съдържанието?

Ако тази статия ви е харесала, можете да подкрепите създаването на нови безплатни материали.

📞 Онлайн уроци по математика за цялата страна◆ гл. ас. д-р Атанас Илчев◆ Индивидуални и групови уроци • Тел: 0883 375 433◆ Подготовка за НВО, ДЗИ, кандидатстудентски изпити◆ 📞 Онлайн уроци по математика за цялата страна◆ гл. ас. д-р Атанас Илчев◆ Индивидуални и групови уроци • Тел: 0883 375 433◆ Подготовка за НВО, ДЗИ, кандидатстудентски изпити◆