Cantorova věta

Z Wikipedie, otevřené encyklopedie

Cantorova věta je jedním ze silných výsledků teorie množin, který je přitom dosažen jejími nejjednoduššími prostředky. Její znění je následující:
Pro libovolnou množinu $x \,\!$ má potenční množina $\mathbb{P}(x)$ obsahující všechny podmnožiny množiny $x \,\!$ vyšší mohutnost, než $x \,\!$ .

[editovat] Význam a důsledky

Tato věta má zajímavé důsledky především pro nekonečné množiny: pro každou nekonečnou množinu existuje množina s větší mohutností (tj. množina ještě o hodně „nekonečnější“ než původní množina). Například množina všech množin přirozených čísel má větší mohutnost, než samotná množina přirozených čísel.

K důkazu sporem je použita obdoba Cantorovy diagonálmí metody - pro každé myslitelné vzájemně jednoznačné zobrazení množiny x na množinu $\mathbb{P}(x)$ lze sestrojit prvek množiny $\mathbb{P}(x)$ , který do tohoto zobrazení nepatří.

Cantorova věta a její důsledky pro nekonečné množiny stojí na poměrně silných předpokladech - potřebují axiomaticky zaručenou existenci nekonečné množiny a existenci potenční množiny $\mathbb{P}(x)$ ke každé množině, jak je tomu například v Zermelo-Fraenkelově teorii množin s jejím axiomem nekonečna a axiomem potence. Například v alternativní teorii množin není díky odlišné axiomatické soustavě podobný výsledek dosažitelný.

V klasické intuitivní teorii množin, která nestála na axiomatických základech, ale chápala množiny jako libovolné dobře definované soubory objektů, vedla Cantorova věta k takzvanému Cantorovu paradoxu: Pokud je $\mathbb{V}$ množina všech množin, pak množina $\mathbb{P}(\mathbb{V})$ všech jejích podmnožin má větší mohutnost než $\mathbb{V}$ , což je spor. Nepříjemné, že?

[editovat] Důkaz

Nechť $X \,\!$ je libovolná množina a $P(X) \,\!$ množina všech podmnožin $X \,\!$ (poteční množina). Tvrzení, že $P(X)\,\!$ má větší mohutnost než $X \,\!$ , je ekvivalentní tomu, že neexistuje zobrazení z $X \,\!$ do $P(X) \,\!$ , které by bylo na. Toto ukážeme sporem:

Nechť existuje zobrazení $f: X \rightarrow P(X)$ , které je na. Tedy pro každý prvek $A \in P(X)$ (A je množina!) existuje nějaké $x \in X$ tak, že $f(x) = A \,\!$ .

Nyní definujme podmnožinu $Y \subset X$

$Y = \{ x \in X: x \notin f(x) \}$ .

$Y$ obsahuje ty prvky $X$ , které nejsou ve svém obrazu daném zobrazením $f$ . $Y$ je zřejmě podmnožina $X$ a tedy musí existovat $y \in X$ tak, že $Y = f(y) \,\!$ . Mohou tedy nastat dvě možnosti:

$y \in Y$ , to je ale spor s definicí $Y$ , podle které $y \notin f(y)$ , ale $f(y) = Y \,\!$ ,
$y \notin Y$ , jenomže pak podle definice $Y \,\!$ musí být $y \in Y$ což je opět spor.