Potenční množina: Porovnání verzí
Smazaný obsah Přidaný obsah
+Booleán |
m →Mohutnost potenční množiny: Přidáno odvození. značka: editace z Vizuálního editoru |
||
Řádek 27:
== Mohutnost potenční množiny ==
* Pokud je <math> X \,\! </math> konečná množina a její [[mohutnost]] je <math> |X| = n \,\! </math>, pak mohutnost její potenční množiny je <math> |\mathcal{P}(X)| = 2^n \,\! </math>. To lze odvodit například takto. Nechť množina <math>M_n = \left \{ k \; |\; \forall k \in \mathbb{N}, k \leq n \right \}</math>. Potenční množina množiny <math>M_n</math> je množina, pro kterou očividně platí rekurentní vztah <math> \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 \} </math>. 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 <math> 2^{n-1} + 2^{n-1} = 2^{n} </math>.
* Pro nekonečné množiny platí podle [[Cantorova věta|Cantorovy věty]], že mohutnost <math> \mathcal{P}(X) \,\! </math> je ostře větší, než mohutnost <math> X \,\! </math>. Z toho mimo jiné vyplývá, že škála mohutností nekonečných množin je nekonečná, protože mohutnost <math> \mathcal{P}(\mathcal{P}(X)) \,\! </math> je ostře větší, než mohutnost <math> \mathcal{P}(X) \,\! </math> atd.
| |||