Wobec tego każde dwa rozważane do tej pory zbiory nieskończone okazywały się równoliczne. A może po prostu zawsze tak jest? Może każde dwa nieskończone zbiory są równoliczne? Może elementy dowolnych dwóch nieskończonych zbiorów da się ustawić w pary? Może każda nieskończoność jest pod tym względem taka sama?

Okazuje się, że nie! Udowodnimy mianowicie, że wszystkich liczb rzeczywistych nie da się zakwaterować w hotelu Hilberta. Jasne jest, że liczb rzeczywistych jest nie mniej niż liczb wymiernych - w takim sensie, że każdy z Czytelników prawdopodobnie jest w stanie wskazać liczbę rzeczywistą, która nie jest wymierna. Na przykład albo takie słynne liczby, jak czy Okazuje się jednak, że jest ich dużo więcej - jest ich więcej również w sensie rozważanego przez nas pojęcia równoliczności zbiorów.

Zanim jednak ten fakt udowodnimy, niezbędne jest ustalenie pewnej podstawowej własności liczb rzeczywistych. Wygodne w tym celu będzie wyobrażenie sobie liczb rzeczywistych jako wszystkich punktów na prostej, zwanej osią liczb rzeczywistych. Przy takim wyobrażeniu stanie się jasne, że jeśli rozpatrzę dowolny ciąg coraz krótszych domkniętych przedziałów z których każdy kolejny zawiera się w poprzednim, to istnieje punkt na osi (czyli liczba rzeczywista), który należy do wszystkich tych przedziałów. Mam nadzieję, że wszyscy Czytelnicy zgodzą się z tą własnością, a zresztą definicja zbioru liczb rzeczywistych bezpośrednio właśnie na tej własności jest oparta.

Mając to w pamięci, przejdźmy do dowodu faktu, że liczb rzeczywistych nie da się zakwaterować w hotelu Hilberta. Właściwie spróbujmy zakwaterować tylko liczby z przedziału Jeśli nawet ich nie uda się zakwaterować, to oczywiście tym bardziej nie da się tego zrobić ze wszystkimi liczbami rzeczywistymi. Załóżmy jednak, nie wprost, że jest to możliwe. Załóżmy, że udało się zakwaterować wszystkie liczby rzeczywiste z przedziału w hotelu Hilberta. Została zatem stworzona lista kwaterunkowa wszystkich liczb z tego przedziału, gdzie liczba to liczba zakwaterowana do pokoju o numerze liczba to liczba zakwaterowana do pokoju itd. Co więcej, na tej liście są wszystkie liczby z rozważanego przedziału.

To założenie doprowadzi nas jednak do sprzeczności. Podzielmy bowiem rozważany przedział na trzy części i Zauważmy, że jeden z tych trzech przedziałów nie zawiera liczby W najgorszej sytuacji (gdy jest równa lub ) leży w dwóch z nich. A zatem wybierzmy z nich ten przedział, w którym nie leży Niech to będzie przedział Następnie podzielmy przedział na trzy równe domknięte odcinki (stykające się brzegowymi punktami). Zauważamy, że na pewno nie leży w jednym z nich. Oczywiście być może nie leży nawet w całym przedziale Ale jeśli leży, to co najwyżej w dwóch z tych trzech części jego podziału. Tak czy inaczej, jest jedna część, którą nazwiemy w której na pewno nie leży. Dzielimy podobnie na trzy części i podobnie wybieramy tę z nich, w której nie ma nazywając ją I postępujemy tak dalej, konstruując nieskończony ciąg coraz mniejszych domkniętych przedziałów z których każdy kolejny zawarty jest w poprzednim.

Ale, zgodnie z naszą obserwacją, istnieje liczba która leży we wszystkich tak wybranych przedziałach. Zauważmy jednak, że bowiem leży w w przeciwieństwie do Podobnie bowiem jest punktem na a nie jest. Rozumując tak dalej, zauważamy, że wobec tego liczby nie ma w ogóle na naszej liście kwaterunkowej co jest sprzeczne z założeniem, że umieściliśmy na niej wszystkie liczby z przedziału

A zatem liczb rzeczywistych nie da się zakwaterować w hotelu Hilberta! Zbiór liczb rzeczywistych nie jest równoliczny ze zbiorem liczb naturalnych.

Poszukajmy innych tego typu przykładów. Okazuje się, że zbiór wszystkich nieskończonych ciągów zero-jedynkowych też ma tę własność, że nie jest możliwe zakwaterowanie wszystkich jego elementów w hotelu Hilberta. Załóżmy przeciwnie, że to możliwe, i rozważmy listę kwaterunkową, na której przyporządkowano wszystkie takie ciągi do pokoi. Lista ta będzie miała charakter tabelki o nieskończonej szerokości i wysokości, w której w kolejnych rzędach zapisano kolejne nieskończone ciągi zer i jedynek przyporządkowane do kolejnych pokoi hotelu Hilberta. Jej lewy górny róg mógłby wyglądać następująco:

