Twierdzenie Cantora

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
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]

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

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

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

zatem zbiór (element zbioru potęgowego ) nie jest obrazem żadnego elementu zbioru w odwzorowaniu – stąd funkcja nie może być suriekcją (funkcją „na”), a już tym bardziej bijekcją (funkcją wzajemnie jednoznaczną).

A skoro nie istnieje bijekcja ze zbioru na , to zbiór nie jest równoliczny ze swoim zbiorem potęgowym . 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 w , przypisująca każdemu elementowi x jego singleton:

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

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

Historia[edytuj]

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 jest funkcją na zbiorze , której wartościami są funkcje charakterystyczne podzbiorów zbioru , to funkcja charakterystyczna nie należy do zbioru wartości .

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]