Potenční množina

Potenční množina množiny ${\displaystyle X\,\!}$ (značí se ${\displaystyle {\mathcal {P}}(X)\,\!}$ nebo též ${\displaystyle 2^{X}\,\!}$), podle některých autorů též booleán ${\displaystyle {\mathcal {B}}(X)\,\!}$^[1], je taková množina, která obsahuje všechny podmnožiny množiny ${\displaystyle X\,\!}$.

Hasseův diagram potenční množiny ke trojprvkové množině {x, y, z}.

Formálně vyplývá existence potenční množiny k libovolné množině z axiomu potenční množiny.

Každá podmnožina potenční množiny ${\displaystyle {\mathcal {P}}(X)\,\!}$ se nazývá systém množin na množině X.

Příklad

• ${\displaystyle A=\{1,2,3\}\,\!}$
• ${\displaystyle {\mathcal {P}}(A)=\{\emptyset ,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}\,\!}$

Vlastnosti

Každá potenční množina obsahuje jako svůj prvek prázdnou množinu, tj.
${\displaystyle (\forall X)(\emptyset \in {\mathcal {P}}(X))\,\!}$

Potenční množina množiny ${\displaystyle X\,\!}$ obsahuje ${\displaystyle X\,\!}$ jako svůj prvek, tj.
${\displaystyle (\forall X)(X\in {\mathcal {P}}(X))\,\!}$

Na potenční množině je přirozeným způsobem definováno uspořádání pomocí relace „být podmnožinou“ ${\displaystyle \subseteq \,\!}$. Toto uspořádání není lineární - například množiny ${\displaystyle \{1,3\}\,\!}$ a ${\displaystyle \{2,3\}\,\!}$ z předchozího příkladu jsou neporovnatelné. Potenční množina spolu s tímto uspořádáním tvoří strukturu nazývanou potenční algebra, která má řadu zajímavých vlastností - jedná se například o úplný svaz.

Mohutnost potenční množiny

• Pokud je ${\displaystyle X\,\!}$ konečná množina a její mohutnost je ${\displaystyle |X|=n\,\!}$, pak mohutnost její potenční množiny je ${\displaystyle |{\mathcal {P}}(X)|=2^{n}\,\!}$. To lze odvodit například takto. Nechť množina ${\displaystyle M_{n}=\left\{k\;|\;\forall k\in \mathbb {N} ,k\leq n\right\}}$. Potenční množina množiny ${\displaystyle M_{n}}$ je množina, pro kterou očividně platí rekurentní vztah ${\displaystyle {\mathcal {P}}(M_{n})={\mathcal {P}}(M_{n-1}\cup \left\{n\right\})={\mathcal {P}}(M_{n-1})\cup \left\{\left\{n\right\}\cup p\;|\;\forall p\in {\mathcal {P}}(M_{n-1})\right\}}$. S použitím matematické indukce lze dojít k závěru, že spojujeme dvě stejně mohutné množiny, tj. mohutnost nové potenční množiny je ${\displaystyle 2^{n-1}+2^{n-1}=2^{n}}$.
• Pro nekonečné množiny platí podle Cantorovy věty, že mohutnost ${\displaystyle {\mathcal {P}}(X)\,\!}$ je ostře větší, než mohutnost ${\displaystyle X\,\!}$. Z toho mimo jiné vyplývá, že škála mohutností nekonečných množin je nekonečná, protože mohutnost ${\displaystyle {\mathcal {P}}({\mathcal {P}}(X))\,\!}$ je ostře větší, než mohutnost ${\displaystyle {\mathcal {P}}(X)\,\!}$ atd.

Potenční množiny v modelech teorie množin

Axiom teorie množin vyžaduje, aby soubor podmnožin nějaké množiny byl množinou, protože ale model nemusí obsahovat všechny možné podmnožiny, liší se v různých modelech i potenční množina nějaké množiny, a to i velikostí, ${\displaystyle X}$ a ${\displaystyle {\mathcal {P}}(X)}$ dokonce mohou mít při pohledu zvenku stejnou mohutnost (v modelu platí podle Cantorovy věty ${\displaystyle X\prec {\mathcal {P}}(X)}$, což ovšem pouze znamená, že uvnitř modelu neexistuje mezi oběma množinami bijekce, tj. zmíněná bijekce není součástí uvažovaného modelu). Příkladem takového „omezeného“ modelu je Gödelova konstrukce konstruovatelných množin.