Twierdzenie Cantora

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania
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 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 są 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 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 | edytuj kod]

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