Matematyka.pl

Dzień dobry

Na angielskiej Wikipedii od kilkunastu lat wisi artykuł o hotelu Hilberta, a w nim jedna z metod zapełniania pokoi "Prime powers method": Zalecenie z pierwszego zdania tej metody "Send the guest in room n to room \(\displaystyle{ 2^{n}}\)" jest według mnie niewykonalne, a metoda jest niepoprawna.

Uzasadniam:

Do rozlokowania \(\displaystyle{ n}\) gości w pokojach o numerach \(\displaystyle{ 2^{n}}\) hotel musi mieć również \(\displaystyle{ 2^{n}}\) pokoi. Wprawdzie większość z nich będzie pusta - ale muszą być.
Aby zakończyć przemieszczanie tych gości (na podjeździe hotelu czekają już następne autokary) musimy zakwaterować wszystkich aktualnych, czyli cały zbiór \(\displaystyle{ N}\) o mocy \(\displaystyle{ \left| \mathbb{N} \right| }\).
Dla tego zbioru gości moc zbioru koniecznych pokoi (zajętych i pustych) to \(\displaystyle{ 2 ^ {\left| \mathbb{N} \right|} }\). Jednak zgodnie z założeniem hotel ma nieskończoną, ale przeliczalną ilość pokoi, czyli \(\displaystyle{ \left| \mathbb{N} \right| }\). Sprzeczność.

Czy to ja się mylę (gdzie i jak?), czy autorzy i czytelnicy tego artykułu (nikt nie poprawił, nie usunął)?

Waldek

WaldekZ pisze: ↑23 sie 2023, o 21:06Dla tego zbioru gości moc zbioru koniecznych pokoi (zajętych i pustych) to \(\displaystyle{ 2 ^ {\left| \mathbb{N} \right|} }\).

Wskazany fragment artykułu jest poprawny, a Twój błąd jest w tym miejscu. Jest prawdą, że po przemieszczeniu pierwszych \(\displaystyle{ n}\) gości zajęte będą (niektóre) pokoje o numerach aż do \(\displaystyle{ 2^n}\). Ale nie wynika stąd, że aby przemieścić \(\displaystyle{ |\NN|}\) gości, potrzebne jest \(\displaystyle{ 2^{|\NN|}}\) pokoi. W istocie potrzebna jest taka liczba pokoi, która jest większa lub równa od każdego \(\displaystyle{ 2^n}\), gdzie \(\displaystyle{ n \in \NN}\), więc \(\displaystyle{ |\NN|}\) pokoi w zupełności wystarczy.

Innymi słowy - skoro do dyspozycji są pokoje numerowane wszystkimi liczbami naturalnymi, to w szczególności do dyspozycji jest każdy pokój o numerze postaci \(\displaystyle{ 2^n}\) - a to właśnie te pokoje wystarczają, żeby przemieścić wszystkich pierwotnych lokatorów.

Ty się mylisz.

WaldekZ pisze: ↑23 sie 2023, o 21:06 Dla tego zbioru gości moc zbioru koniecznych pokoi (zajętych i pustych) to \(\displaystyle{ 2 ^ {\left| \mathbb{N} \right|} }\).

Nieprawda. Skąd ten pomysł?

WaldekZ pisze: ↑23 sie 2023, o 21:06 Zalecenie z pierwszego zdania tej metody "Send the guest in room n to room \(\displaystyle{ 2^{n}}\)" jest według mnie niewykonalne, a metoda jest niepoprawna.

Funkcja \(\displaystyle{ f:\NN^+\to\NN^+,\ f(n)=2^n}\) jest bardzo porządną injekcją, a o to chodzi. I jest to jak najbardziej wykonalne...

JK

Wiem, że dla skończonych \(\displaystyle{ n}\) istnieje oczywista bijekcja \(\displaystyle{ n \rightarrow 2^{n}}\). Chciałbym jednak zobaczyć, jak można formalnie udowodnić, dla \(\displaystyle{ \ całego~ zbioru }\) gości o mocy \(\displaystyle{ \left| \mathbb{N} \right|}\), że zbiór koniecznych pokoi ma również moc \(\displaystyle{ \left| \mathbb{N} \right|}\), a nie \(\displaystyle{ 2 ^ {\left| \mathbb{N} \right|} }\). Czyli dowód na liczbach kardynalnych, a nie naturalnych.
Dowód dla zbioru - jako całości - jest dla mnie ważny, gdyż pociąga za sobą pewne konsekwencje, do których chciałbym się odnieść w przyszłości.

