Twierdzenie Cantora


Twierdzenie Cantora w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

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.

Spis treści

Dowód | edytuj kod

Niech f : A P ( A ) {\displaystyle f\colon A\to {\mathcal {P}}(A)} będzie dowolną funkcją z danego zbioru A {\displaystyle A} w jego zbiór potęgowy P ( A ) . {\displaystyle {\mathcal {P}}(A).} Zdefiniujmy zbiór B {\displaystyle B} jako zbiór tych elementów zbioru A , {\displaystyle A,} które nie należą do swoich obrazów w odwzorowaniu f : {\displaystyle f{:}}

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

Zbiór B , {\displaystyle B,} jako podzbiór zbioru A , {\displaystyle A,} jest oczywiście elementem zbioru potęgowego A : {\displaystyle A{:}}

B A B P ( A ) . {\displaystyle B\subseteq A\Rightarrow B\in {\mathcal {P}}(A).}

Wobec powyższego dla dowolnego elementu m {\displaystyle m} należącego do zbioru A {\displaystyle A} zachodzi:

m f ( m ) m f ( m ) m B f ( m ) B , {\displaystyle m\notin f(m)\Rightarrow m\notin f(m)\wedge m\in B\Rightarrow f(m)\neq B,} m f ( m ) m f ( m ) m B f ( m ) B . {\displaystyle m\in f(m)\Rightarrow m\in f(m)\wedge m\notin B\Rightarrow f(m)\neq B.}

Zatem zbiór B {\displaystyle B} nie jest obrazem żadnego elementu zbioru A {\displaystyle A} w odwzorowaniu f , {\displaystyle f,} stąd funkcja f {\displaystyle f} nie może być suriekcją (funkcją „na”), a w szczególności nie może być bijekcją. Oznacza to, że zbiory A {\displaystyle A} i P ( A ) {\displaystyle {\mathcal {P}}(A)} nie są równoliczne: | A | | P ( A ) | . {\displaystyle |A|\neq |{\mathcal {P}}(A)|.}

Jednocześnie zbiór A {\displaystyle A} nie może mieć mocy większej od swojego zbioru potęgowego P ( A ) , {\displaystyle {\mathcal {P}}(A),} gdyż jest równoliczny z podzbiorem właściwym zbioru P ( A ) . {\displaystyle {\mathcal {P}}(A).} Istnieje bowiem iniekcja z A {\displaystyle A} w P ( A ) , {\displaystyle {\mathcal {P}}(A),} przypisująca każdemu elementowi x {\displaystyle x} jego singleton:

g : A x { x } P ( A ) . {\displaystyle g:A\ni x\mapsto \{x\}\in {\mathcal {P}}(A).}

Zatem moc zbioru A {\displaystyle A} jest mniejsza niż jego zbioru potęgowego:

| A | < | P ( A ) | . {\displaystyle |A|<|{\mathcal {P}}(A)|.}

Powyższy dowód z uwagi na użyte wyrażenie x f ( x ) {\displaystyle x\notin f(x)} jest rozumowaniem przekątniowym.

Historia | edytuj kod

Cantor podał podobny dowód w pracy Über eine elementare Frage der Mannigfaltigkeitslehre[1][2] (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 f {\displaystyle f} jest funkcją na zbiorze X , {\displaystyle X,} której wartościami są funkcje charakterystyczne podzbiorów zbioru X , {\displaystyle X,} to funkcja charakterystyczna x 1 ( f ( x ) ) ( x ) {\displaystyle x\mapsto 1-(f(x))(x)} nie należy do zbioru wartości f . {\displaystyle 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ż | edytuj kod

Przypisy | edytuj kod

  1. GeorgG. Cantor GeorgG., Ueber eine elementare Frage der Mannigfaltigkeitslehre, „Jahresbericht der Deutschen Mathematiker Vereinigung” (1), 1891, s. 75–78 .
  2. Google Translate™, DeepL™, Peter P. Jones: A Translation of G. Cantor’s “Ueber eine elementare Frage der Mannigfaltigkeitslehre”. 2019-08-23. (“O elementarnym pytaniu w teorii rozmaitości”, półautomatyczne tłumaczenie z niemieckiego na angielski)
Na podstawie artykułu: "Twierdzenie Cantora" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy