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 nie jest obrazem żadnego elementu zbioru w odwzorowaniu , stąd funkcja nie może być suriekcją (funkcją „na”), a w szczególności nie może być bijekcją. Oznacza to, że zbiory i nie jest równoliczne: .

Jednocześnie zbiór nie może mieć mocy większej od swojego zbioru potęgowego , gdyż jest równoliczny z podzbiorem właściwym zbioru . Istnieje bowiem 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 z uwagi na użyte wyrażenie jest 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]