Najwyraźniej nie rozumiesz, o czym piszesz.

WaldekZ pisze: ↑23 sie 2023, o 22:55 Wiem, że dla skończonych \(\displaystyle{ n}\) istnieje oczywista bijekcja \(\displaystyle{ n \rightarrow 2^{n}}\).

Nie wiem, jaką "oczywistą bijekcję dla skończonych \(\displaystyle{ n}\)" masz na myśli. Wiesz co to jest bijekcja?

WaldekZ pisze: ↑23 sie 2023, o 22:55Chciałbym jednak zobaczyć, jak można formalnie udowodnić, dla \(\displaystyle{ \ całego~ zbioru }\) gości o mocy \(\displaystyle{ \left| \mathbb{N} \right|}\), że zbiór koniecznych pokoi ma również moc \(\displaystyle{ \left| \mathbb{N} \right|}\), a nie \(\displaystyle{ 2 ^ {\left| \mathbb{N} \right|} }\). Czyli dowód na liczbach kardynalnych, a nie naturalnych.

Masz to dwukrotnie napisane powyżej: mniej formalnie

Dasio11 pisze: ↑23 sie 2023, o 21:28W istocie potrzebna jest taka liczba pokoi, która jest większa lub równa od każdego \(\displaystyle{ 2^n}\), gdzie \(\displaystyle{ n \in \NN}\), więc \(\displaystyle{ |\NN|}\) pokoi w zupełności wystarczy.

Innymi słowy - skoro do dyspozycji są pokoje numerowane wszystkimi liczbami naturalnymi, to w szczególności do dyspozycji jest każdy pokój o numerze postaci \(\displaystyle{ 2^n}\) - a to właśnie te pokoje wystarczają, żeby przemieścić wszystkich pierwotnych lokatorów.

i bardziej formalnie:

Jan Kraszewski pisze: ↑23 sie 2023, o 21:34 Funkcja \(\displaystyle{ f:\NN^+\to\NN^+,\ f(n)=2^n}\) jest bardzo porządną injekcją, a o to chodzi.

Poza tym

WaldekZ pisze: ↑23 sie 2023, o 22:55Czyli dowód na liczbach kardynalnych, a nie naturalnych.

liczby naturalne też są kardynalne.

JK

Pokażę, jak ja widzę taki dowód:

Niech hotel Hilberta ma piętra. To nic nie zmienia, numeracja pokoi zostaje zachowana. Na każdym piętrze \(\displaystyle{ n}\) jest \(\displaystyle{ R(n)=2^{n}}\) pokoi, z których tylko pierwszy będzie zajęty, a pozostałe pozostaną puste:

\(\displaystyle{ n~~~~R(n) ~~~~numery~pokoi~}\)
\(\displaystyle{ 0~~~~1~~~~~~~~~~~~~~~~1}\)
\(\displaystyle{ 1~~~~2~~~~~~~~~~~~~~~~2~3}\)
\(\displaystyle{ 2~~~~4~~~~~~~~~~~~~~~~4~ 5~ 6~ 7}\)
\(\displaystyle{ 3~~~~8~~~~~~~~~~~~~~~~8~ 9~ 10~ 11~ 12~ 13~ 14~ 15}\)
...

Teraz, pod każdą tabliczką z numerem pokoju zawieśmy dodatkową tabliczkę, każdą z zapisanym innym podzbiorem zbioru \(\displaystyle{ \left\{ 1..n\right\} }\):

\(\displaystyle{ n~~~~R(n) ~~~~podzbiór~}\)
\(\displaystyle{ 0~~~~1~~~~~~~~~~~~~~~~\left\{ \emptyset\right\} }\)
\(\displaystyle{ 1~~~~2~~~~~~~~~~~~~~~~\left\{ \emptyset\right\} ~\left\{ 1 \right\} }\)
\(\displaystyle{ 2~~~~4~~~~~~~~~~~~~~~~\left\{ \emptyset\right\} ~\left\{ 1 \right\}~ \left\{ 2 \right\}~ \left\{ 1 , 2 \right\}}\)
\(\displaystyle{ 3~~~~8~~~~~~~~~~~~~~~~\left\{ \emptyset\right\} ~\left\{ 1 \right\}~ \left\{ 2 \right\}~ \left\{ 3 \right\}~\left\{ 1, 2\right\} ~\left\{ 1, 3 \right\}~ \left\{ 2 , 3 \right\}~ \left\{ 1 , 2, 3 \right\}}\)
...

