Page 1 of 1

Hilbertov hotel

Posted: Wed Jun 18, 2014 6:37 pm
by Martin Sleziak
Na jednom z cvičení padla otázka: "Čo z toho, čo sa tu učíme, sa dá povedať študentom na strednej škole?"

Chcel by som napísať niečo o Hilbertovom hoteli, čo je v podstate niečo, čo sme sa učili; len povedané iným jazykom a dá sa to určite porozprávať aj stredoškolákom.

Rozhodne som k tomu chcel napísať nejaký pokec na fórum už skôr - zhruba vtedy, keď ste sa na to pýtali. Nejako sa mi nepodarilo nájsť si čas. Snáď je zmysluplné dať to tu aj teraz. Možno si to niekto pozrie aj napriek tomu, že už má ten predmet za sebou. A ak nie, bude to tu pre ľudí, čo to budú mať zapísané v budúcich rokoch.

Sú aj iné témy z tejto prednášky, ktoré by nemali mať problém zvládnuť stredoškoláci. Napríklad dôkaz, že reálnych čísel je viac ako prirodzených pomocou desiatkového zápisu a diagonálnej metódy. (V aktuálnej verzii prednášok je to príklad 4.5.4. A je to v podstate ten istý dôkaz, ktorý sme predtým robili s dyadickými zápismi. Akurát my sme sa snažili aj dokázať, že každé reálne číslo má jednoznačne určený dyadický zápis a zdôvodniť, kedy je jednoznačný. Pre stredoškolákov to dokazovať zrejme netreba, s desiatkovým zápisom sa proste pracuje ako s prirodzenou reprezentáciou reálnych čísel.) Možno je pre stredoškolákov zvládnuteľná aj ďalšia aplikácia diagonálnej metódy, kde ukážeme, že $2^a>a$, čiže pre každú nekonečnú množinu existuje ešte nejaká ďalšia množina, ktorá je od nej väčšia.

Všeobecne pojem porovnávania veľkosti množín je zrozumiteľný (rovnako veľké = dajú sa popárovať = existuje bijekcia); aj keď nepoužijete slová ako "bijekcia" alebo nezadefinujete pojem "mohutnosti množiny". Dá sa to robiť menej formálne.

Ak si dobre pamätám, tak aj v knihe Peter Bero: Matematici, ja a ty sa vyskytli nejaké veci týkajúce sa vlastne kardinality; hoci je to kniha, ktorú kľudne môžu čítať základoškoláci. (Myslím, že sa tam spomínal napríklad Galileov paradox a aj Aristotelov paradox. Nemám však momentálne prístup k tej knihe, takže to nemôžem skontrolovať. Keďže ste absolvovali pomerne veľa didaktických predmetov, tak meno Peter Bero by vám mohlo byť známe.)

Každopádne, nedá mi nepovedať to, že pre vás ako pre budúcich učiteľov môže byť občas užitočné vedieť aj niečo navyše, nie len to, čo budete učiť na strednej škole. (Teda to, že ste sa na vysokej škole naučili nejakú vec, ktorú nemôžete vysvetliť stredoškolákom, neznamená to, že je pre vás úplne zbytočná. A aspoň do istej miery by ste snáď mohli veriť ľuďom, ktorí zostavovali študijný program a zaradili do neho veci, ktoré považujú za užitočné a zaujímavé pre učiteľov.) Tým nijako netvrdím to, že by znalosti z predmetu teória množín boli úplne nevyhnutné pre každého, kto chce učiť matematiku - to by bol samozrejme nezmysel. Ale osobne si myslím, že veci, ktoré sme prebrali po koniec kapitoly o kardinalite, neboli až také zložité a dajú sa považovať za súčasť všeobecného rozhľadu človeka, ktorý sa zaoberá matematikou.

Re: Hilbertov hotel

Posted: Wed Jun 18, 2014 6:39 pm
by Martin Sleziak
Jednotlivé časti tohoto príbehu vlastne súvisia s nejakými identitami týkajúcimi sa kardinálneho čísla $\newcommand{\alnul}{\aleph_0}\alnul$, ktoré sú ale prerozprávané iným spôsobom. Keďže vy už ste zvyknutí na označenie pre kardinálov, tak sa môžete vždy zamyslieť nad tým, akej identity sa jednotlivé časti príbehu týkajú a aj či sa nepodobajú na niektoré dôkazy, ktoré ste videli na prednáške. (Alebo aj obrátene, môžete sa zamyslieť nad tým, ku ktorým kardinálnym identitám by ste vedeli vymyslieť podobný príbeh.)

