Twierdzenie Cantora

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ódEdytuj

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.

HistoriaEdytuj

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