Twierdzenie Cantora

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania
Ujednoznacznienie 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.

Dowód[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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ż[edytuj | edytuj kod]