Twierdzenie Cantora

Z Wikipedii

Twierdzenie Cantora to twierdzenie teorii mnogości głoszące, że każdy zbiór ma moc mniejszą niż zbiór wszystkich jego podzbiorów, czyli jego zbiór potęgowy.

[edytuj] 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 tym przekształceniu:

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

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 , 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):

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

| A | < | P(A) |

– czego należało dowieść.

Zauważmy, że powyższy dowód jest (z uwagi na postać wyrażenia ) w istocie rozumowaniem przekątniowym.

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