Tento spôsob priblíženia nekonečných spočítateľných množín populárnou formou je dosť známy, kľudne ste sa s ním už mohli niekde stretnúť.
Hilbertov hotel

Vo veľmi vzdialenej galaxii, mimo obvyklých trás vogónskych lodí, je planéta nie veľmi odlišná od Zeme. A na tejto planéte je veľmi zvláštny hotel.

Zvláštny je tým, že má nekonečne veľa izieb: Izby hotela sú očíslované prirodzenými číslami: 0, 1, 2, ..., 131, ..., 2475, ... (Keďže sme tak boli zvyknutí z prednášky, číslujem prirodzené čísla od nuly. Na strednej ste asi skôr zvyknutí, že prirodzené čísla začínajú od jednotky.)

A na recepcii hotela pracuje Marek, ktorý kedysi absolvoval učiteľské štúdium na FMFI. Na prvý pohľad sa to môže zdať prekvapivé, ale to, čo sa naučil na matfyze, bolo užitočné aj pri práci v nekonečnom hoteli.

Jedného dňa sa stalo, že hotel bol plne obsadený. Prišiel však ešte jeden hosť. Riaditeľ hotela mu povedal: "Bohužiaľ, všetky izby sú obsadené, nebudeme vás mať kde ubytovať." Našťastie bol práve na recepcii Marek, ktorý mal dobrý nápad: "Čo keby sme poprosili každé hosťa, aby sa presunul do izby s číslom o jedno väčším. Hosť z nultej izby sa posunie do prvej. Izba s číslom 1 sa uvoľní tak, že hosť ktorý tam býval, sa presunie do izby číslo 2. Z izby č. 2 pôjde hosť do izby č. 3., atď. Takto bude po všetkých presunoch v každej izbe stále iba jeden hosť a uvoľníme izbu č. 0 pre nového hosťa.
Spoiler:
Toto je vlastne presne dôkaz identity $\alnul=\alnul+1$.
O týždeň neskôr nastala oveľa komplikovanejšie situácia. V neďalekom hoteli (ktorý mal tiež nekonečne veľa izieb) sa pokazila klimatizácia. Museli teda pre svojich hostí hľadať náhradné ubytovanie. Pred hotelom, v ktorom pracoval Marek, zastal autobus (nekonečný, sedadlá sú očíslované 0, 1, 2, ...) plný hostí zo susedného hotela. Keďže náš hotel bol plný, riaditeľ chcel autobus poslať preč. Našťastie Marek dostal nápad, ako ubytovať všetkých hostí z autobusu, tak, aby nikto z hotela nemusel odísť. Vedeli by ste mu poradiť ako?
Spoiler:
Jedno z mnohých možných riešení: Marek môže požiadať hostí ubytovaných v hoteli, aby sa každý z nich presunul do izby s dvojnásobným číslom. Takto zostali všetky izby s nepárnymi číslami voľné, do nich sa mohli umiestniť všetci hostia, ktorý prišli nekonečným autobusom.
S akou identitou z prednášky táto úloha súvisí?
Spoiler:
Je to $\alnul=\alnul+\alnul$.
Prešla sezóna dovoleniek a každý z hostí ubytovaných v hoteli bol spokojný so službami ale aj so šikovným riešením problémov s kapacitou hotela. Pretože boli spokojní, každý z nich si zobral so sebou niekoľko letákov so základnými informáciami o hoteli, a po príchode domov ho odporúčal aj svojim známym. Vďaka tomu, že sa dobrá povesť hotela takto rozšírila, zrazu keď znovu prišla dovolenková sezóna, stálo pred hotelom (spočítateľne) nekonečne veľa autobusov a v každom z nich (spočítateľne) nekonečne veľa záujemcov o ubytovanie. Vedel si Marek poradiť aj s takýmto problémom?
Spoiler:
Napríklad: Hostí z prvého autobusu mohol ubytovať do izieb s nepárnymi číslami. Hostí z druhého autobusu do izieb s číslami tvaru $2\cdot(2n+1)$, teda do tých izieb, ktoré sú párne, ale nie sú deliteľné štyrmi. Ďalší autobus pôjde do $2^2(2n+1)$ atď.
S akou identitou z prednášky táto úloha súvisí?
Spoiler:
Je to $\alnul=\alnul\cdot\alnul$.
Inak povedané, hľadáme bijekciu medzi $\mathbb N\times\mathbb N$ a $\mathbb N$.
Je veľa takých párovacích funkcií, nejaké sme spomenuli aj na prednáške (práve v kapitole s dôkazom $\alnul^2=\alnul$.)