Twierdzenie 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. Konsekwencje tego faktu:

zbiór liczb rzeczywistych jest nieprzeliczalny – większy od zbioru liczb naturalnych^[1];
nie istnieje zbiór wszystkich zbiorów.

Dowód

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

B=\{x\in A:x\notin f(x)\}.

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

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

Wobec powyższego dla dowolnego elementu $m$ należącego do zbioru $A$ zachodzi:

m\notin f(m)\Rightarrow m\notin f(m)\wedge m\in B\Rightarrow f(m)\neq B,

m\in f(m)\Rightarrow m\in f(m)\wedge m\notin B\Rightarrow f(m)\neq B.

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

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

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

Zatem moc zbioru $A$ jest mniejsza niż jego zbioru potęgowego:

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

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

Historia

Cantor podał podobny dowód w pracy Über eine elementare Frage der Mannigfaltigkeitslehre^[2]^[3] (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$ jest funkcją na zbiorze $X,$ której wartościami są funkcje charakterystyczne podzbiorów zbioru $X,$ to funkcja charakterystyczna $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ż

problem stopu

Przypisy

↑ Cantora twierdzenie, [w:] Encyklopedia PWN [online], Wydawnictwo Naukowe PWN [dostęp 2022-10-14] .
↑ GeorgG. Cantor GeorgG., Ueber eine elementare Frage der Mannigfaltigkeitslehre, „Jahresbericht der Deutschen Mathematiker Vereinigung” (1), 1891, s. 75–78 .
↑ 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).

Linki zewnętrzne

Cantor’s theorem (ang.), Routledge Encyclopedia of Philosophy, rep.routledge.com [dostęp 2023-05-10].

[epwn-1] Cantora twierdzenie, [w:] Encyklopedia PWN [online], Wydawnictwo Naukowe PWN [dostęp 2022-10-14] .

[2] GeorgG. Cantor GeorgG., Ueber eine elementare Frage der Mannigfaltigkeitslehre, „Jahresbericht der Deutschen Mathematiker Vereinigung” (1), 1891, s. 75–78 .

[3] 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).

[1]

[2]

[3]