Tekst źródłowy strony Twierdzenie Cantora

{{Inne znaczenia|twierdzenia o mocy zbioru potęgowego|[[twierdzenie Cantora (ujednoznacznienie)|inne twierdzenia noszące nazwisko Cantora]]}}

'''Twierdzenie Cantora''' – twierdzenie [[teoria mnogości|teorii mnogości]] udowodnione przez [[Georg Cantor|Georga Cantora]] mówiące, że każdy [[zbiór]] ma [[moc zbioru|moc]] mniejszą niż rodzina jego wszystkich podzbiorów, czyli jego [[zbiór potęgowy]]. Konsekwencje tego faktu:
* zbiór liczb rzeczywistych jest [[Zbiór nieprzeliczalny|nieprzeliczalny]] – większy od zbioru liczb naturalnych<ref name="epwn">{{Encyklopedia PWN |id = 3883069 |tytuł = Cantora twierdzenie |data dostępu = 2022-10-14}}</ref>;
* nie istnieje [[Paradoks zbioru wszystkich zbiorów|zbiór wszystkich zbiorów]].

== Dowód ==
Niech <math>f\colon A \to \mathcal{P}(A)</math> będzie dowolną [[Funkcja|funkcją]] z danego zbioru <math>A</math> w jego zbiór potęgowy <math>\mathcal{P}(A).</math> Zdefiniujmy zbiór <math>B</math> jako zbiór tych elementów zbioru <math>A,</math> które '''nie należą''' do swoich [[Obraz (matematyka)|obrazów]] w odwzorowaniu <math>f{:}</math>
: <math>B=\{x\in A : x\notin f(x)\}.</math>

Zbiór <math>B,</math> jako [[podzbiór]] zbioru <math>A,</math> jest oczywiście elementem zbioru potęgowego <math>A{:}</math>
: <math>B\subseteq A \Rightarrow B\in \mathcal{P}(A).</math>

Wobec powyższego dla dowolnego elementu <math>m</math> należącego do zbioru <math>A</math> zachodzi:
: <math>m \notin f(m) \Rightarrow m\notin f(m) \wedge m\in B \Rightarrow f(m)\neq B,</math>
: <math>m \in f(m) \Rightarrow m\in f(m) \wedge m\notin B \Rightarrow f(m)\neq B.</math>

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

Jednocześnie zbiór <math>A</math> nie może mieć mocy większej od swojego zbioru potęgowego <math>\mathcal{P}(A),</math> gdyż jest równoliczny z [[podzbiór|podzbiorem właściwym]] zbioru <math>\mathcal{P}(A).</math> Istnieje bowiem [[funkcja różnowartościowa|iniekcja]] z <math>A</math> w <math>\mathcal{P}(A),</math> przypisująca każdemu elementowi <math>x</math> jego [[Zbiór jednoelementowy|singleton]]:
: <math>g : A \ni x \mapsto \{x\} \in \mathcal{P}(A).</math>

Zatem moc zbioru <math>A</math> jest mniejsza niż jego zbioru potęgowego:
: <math>|A| <|\mathcal{P}(A)|.</math>

Powyższy dowód z uwagi na użyte wyrażenie <math>x\notin f(x)</math> jest [[metoda przekątniowa|rozumowaniem przekątniowym]].

== Historia ==
Cantor podał podobny dowód w pracy ''Über eine elementare Frage der Mannigfaltigkeitslehre''<ref>{{cytuj |autor = Georg Cantor |tytuł = Ueber eine elementare Frage der Mannigfaltigkeitslehre |czasopismo = Jahresbericht der Deutschen Mathematiker Vereinigung |numer = 1 |s = 75–78 |data = 1891}}</ref><ref>{{cytuj stronę |url = https://www.researchgate.net/publication/335364685_A_Translation_of_G_Cantor's_Ueber_eine_elementare_Frage_der_Mannigfaltigkeitslehre |tytuł = A Translation of G. Cantor’s “Ueber eine elementare Frage der Mannigfaltigkeitslehre” |autor = Google Translate™ |autor2 = DeepL™ |autor3 = Peter P. Jones |data = 2019-08-23}} (“O elementarnym pytaniu w teorii rozmaitości”, półautomatyczne tłumaczenie z niemieckiego na angielski).</ref> (1890/91) (gdzie zastosował [[Metoda przekątniowa|metodę przekątniową]], również dla dowodu [[zbiór nieprzeliczalny|nieprzeliczalności]] zbioru [[liczby rzeczywiste|liczb rzeczywistych]], którą wcześniej wykazywał innymi metodami). 

Dowód ów Cantor sformułował w terminach [[funkcja charakterystyczna zbioru|funkcji charakterystycznych zbioru]], nie podzbiorów zbioru, jak się go formułuje obecnie. Wykazał mianowicie, że jeśli <math>f</math> jest funkcją na zbiorze <math>X,</math> której wartościami są funkcje charakterystyczne podzbiorów zbioru <math>X,</math> to funkcja charakterystyczna <math>x\mapsto 1-(f(x))(x)</math> '''nie''' należy do [[Obraz (matematyka)|zbioru wartości]] <math>f.</math>

Podobny dowód pojawił się w ''[[Principia mathematica]]'' [[Alfred North Whitehead|Whiteheada]] i [[Bertrand Russell|Russella]] ([[1903]], rozdział 348), gdzie pokazuje się, że [[Funkcja zdaniowa|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 ==
{{Przypisy}}

== Linki zewnętrzne ==
* {{paywall}} ''[https://www.rep.routledge.com/articles/thematic/cantors-theorem/v-1 Cantor’s theorem]'' {{lang|en}}, [[Routledge Encyclopedia of Philosophy]], rep.routledge.com [dostęp 2023-05-10].

{{Liczby kardynalne}}

{{Kontrola autorytatywna}}

[[Kategoria:Twierdzenia teorii mnogości|Cantora]]
[[Kategoria:Liczby kardynalne]]