Twierdzenie Cantora

Ten artykuł dotyczy twierdzenia o mocy zbioru potęgowego. Zobacz też: inne twierdzenia noszące nazwisko 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. Konsekwencje tego faktu:

• zbiór liczb rzeczywistych jest nieprzeliczalny – większy od zbioru liczb naturalnych^[1];
• nie istnieje zbiór wszystkich zbiorów.

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

${\displaystyle B=\{x\in A:x\notin f(x)\}.}$

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

${\displaystyle B\subseteq A\Rightarrow B\in {\mathcal {P}}(A).}$

Wobec powyższego dla dowolnego elementu ${\displaystyle m}$ należącego do zbioru ${\displaystyle A}$ zachodzi:

${\displaystyle m\notin f(m)\Rightarrow m\notin f(m)\wedge m\in B\Rightarrow f(m)\neq B,}$

${\displaystyle m\in f(m)\Rightarrow m\in f(m)\wedge m\notin B\Rightarrow f(m)\neq B.}$

Zatem zbiór ${\displaystyle B}$ nie jest obrazem żadnego elementu zbioru ${\displaystyle A}$ w odwzorowaniu ${\displaystyle f,}$ stąd funkcja ${\displaystyle f}$ nie może być suriekcją (funkcją „na”), a w szczególności nie może być bijekcją. Oznacza to, że zbiory ${\displaystyle A}$ i ${\displaystyle {\mathcal {P}}(A)}$ nie są równoliczne: ${\displaystyle |A|\neq |{\mathcal {P}}(A)|.}$

Jednocześnie zbiór ${\displaystyle A}$ nie może mieć mocy większej od swojego zbioru potęgowego ${\displaystyle {\mathcal {P}}(A),}$ gdyż jest równoliczny z podzbiorem właściwym zbioru ${\displaystyle {\mathcal {P}}(A).}$ Istnieje bowiem iniekcja z ${\displaystyle A}$ w ${\displaystyle {\mathcal {P}}(A),}$ przypisująca każdemu elementowi ${\displaystyle x}$ jego singleton:

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

Zatem moc zbioru ${\displaystyle A}$ jest mniejsza niż jego zbioru potęgowego:

${\displaystyle |A|<|{\mathcal {P}}(A)|.}$

Powyższy dowód z uwagi na użyte wyrażenie ${\displaystyle x\notin f(x)}$ jest rozumowaniem przekątniowym.

Cantor podał podobny dowód w pracy Über eine elementare Frage der Mannigfaltigkeitslehre^[2][3] (1890/91) (gdzie zastosował metodę przekątniową, również 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ł mianowicie, że jeśli ${\displaystyle f}$ jest funkcją na zbiorze ${\displaystyle X,}$ której wartościami są funkcje charakterystyczne podzbiorów zbioru ${\displaystyle X,}$ to funkcja charakterystyczna ${\displaystyle x\mapsto 1-(f(x))(x)}$ nie należy do zbioru wartości ${\displaystyle 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).

• problem stopu

• Cantor’s theorem (ang.), Routledge Encyclopedia of Philosophy, rep.routledge.com [dostęp 2023-05-10].