Treść z książki N.J. Wilenkina "Opowieści o zbiorach". PWN 1972 seria "Biblioteka Problemów".
Od str. 90
Wszystkie dotychczas rozpatrywane zbiory były przeliczalne.
Nasuwa się pytanie, czy wszystkie zbiory nieskończone są zbiorami przeliczalnymi. Gdyby tak było, wówczas matematycy mieliby bardzo łatwe życie: wszystkie zbiory nieskończone miały by tyle samo elementów i nie byłaby potrzebna żadna analiza nieskończoności. Okazało się jednak, że sprawa jest bardziej skomplikowana; zbiory nieprzeliczalne istnieją, i to zbiory o różnych mocach. Jeden ze zbiorów nieprzeliczalnych jest wszystkim dobrze znany. Jest to zbiór wszystkich punktów na linii proslej. Zanim się jednak zajmiemy tym zbiorem, poświęcimy znów nieco uwagi innemu, ściśle z nim związanemu zbiorowi A wariantów zapełnienia lokatorami niezwykłe go hotelu.
Zauważmy, że udowodnienie nieprzeliczalności jakiegoś zbioru jest na ogół niełatwe. Przecież udowodnienie, że jakiś zbiór jest przeliczalny oznacza po prostu wymyślenie jakiejś reguły, według której można ponumerować jego elementy. Natomiast udowodnienie, że pewien zbiór jest nieprzeliczalny oznacza udowodnienie, że takiej reguły nie ma i być nie może. Inaczej mówiąc, należy udowodnić, że niezależnie od wymyślonej reguły, zawsze znajdzie się nie zanumerowany element zbioru. W celu przeprowadzania dowodów nieprzeliczalności zbiorów, Cantor wymyślił bardzo pomysłowy sposób, zwany metodą przekątniową (z metodą tą spotkaliśmy się już na s., 17). Metoda dowodu Cantora stanie się dla nas w pełni zrozumiała, gdy posłuchamy następującego opowiadania Ijona Tichego.
Opowiadałem dotychczas o sukcesach dyrektora niezwykłego hotelu: o tym jak udało mu się ulokować w wypełnionym do ostatniego miejsca hotelu jeszcze nieskończenie wielu lokatorów, a później również mieszkańców nieskończonego zbioru równie niezwykłych hoteli. Był jednak przypadek, gdy owemu magowi i czarodziejowi zdarzyło się niepowodzenie.
Ze Zjednoczenia Hoteli Kosmicznych przyszło polecenie przygotowania zawczasu wszystkich możliwych wariantów zapełnienia pokojów. Warianty owe należało przygotować w postaci tablicy, w której każdy wiersz miał przedstawiać jeden z wariantów. Ustalono, że pokoje zamieszkane miały być oznaczone jedynkami, pokoje zaś puste - zerami. Na przykład wariant
101010101010., ,
oznaczał, że wszystkie pokoje o numerach nieparzystych są zajęte, a wszystkie parzyste - puste; wariant
1111111111., .
oznaczał kompletne zamieszkanie całego hotelu; wariant zaś
0000000000 ...
oznaczał całkowity krach finansowy - wszystkie pokoje puste.
Dyrektor był przeciążony pracą i dlatego wymyślił bardzo proste wyjście z sytuacji. Każdemu dyżurnemu każdego piętra polecił przygotować tyle wariantów zamieszkania, ile pokojów było w jego dyspozycji. Jednocześnie zalecił nie powtarzać tych samych wariantów. Po kilku dniach przedłożono wykazy dyrektorowi, on zaś sporządził z nich jeden wielki spis.
- Czy jest pan przekonany o tym, że ten spis jest pełny? zapytałem dyrektora. - Czy nie przepuszczono czasem jakiegoś wariantu?
- Nie wiem - odpowiedział. - Wariantów jest w spisie nieskończenie wiele i nie wiem jak sprawdzić, czy nie istnieje jeszcze jakiś wariant nie wprowadzony do spisu.
W tym momencie doznałem olśnienia (może zresztą nieco wyolbrzymiam swoje zdolności, a może rozmowy z profesorem Tarantogą nie minęły bez echa).
- Mogę się założyć, że spis jest niepełny. Podejmuję się wskazać wariant, który na pewno został przepuszczony.
- Zgadzam się z tym, że spis jest niepełny. Nie wierzę jednak, że uda się znaleźć przepuszczony wariant, przecież jest w tym spisie nieskończenie wiele wariantów.
Przecięliśmy podane dłonie, zakład stanął. Aby go wygrać, poleciłem przybić na drzwiach każdego pokoju tabliczkę z wypisanym wariantem, który odpowiadał temu pokojowi (jak czytelnik zapewne pamięta, przygotowano tyle wariantów, ile było pokojów w hotelu). Moje dalsze postępowanie było niezwykle proste. Podchodząc do drzwi pierwszego pokoju zobaczyłem, że odpowiadający mu wariant zaczyna się cyfrą 0. Natychmiast w moim notesie pojawiła się cyfra l; była to pierwsza cyfra wariantu, który chciałem skonstruować.
Gdy podszedłem do drugiego pokoju, nie interesowałem się wcale pierwszą cyfrą jego wariantu, bowiem pierwszą cyfrę jego wariantu miałem już zanotowaną. Dlatego całą uwagę skupiłem na drugiej cyfrze. Stwierdziwszy, że jest to cyfra l, zapisałem w swoim notesie cyfrę 0. Podobnie, po odczytaniu na drzwiach trzeciego pokoju znów cyfry l jako trzeciej cyfry odpowiadającego temu pokojowi wariantu zapisałem w swoim notesie ponownie 0. Ogólnie, jeśli stwierdzałem, że n-tą cyfrą n-tego wariantu jest 0, to do notesu wspisywałem na n-tym miejscu cyfrę l, jeśli zaś n-tą cyfrą n-tego wariantu było l, to zapisywałem w notesie 0.
Po obejściu wszystkich pokojów w hotelu miałem zanotowany w notesie ciąg zer i jedynek.
Wchodząc do gabinetu dyrektora powiedziałem:
- Oto interesujący nas opuszczony wariant.
- A skąd wiadomo, że został przepuszczony?
- Wariant ten nie może być pierwszym, ponieważ różni się od pierwszego pierwszą cyfrą, nie może być drugim, ponieważ różni się od drugiego drugą cyfrą, ani trzecim, ponieważ różni się od trzeciego trzecią cyfrą; ogólnie, nie może być n-tym, ponieważ różni się od n-tego n-tą cyfrą.
Wygrałem zakład, w wyniku czego otrzymałem wieczne prawo bezpłatnego korzystania z tego hotelu.
Zostało jednocześnie wyjaśnione, że dla każdego przeliczalnego zbioru wariantów istnieje zawsze wariant nie należący do tego zbioru (warianty te zawsze, można porozwieszać na drzwiach pokojów). Oznacza to, że zbiór wszystkich wariantów ulokowania mieszkańców w hotelu jest nieprzeliczalny i zadanie polecone dyrektorowi okazało się niewykonalne.
Wiadomość o tym trzeba było przekazać telegraficznie. Trzeba przyznać, że w tym niezwykłym hotelu telegraf był również niezwykły. Nadawał on telegramy składające się nie ze skończonego, lecz LI nieskończonego (mówiąc dokładniej - przeliczalnego) zbioru kropek i kresek. Telegramy te miały następującą postać
_._ _._ _ _. itd.
Od razu zrozumiałem, że również zbiór takich telegramów jest nieprzeliczalny, bowiem w miejsce kropek i kresek można wstawić zera i jedynki, i wówczas nie będzie żadnej różnicy między . telegramami z przeliczalnym zbiorem znaków a zbiorem wszystkich wariantów rozmieszczenia gości w hotelu.
Po 'wysłaniu telegramu serdecznie pożegnałem się z dyrektorem hotelu i odleciałem ku galaktyce RGC-8067, gdzie miałem wykonać astrograficzne zdjęcia ...
Łatwo już teraz będzie można udowodnić, że zbiór wszystkich punktów na linii prostej jest nieprzeliczalny. Zamiast mówić o tym zbiorze, możemy mówić o zbiorze wszystkich liczb rzeczywistych, bowiem każdemu punktowi prostej odpowiada liczba rzeczywista i odwrotnie.
Każdą liczbę rzeczywistą można zapisać w postaci ułamka dziesiętnego nieskończonego postaci
α, α1, α2, α3,... αn, ...
Niektóre z tych liczb można zapisać w dwóch różnych postaciach: na przykład 0,50000 ... i 0,49999 ... przedstawiają tę samą .liczbę. Dla uproszczenia będziemy używali zapisu zawierającego zera.
Załóżmy, że udało nam się w jakiś sposób ponumerować wszystkie liczby rzeczywiste. Aby wykazać, że założenie to jest fałszywe, wystarczy wskazać chociaż jedną niezanumerowaną liczbę. Idąc w ślady Ijona Tichego będziemy postępowali następująco.
Najpierw napiszemy zero i postawimy za nim przecinek. Potem weźmiemy liczbę, która miała pierwszy numer i zwrócimy uwagę na jej pierwsze miejsce po przecinku dziesiętnym (tzn. na liczbę dziesiątek). Jeśli cyfra ta jest różna od l, to w konstruowanej przez nas liczbie napiszemy po przecinku l, jeśli zaś cyfra ta jest równa l, to napiszemy po przecinku 2. Następnie przejdziemy do liczby, która otrzymała drugi numer i spojrzymy na jej drugą cyfrę po przecinku. I znów, jeśli ta cyfra jest różna od jedynki, to w konstruowanej liczbie napiszemy na miejscu setek cyfrę l, jeśli zaś ta cyfra jest jedynką, napiszemy cyfrę 2. Dokładnie tak samo będziemy postępowali z dalszymi liczbami, zwracając za każdym razem uwagę tylko na n-tą cyfrę liczby o numerze n. W rezultacie otrzymamy pewną liczbę, składającą się z samych jedynek lub dwójek po przecinku, na przykład:
N = 0,1121211 ...
Jest oczywiste, że liczba ta nie miała żadnego numeru: na pierwszym miejscu dziesiętnym różni się ona od liczby z numerem l, na drugim - od liczby o numerze 2, .. , na n-tym - od liczby o numerze n itd. (patrz s. 17).
Aby czytelnikowi lepiej wyjaśnić, jak powstaje liczba, która nie otrzymała numeru, zakładamy, że przy określonej numeracji pierwszych pięciu liczb ma ona następującą postać:
4,27364 .
-1,31226 .
7,954,71 .
0,62419 .
8,56280 .
Wówczas liczba, która nie otrzymała numeru, będzie miała następujące pierwsze znaki dziesiętne:
0,12121...
Oczywiście nie tylko ta jedna, lecz także wiele innych liczb nic otrzymało numerów (moglibyśmy np. zastępować przez 2 wszystkie cyfry prócz 2, cyfrę zaś 2 - przez 7, albo też wy brać zupełnie inną regułę). Wystarczy jednak istnienie jednej tylko liczby, która nie została objęta numeracją, aby odrzucić hipotezę o możliwości ponumerowania wszystkich liczb rzeczywistych.