Zbiór wszystkich podzbiorów jest zawsze większy od zbioru, od którego zaczęliśmy
Dla dowolnego zbioru S można utworzyć jego zbiór potęgowy P(S), czyli zbiór wszystkich podzbiorów S. Cantor udowodnił, że P(S) ma zawsze większą kardynalność niż S — także wtedy, gdy S jest już nieskończony. Gdyby funkcja f:S→P(S) miała trafiać w każdy podzbiór, można zbudować D={x∈S : x∉f(x)}. Zbiór D różni się od f(x) co najmniej w punkcie x dla każdego x, więc nie jest wartością f dla żadnego argumentu. To prowadzi do niezwykłej konsekwencji: nie istnieje największy rozmiar nieskończoności. w standardowej teorii mnogości.
Od zwykłego zbioru do zbioru wszystkich wyborów
Jeśli S={a,b,c}, jego zbiór potęgowy zawiera osiem elementów: zbiór pusty, trzy zbiory jednoelementowe, trzy dwuelementowe i całe S. Dla zbioru n-elementowego liczba podzbiorów wynosi 2^n. W przypadku skończonym nic dziwnego się nie dzieje — 2^n jest większe od n dla dodatniego n. Zaskoczenie zaczyna się przy zbiorach nieskończonych. Można by podejrzewać, że po osiągnięciu „nieskończoności” operacja tworzenia podzbiorów nie zwiększa już rozmiaru. Twierdzenie Cantora mówi, że zwiększa go zawsze.
Przekątniowy podzbiór, którego brakuje
Załóżmy, że istnieje funkcja f:S→P(S), która trafia w każdy podzbiór S. Dla każdego elementu x możemy zapytać, czy x należy do podzbioru f(x). Zdefiniujmy D jako zbiór tych x, dla których odpowiedź brzmi „nie”. Ponieważ D sam jest podzbiorem S, surjektywność f wymagałaby istnienia takiego a, że f(a)=D. Wtedy pytamy: czy a należy do D? Z definicji D, a należy do D wtedy i tylko wtedy, gdy a nie należy do f(a). Lecz f(a)=D, więc otrzymujemy sprzeczność. Żadna funkcja z S do P(S) nie może być na P(S) surjektywna.
Więcej niż tylko liczby naturalne i rzeczywiste
Dla S=N zbiór P(N) można utożsamić z nieskończonymi ciągami zer i jedynek: na n-tym miejscu wpisujemy 1, jeśli n należy do danego podzbioru. Taki zbiór ma kardynalność continuum, tę samą co R. Ale twierdzenie działa ponownie: P(P(N)) jest jeszcze większy. Następnie można utworzyć kolejny zbiór potęgowy i znów zwiększyć kardynalność. Nie otrzymujemy jednej „najwyższej” nieskończoności, tylko niekończącą się hierarchię coraz większych kardynałów.
Dlaczego nie ma największej nieskończoności
Gdyby istniał zbiór S o największej możliwej kardynalności, utworzenie P(S) dałoby zbiór o większej kardynalności, co przeczyłoby założeniu. Dlatego w standardowej teorii mnogości nie ma największej liczby kardynalnej. Mówi się nawet nie o „zbiorze wszystkich kardynałów”, lecz o klasie właściwej, ponieważ próba zamknięcia wszystkich takich rozmiarów w jednym zbiorze prowadziłaby do problemów tego samego typu.
To nie jest zwykłe potęgowanie liczb
Zapis 2^|S| ma sens w arytmetyce kardynałów, ale warto pamiętać o jego znaczeniu: liczymy funkcje z S do zbioru {0,1}, czyli dokładnie wszystkie sposoby wybierania podzbioru S. Twierdzenie Cantora stwierdza |P(S)|>|S|. Dla skończonych zbiorów widzimy to w elementarnym wzorze 2^n. Dla nieskończonych rezultat jest głębszy, bo pokazuje, że „nieskończoność” nie zatrzymuje procesu powiększania zbioru.
Wspólny rdzeń z argumentem przekątniowym
Dowód jest blisko spokrewniony z przekątnym dowodem nieprzeliczalności liczb rzeczywistych. W obu przypadkach zakładamy, że pewna lista albo funkcja obejmuje wszystko, a następnie budujemy obiekt różniący się od elementu przypisanego mu „na przekątnej”. To uogólnienie jest silniejsze niż konkretny wynik o R: działa dla każdego zbioru, skończonego lub nieskończonego, i daje ogólną maszynę do konstruowania większej kardynalności.
Nie trzeba znać rozmiaru zbioru, aby go powiększyć
Twierdzenie Cantora jest niezwykłe również dlatego, że nie wymaga policzenia elementów S ani nadania jego kardynalności konkretnej nazwy. Wystarczy sam fakt, że mamy zbiór. Operacja S→P(S) automatycznie tworzy obiekt o ściśle większej mocy. Dla zbioru liczb naturalnych podzbiory można kodować nieskończonymi ciągami zer i jedynek: zero oznacza „elementu nie ma”, a jedynka „element jest”. Już ten przykład pokazuje, dlaczego przejście od elementów do wszystkich możliwych wyborów jest tak potężne. Następnie tę samą operację można powtórzyć dla P(N), później dla P(P(N)) i dalej. Każdy krok jest formalnie tego samego rodzaju, lecz każdy prowadzi do nowego, większego poziomu kardynalności. W języku kardynałów rezultat zapisuje się jako |S|<2^{|S|}. Nierówność jest ścisła niezależnie od tego, czy S ma trzy elementy, przeliczalnie nieskończenie wiele elementów, czy jeszcze większą moc. Nie trzeba przy tym znać żadnej „następnej” kardynalności: twierdzenie gwarantuje tylko, że zbiór potęgowy leży wyżej. To subtelne, bo 2^{|S|} nie musi być bezpośrednim następnikiem |S|. Właśnie tutaj pojawia się m.in. hipoteza continuum, pytająca, czy między ℵ₀ a 2^{ℵ₀} istnieje pośrednia kardynalność. Dlatego operacja zbioru potęgowego jest uniwersalną „windą” w hierarchii nieskończoności: z każdego poziomu prowadzi do poziomu ściśle wyższego.