Na każdym piętrze mamy wszystkie podzbiory zbioru \(\displaystyle{ \left\{ 1..n\right\} }\). Dla każdego piętra \(\displaystyle{ n}\) tabliczki z tymi podzbiorami tworzą więc zbiór potęgowy \(\displaystyle{ P(n)}\) o mocy \(\displaystyle{ \left| 2^{n}\right| }\). Jaką moc będzie miał zbiór wszystkich tabliczek w całym hotelu?

Dokładnie taką, jaką zbiór wszystkich pokoi hotelu, bo przecież na każdych drzwiach wisi dokładnie jedna tabliczka. A zatem - \(\displaystyle{ \aleph_0}\) (tj. \(\displaystyle{ |\NN|}\)).

WaldekZ pisze: ↑24 sie 2023, o 01:39 \(\displaystyle{ n~~~~R(n) ~~~~podzbiór~}\)
\(\displaystyle{ 0~~~~1~~~~~~~~~~~~~~~~\left\{ \emptyset\right\} }\)

Tak czysto technicznie: podzbiorem \(\displaystyle{ \NN}\) jest \(\displaystyle{ \emptyset,}\) a nie \(\displaystyle{ \{\emptyset\}.}\)

Myślę, że uległeś złudzeniu, że skoro \(\displaystyle{ n}\) "zbiega" do \(\displaystyle{ \aleph_0}\), to \(\displaystyle{ 2^n}\) "zbiega" do \(\displaystyle{ 2^{\aleph_0}}\), a to tak nie działa.

JK

Jan Kraszewski pisze: ↑24 sie 2023, o 10:30 Tak czysto technicznie: podzbiorem \(\displaystyle{ \NN}\) jest \(\displaystyle{ \emptyset,}\) a nie \(\displaystyle{ \{\emptyset\}.}\)

\(\displaystyle{ 1\in \NN \Rightarrow \left\{ \varnothing \right\} \subset \NN }\)

Janusz Tracz pisze: ↑24 sie 2023, o 12:40\(\displaystyle{ 1\in \NN \Rightarrow \left\{ \varnothing \right\} \subset \NN }\)

Nie bardzo wiem, co miałoby znaczyć to wynikanie (tzn. oczywiście wiem, co masz na myśli, ale wtedy należałoby napisać \(\displaystyle{ 1\in\NN\land 1=\{\emptyset\}\land\NN\text{ jest zbiorem tranzytywnym} \Rightarrow \{\emptyset\} \subseteq \NN}\)). Tym niemniej ten "argument" świadczy o niezrozumieniu kontekstu. Po pierwsze, autor wątku z całą pewnością nie tak rozumie liczby naturalne. Po drugie, jawnie wypisuje kolejne podzbiory, skąd łatwo można wywnioskować, że popełnia wspomniany błąd.

JK

WaldekZ pisze: ↑24 sie 2023, o 01:39 Pokażę, jak ja widzę taki dowód:

Niech hotel Hilberta ma piętra. To nic nie zmienia, numeracja pokoi zostaje zachowana. Na każdym piętrze \(\displaystyle{ n}\) jest \(\displaystyle{ R(n)=2^{n}}\) pokoi, z których tylko pierwszy będzie zajęty, a pozostałe pozostaną puste:

\(\displaystyle{ n~~~~R(n) ~~~~numery~pokoi~}\)
\(\displaystyle{ 0~~~~1~~~~~~~~~~~~~~~~1}\)
\(\displaystyle{ 1~~~~2~~~~~~~~~~~~~~~~2~3}\)
\(\displaystyle{ 2~~~~4~~~~~~~~~~~~~~~~4~ 5~ 6~ 7}\)
\(\displaystyle{ 3~~~~8~~~~~~~~~~~~~~~~8~ 9~ 10~ 11~ 12~ 13~ 14~ 15}\)
...

Teraz, pod każdą tabliczką z numerem pokoju zawieśmy dodatkową tabliczkę, każdą z zapisanym innym podzbiorem zbioru \(\displaystyle{ \left\{ 1..n\right\} }\):

