Twierdzenie Cantora

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

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:

$B=\left\{\,x\in A : x\notin f(x)\,\right\}.$

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

$B\subseteq A \implies B\in P(A).$

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 $B' = A\setminus B$ , 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 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 być mocy większej od zbioru potęgowego, gdyż jest równoliczny z jego podzbiorem właściwym – istnieje iniekcja z $A$ w $P (A)$ :

$g : A \ni x \mapsto \{x\} \in 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 $x\notin f(x)$ ) 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 $x\mapsto 1-f(x)(x)$ 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.

Źródło: "http://pl.wikipedia.org../../../t/w/i/Twierdzenie_Cantora_d866.html"

Kategorie: Teoria mnogości • Twierdzenia matematyczne