Czy są jeszcze inne liczby kardynalne niż alef₀ i c? Odpowiedź na to pytanie daje następujące twierdzenie Cantora:

Dowód

Jeśli X jest zbiorem pustym, to twierdzenie jest oczywiście prawdziwe, bo |X|= 0, a |2 ^X| =1 (por. wykład 1).

Oczywiście |X| ≤ |2^X|, bo funkcja g(x)={x} odwzorowuje X na podzbiór zbioru potęgowego P(X), a mianowicie na rodzinę zbiorów jednoelementowych {{x}: x ∈ X}.

Wystarczy zatem pokazać, że żaden podzbiór zbioru X nie jest równoliczny z 2^X. Przypuśćmy przeciwnie, że dla pewnego A ⊆ X, istnieje bijekcja f : A → 2 ^X. Czyli dla każdego a ∈ A, f(a) ⊆ X. Niech Z = {a ∈ A : a ∉ f(a)}. Oczywiście Z ⊆ X. Ponieważ funkcja f jest odwzorowaniem A na zbiór wszystkich podzbiorów X, więc dla pewnego a₀ ∈ A, f(a₀) = Z. Rozważymy dwa możliwe przypadki: I przypadek a₀ ∈ Z , II przypadek a₀ ∉ Z

W pierwszym przypadku, z założenia a₀ ∈ Z i na mocy definicji zbioru Z mamy a₀ ∉ f(a₀), czyli a₀ ∉ Z. Sprzeczność.

W drugim przypadku, gdyby a₀ ∉ Z, to ponieważ f(a₀) = Z, więc a₀ ∉ f(a₀). Stąd i na mocy definicji zbioru Z mamy a₀ ∈ Z. Sprzeczność.

Ponieważ oba wykluczające się przypadki prowadzą do sprzeczności, więc zbiór Z nie może istnieć, i w konsekwencji, nie może istnieć funkcja f odwzorowująca A wzajemnie jednoznacznie na 2 ^X. ♦

Twierdzenie Cantora daje metodę konstrukcji nieskończonego ciągu różnych liczb kardynalnych.

Zbiory

mają wszystkie różne moce. W szczególności wynika stąd również, że |N| < |2^N|.

Inną konsekwencją twierdzenia Cantora jest nieistnienie zbioru wszystkich zbiorów. (Rozważaliśmy już ten problem w wykładzie 1.6.). Z założenia, że istnieje zbiór wszystkich zbiorów X wynika, że zbiór wszystkich podzbiorów jakiegokolwiek zbioru A jest podzbiorem zbioru X, czyli P(A) ⊆ X. W szczególności P(X) ⊆ X. Zatem |P(X)| ≤ |X|, co jest sprzeczne z twierdzeniem Cantora.