\(\displaystyle{ n~~~~R(n) ~~~~podzbiór~}\)
\(\displaystyle{ 0~~~~1~~~~~~~~~~~~~~~~\left\{ \emptyset\right\} }\)
\(\displaystyle{ 1~~~~2~~~~~~~~~~~~~~~~\left\{ \emptyset\right\} ~\left\{ 1 \right\} }\)
\(\displaystyle{ 2~~~~4~~~~~~~~~~~~~~~~\left\{ \emptyset\right\} ~\left\{ 1 \right\}~ \left\{ 2 \right\}~ \left\{ 1 , 2 \right\}}\)
\(\displaystyle{ 3~~~~8~~~~~~~~~~~~~~~~\left\{ \emptyset\right\} ~\left\{ 1 \right\}~ \left\{ 2 \right\}~ \left\{ 3 \right\}~\left\{ 1, 2\right\} ~\left\{ 1, 3 \right\}~ \left\{ 2 , 3 \right\}~ \left\{ 1 , 2, 3 \right\}}\)
...

Na każdym piętrze mamy wszystkie podzbiory zbioru \(\displaystyle{ \left\{ 1..n\right\} }\). Dla każdego piętra \(\displaystyle{ n}\) tabliczki z tymi podzbiorami tworzą więc zbiór potęgowy \(\displaystyle{ P(n)}\) o mocy \(\displaystyle{ \left| 2^{n}\right| }\). Jaką moc będzie miał zbiór wszystkich tabliczek w całym hotelu?

Błąd tkwi w tym, że nie dostaniesz wszystkich podzbiorów `\NN` a tylko skończone (i to każdy powieszony mnóstwo razy na różnych drzwiach) . A tych jest niewiele.

Dokładniej, jest ich tyle, ile jest liczb naturalnych.

Wynika to stąd, że:
\(\displaystyle{ \prod_{i=1}^{n} \NN \sim \NN}\),
a to wynika z równoliczości \(\displaystyle{ \NN \times \NN\sim \NN}\), oraz z prostego prawa: \(\displaystyle{ A \times \left( B \times C\right)\sim \left( A \times B\right) \times C;}\) więc przez prostą intuicję można chyba udowodnić, że dla dowolnego \(\displaystyle{ n}\) naturalnego, poczynając od \(\displaystyle{ n=1}\): \(\displaystyle{ \prod_{i=1}^{n} \NN\sim \NN}\), a stąd wynika, że dla dowolnego ustalonego \(\displaystyle{ n}\) naturalnego \(\displaystyle{ n \ge 1}\) rodzina wszystkich \(\displaystyle{ n}\) elementowych podzbiorów zbioru liczb naturalnych jest równoliczna że zbiorem \(\displaystyle{ \NN}\), a zatem rodzina wszystkich skończonych podzbiorów zbioru liczb naturalnych, jako suma przeliczalnej rodziny zbiorów przeliczalnych, jest zbiorem przeliczalnym, tzn. równolicznym że zbiorem \(\displaystyle{ \NN}\) .

Zdaje się, że mamy ogólniejszy fakt:
Jeśli \(\displaystyle{ X}\) jest zbiorem nieskończonym, to rodzina wszystkich skończonych podzbiorów zbioru \(\displaystyle{ X}\) jest z nim równoliczna.
Wynika to z prawa \(\displaystyle{ X \times X\sim X;}\) dla nieskończonego zbioru \(\displaystyle{ X.}\)

Bardzo dziękuję wszystkim Państwu za wypowiedzi dotyczące rodzaju nieskończoności w wykładniczym hotelu Hilberta.

Na mój pomysł, że zbiór pokoi ma moc \(\displaystyle{ {\mathfrak {c}}}\) jedem z panów zareagował: "Nieprawda. Skąd ten pomysł?"
Niebawem w następnym wątku o nawiązującym tytule wyjaśnię "skąd ten pomysł", a państwo mi wyjaśnią, że znowu się mylę.

Pozdrawiam

WaldekZ pisze: ↑7 wrz 2023, o 23:17Niebawem w następnym wątku o nawiązującym tytule wyjaśnię "skąd ten pomysł", a państwo mi wyjaśnią, że znowu się mylę.

Niewątpliwie.

JK