Twierdzenie Cantora

Twierdzenie Cantora – twierdzenie teorii mnogości udowodnione przez Georga Cantora mówiące, że każdy zbiór ma moc mniejszą niż rodzina jego wszystkich podzbiorów, czyli jego zbiór potęgowy.

Dowód

Niech $f$ będzie dowolną funkcją z danego zbioru $A$ w jego zbiór potęgowy $P(A)$. Zdefiniujmy zbiór $B$ jako zbiór tych elementów zbioru $A$, które nie należą do swoich obrazów w odwzorowaniu $f$:

$B=\left\{\,x\in A : x\notin f(x)\,\right\}.$

Zbiór $B$, jako podzbiór zbioru $A$, jest oczywiście elementem zbioru potęgowego $A$:

$B\subseteq A \Rightarrow B\in P(A).$

Tak zdefiniowany zbiór nie jest obrazem żadnego elementu zbioru $B$, gdyż element taki należałby wówczas do swego obrazu – a zbiór $B$ składa się z elementów, które nie należą do swych obrazów. Zbiór $B$ nie jest również obrazem żadnego elementu dopełnienia $B' = A\setminus B$, bowiem taki element – jako nie należący do swego obrazu – winien należeć do $B$.

Wobec powyższego zbiór $B$ (element zbioru potęgowego $P(A)$) nie jest obrazem żadnego elementu zbioru $A$ w odwzorowaniu $f$ – zatem funkcja $f$ nie jest suriekcją (funkcją "na"), a zatem nie jest też bijekcją (funkcją wzajemnie jednoznaczną).

A skoro nie istnieje bijekcja ze zbioru $A$ na $P(A)$, to zbiór $A$ nie jest równoliczny ze swoim zbiorem potęgowym $P(A)$. Wiadomo również, że nie może mieć mocy większej od zbioru potęgowego, gdyż jest równoliczny z jego podzbiorem właściwym – istnieje iniekcja z $A$ w $P(A)$, przypisująca każdemu elementowi x jego singleton:

$g : A \ni x \mapsto \{x\} \in P(A).$

Zatem moc zbioru $A$ jest mniejsza niż jego zbioru potęgowego:

$|A| <|P(A)|.$

Powyższy dowód jest (z uwagi na postać wyrażenia $x\notin f(x)$) w istocie rozumowaniem przekątniowym.

Historia

Cantor podał podobny dowód w pracy Über eine elementare Frage der Mannigfaltigkeitslehre (1890/91) (w tej samej pracy zastosował też metodę przekątniową dla dowodu nieprzeliczalności zbioru liczb rzeczywistych, którą wcześniej wykazywał innymi metodami). Dowód ów Cantor sformułował w terminach funkcji charakterystycznych zbioru, nie podzbiorów zbioru, jak się go formułuje obecnie. Wykazał w nim, że jeśli $f$ jest funkcją w zbiorze $X$, której wartościami są dwuwartościowe multifunkcje na zbiorze $X$, to multifunkcja $x\mapsto 1-f(x)(x)$ nie należy do zbioru wartości $f$.

Podobny dowód pojawił się w Principia mathematica Whiteheada i Russella (1903, rozdział 348), gdzie pokazuje się, że form zdaniowych jest więcej niż obiektów. Russell przypisuje ideę dowodu Cantorowi.

Ernst Zermelo cytuje twierdzenie Cantora w pracy Untersuchungen über die Grundlagen der Mengenlehre I (1908).

Zobacz też

• skala betów
• problem stopu