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. Konsekwencje tego faktu:

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

Dowód

Niech $f:A\to 𝒫(A)$ będzie dowolną funkcją z danego zbioru $A$ w jego zbiór potęgowy $𝒫(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=\{x\in A:x\notin f(x)\}.$

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

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

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

$m\notin f(m)\Rightarrow m\notin f(m)\wedge m\in B\Rightarrow f(m)\ne B,$

$m\in f(m)\Rightarrow m\in f(m)\wedge m\notin B\Rightarrow f(m)\ne B.$

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

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

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

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

$|A|<|𝒫(A)|.$

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

Historia

Cantor podał podobny dowód w pracy Über eine elementare Frage der Mannigfaltigkeitslehre (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 $f$ jest funkcją na zbiorze $X,$ której wartościami są funkcje charakterystyczne podzbiorów zbioru $X,$ to funkcja charakterystyczna $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ż

• problem stopu

Linki zewnętrzne

• Szablon:Paywall Cantor’s theorem Szablon:Lang, Routledge Encyclopedia of Philosophy, rep.routledge.com [dostęp 2023-05-10].