Cantor pokazał, że wszystkich liczb rzeczywistych nie da się umieścić na żadnej liście
Załóżmy, że ktoś twierdzi, iż wypisał wszystkie liczby rzeczywiste z przedziału [0,1] w kolejności r1, r2, r3, …. Argument przekątniowy Cantora konstruuje nową liczbę, której n-ta cyfra po przecinku różni się od n-tej cyfry liczby rn. Taka liczba różni się więc od pierwszej pozycji co najmniej pierwszą cyfrą, od drugiej — drugą, i tak dalej. Nie może znajdować się nigdzie na rzekomo kompletnej liście. Oznacza to, że liczby rzeczywiste są nieprzeliczalne: ich nieskończoność jest większa niż nieskończoność liczb naturalnych.
Założenie: spróbujmy wypisać wszystko
Cantorowski dowód zaczyna się od założenia przeciwnego do tezy. Wyobraźmy sobie, że wszystkie liczby z przedziału [0,1) da się ponumerować: r1, r2, r3, …. Każdą zapisujemy jako nieskończone rozwinięcie dziesiętne. Mamy więc tabelę: wiersz pierwszy to cyfry r1, drugi — r2, trzeci — r3 i tak dalej. Jeżeli lista rzeczywiście jest kompletna, każda liczba z tego przedziału musi pojawić się w którymś wierszu. Cantor nie próbuje sprawdzać listy po kolei. Zamiast tego buduje jeden obiekt, który z definicji ominie każdy jej wiersz.
Ruch po przekątnej
Patrzymy na pierwszą cyfrę pierwszej liczby, drugą cyfrę drugiej, trzecią cyfrę trzeciej i ogólnie n-tą cyfrę n-tego wiersza. Następnie tworzymy nową liczbę x, wybierając na n-tym miejscu cyfrę różną od tej przekątnej. Dla bezpieczeństwa można użyć na przykład reguły: jeżeli dana cyfra to 4, wpisz 5, a w przeciwnym razie wpisz 4. Dzięki temu omijamy kłopot z podwójnymi zapisami typu 0,4999… = 0,5000…. Nowa liczba x różni się od rn na n-tym miejscu, zatem nie jest równa żadnemu elementowi listy.
Dlaczego to obala każdą możliwą listę
Siła argumentu polega na jego ogólności. Nie ma znaczenia, w jakiej kolejności ktoś próbuje ustawić liczby, jak sprytny algorytm zastosuje ani czy na liście widać jakikolwiek wzór. Z każdej konkretnej listy można zbudować przekątną liczbę, której na niej nie ma. Dowód nie mówi więc tylko, że pewna próba numerowania jest nieudana. Pokazuje, że nie może istnieć żadna bijekcja między liczbami naturalnymi a liczbami rzeczywistymi.
Narodziny różnych rozmiarów nieskończoności
Liczby naturalne są nieskończone, lecz przeliczalne: same stanowią wzorcową listę 1, 2, 3, …. Liczby całkowite i wymierne również można ponumerować. Cantor odkrył natomiast, że continuum liczb rzeczywistych ma większą kardynalność. Odtąd „nieskończony” przestało być pojedynczym rozmiarem. Można mieć dwa zbiory bez końca, a mimo to udowodnić, że w jednym sensie elementów jednego z nich jest ściśle więcej.
Przekątna jako metoda, nie tylko sztuczka
Idea przekątniowa okazała się jedną z najbardziej płodnych technik matematyki i logiki. Jej ogólny schemat brzmi: załóż, że wszystkie obiekty pewnego rodzaju zostały wypisane, a następnie skonstruuj obiekt różniący się od n-tego wpisu w n-tym kontrolowanym miejscu. Podobna architektura pojawia się później w teorii obliczeń i dowodach nierozstrzygalności. Nie oznacza to, że wszystkie takie twierdzenia są tym samym, ale pokazuje, jak jeden pomysł potrafi przekraczać granice działów matematyki.
Co dokładnie zostało udowodnione
Wniosek nie brzmi, że liczb rzeczywistych „nie da się wypisać w praktyce”, bo również całej listy liczb naturalnych nigdy fizycznie nie wypiszemy. Różnica jest czysto matematyczna. Dla naturalnych istnieje funkcja przypisująca kolejne numery wszystkim elementom; dla rzeczywistych taka funkcja nie może być bijekcją. To mocniejsze stwierdzenie niż ograniczenie czasu czy pamięci. Nie zależy od technologii, lecz od struktury samych zbiorów. To dlatego argument Cantora jest czymś więcej niż obserwacją o ogromnej liczbie danych: mówi, że żaden skończony ani nieskończony algorytm numerujący kolejnymi liczbami naturalnymi nie może stworzyć kompletnej listy continuum.
Przekątna działa również bez zapisu dziesiętnego
Rozwinięcia dziesiętne są wygodną ilustracją, ale istota dowodu jest bardziej abstrakcyjna. Można rozważyć wszystkie nieskończone ciągi zer i jedynek i założyć, że ustawiono je na liście. Następnie w n-tym miejscu nowego ciągu wybieramy bit przeciwny do n-tego bitu n-tego wiersza. Nowy ciąg nie występuje na liście. Takie ciągi można utożsamić z podzbiorami N przez wskazanie, które pozycje mają wartość 1. Dlatego argument przekątniowy łączy nieprzeliczalność continuum z ogólniejszym twierdzeniem, że zbiór wszystkich podzbiorów N jest większy od samego N. Sednem nie są więc cyfry, lecz możliwość systematycznego „uciekania” z każdej rzekomo kompletnej enumeracji. Do dowodu nie potrzeba nawet całej prostej rzeczywistej. Wystarczy wykazać, że sam przedział (0,1) nie daje się ponumerować, a już wiadomo, że R również jest nieprzeliczalny, ponieważ zawiera ten przedział. To wzmacnia intuicję wyniku: „większa” nieskończoność nie bierze się z nieskończonej długości osi. Jest już obecna w dowolnie krótkim odcinku continuum.