W poszukiwaniu sprzeczności spójrzmy na przekątną tej tabelki i rozważmy ciąg zer i jedynek, w którym wszystko jest zrobione "na złość". Niech ten ciąg będzie skonstruowany następująco: jeśli początkowy (zerowy) wyraz ciągu z pokoju 0 to to niech nasz ciąg na tym miejscu ma zaś jeśli wyraz ten to niech nasz ciąg ma na tym miejscu Podobnie, jeśli kolejny (pierwszy) wyraz ciągu zakwaterowanego w pokoju to niech nasz ciąg na tym miejscu ma zaś jeśli wyraz ten to niech nasz ciąg ma na tym miejscu I tak dalej, nasz ciąg na -tym swoim miejscu niech ma tę z liczb 0 lub która nie występuje na -tym miejscu ciągu zakwaterowanego w -tym pokoju. Gdyby lewy górny róg listy kwaterunkowej wyglądał tak, jak przedstawiono wyżej, nasz ciąg zaczynałby się więc następująco:

Ale tego znalezionego ciągu, wbrew założeniu, nie ma na liście kwaterunkowej. Rzeczywiście, różni się od każdego ciągu na tej liście: od zerowego na zerowym miejscu, od pierwszego na pierwszym, i tak dalej, od -tego ciągu na -tym swoim miejscu. Co stanowi sprzeczność i dowodzi, że zbiór wszystkich nieskończonych ciągów zer i jedynek nie jest równoliczny ze zbiorem liczb naturalnych.

Aby znaleźć kolejny taki przykład, rozważmy pojęcie zbioru wszystkich podzbiorów danego zbioru. Jeśli zbiór to trzyelementowy zbiór osób, do którego należą Alojzy, Bonifacy i Cezary, to zbiór jego podzbiorów ma elementów. Są to: zbiór pusty, trzy zbiory jednoosobowe (zbiór, którego jedynym elementem jest Alojzy, zbiór, którego jedynym elementem jest Bonifacy, i taki sam zbiór, tyle że z Cezarym), trzy zbiory dwuosobowe o elementach odpowiednio: Alojzy z Bonifacym, Bonifacy z Cezarym i Alojzy z Cezarym, oraz w końcu cały trzyelementowy zbiór. Łatwo można wysnuć wniosek, że podzbiorów zbioru -elementowego jest - zachęcamy Czytelników do zastanowienia się przez chwilę, dlaczego tak jest. Zbiór wszystkich podzbiorów zbioru będziemy oznaczać jako

Rozważmy zbiór Jego elementy to wszystkie podzbiory zbioru liczb naturalnych, a więc na przykład zbiór liczb nieparzystych, zbiór licz pierwszych, ale też zbiór pusty. Oczywiście jest zbiorem nieskończonym. Okazuje się, że jest on na tyle duży, że także nie jest możliwe zakwaterowanie jego elementów w hotelu Hilberta. Aby tego dowieść, zauważmy, że każdy podzbiór liczb naturalnych można zakodować za pomocą nieskończonego ciągu zero-jedynkowego, w którym kolejne cyfry kodują obecność (oznaczaną jako ) lub nieobecność (oznaczaną jako 0) kolejnych liczb naturalnych w rozpatrywanym podzbiorze. Zatem kod zbioru liczb pierwszych zacznie się od bowiem nie są pierwsze, więc na tych miejscach w ciągu widzimy zera, a są liczbami pierwszymi, co skutkuje jedynkami na odpowiednich miejscach ciągu.

Ale skoro każdy podzbiór zbioru liczb naturalnych ma swój unikalny kod w postaci nieskończonego ciągu zer i jedynek (oraz każdy ciąg zer i jedynek odpowiada pewnemu podzbiorowi liczb naturalnych), to nie jest możliwe zakwaterowanie wszystkich podzbiorów zbioru liczb naturalnych w hotelu Hilberta, bowiem, jak już wiemy, nie da się tego zrobić dla zbioru wszystkich ciągów zero-jedynkowych. Zbiór nie jest równoliczny ze zbiorem Możemy napisać, że

Okazuje się, że zachodzi ogólniejszy fakt. Powyższa zależność jest prawdziwa dla dowolnego zbioru (skończonego lub nieskończonego). Podzbiorów zbioru nigdy nie da się ustawić w pary z jego elementami, co będziemy notować Zachęcam Czytelników do zastanowienia się, dlaczego tak jest. Wystarczy nieco zmodyfikować przedstawiony dowód, że !

Twierdzenie to udowodnił już Georg Cantor. Nosi ono jego imię. Pora więc wrócić do jego rozważań i prześledzić historię zaskakującego problemu, którego Cantorowi nie udało się rozwiązać. Ale to już w następnym odcinku.