Zbiór potęgowy

Elementy zbioru potęgowego {x, y, z}.

Zbiór potęgowy – dla danego zbioru $X$ zbiór wszystkich jego podzbiorów oznaczany symbolami ${\mathcal {S}}(X)$,${\mathcal {P}}(X)$ lub $2^{X}.$ W aksjomatycznej teorii mnogości Zermela-Fraenkla istnienie zbioru potęgowego postuluje aksjomat zbioru potęgowego.

To, że zbiór $B$ jest zbiorem potęgowym zbioru $A,$ można formalnie zapisać tak:

$B={\mathcal {P}}(A)\;\equiv \;\forall x\;(x\in B\Leftrightarrow x\subseteq A).$

Uwaga: Ściśle biorąc, dla danego zbioru nie można podać definicji jego zbioru potęgowego, która zaczynała by się: „jest to zbiór, który...”, bo definicja taka zakłada istnienie zbioru przed jego zdefiniowaniem, a takie definiowanie jest zakazane w aksjomatycznej teorii ZF. Można jedynie formalnie zdefiniować dla dwóch zbiorów, kiedy jeden z nich jest zbiorem potęgowym drugiego.

Moc zbioru potęgowego

Jeśli $A$ jest zbiorem $n$-elementowym, to ${\mathcal {P}}(A)$ ma dokładnie $2^{n}$ elementów. W szczególności, zbiór potęgowy zbioru pustego złożony jest tylko ze zbioru pustego, a więc ma $2^{0}=1$ element. Ogólniej, dla dowolnego zbioru $A$

$|{\mathcal {P}}(A)|=2^{|A|},$

gdzie $|{\mathcal {P}}(A)|,|A|$ oznaczają moc (liczbę kardynalną) zbioru, odpowiednio, ${\mathcal {P}}(A)$ i $A.$ Zbiór potęgowy zbioru liczb naturalnych jest mocy continuum, tzn. jest równoliczny ze zbiorem liczb rzeczywistych. Twierdzenie Cantora mówi, że dla każdego (skończonego albo nieskończonego) zbioru $A,$ jego zbiór ${\mathcal {P}}(A)$ jest większej mocy (ma „więcej elementów”).

Przykłady

• ${\mathcal {P}}(\varnothing )=\{\varnothing \}$
• ${\mathcal {P}}(\{\varnothing \})=\{\varnothing ,\{\varnothing \}\}$
• ${\mathcal {P}}(\{1,2,3\})=\{\varnothing ,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}$

Zobacz też

• następnik liczby porządkowej
• zbiór pusty

Bibliografia

• Aleksander Błaszczyk, Sławomir Turek: Teoria mnogości. Warszawa: Wydawnictwo Naukowe PWN, 2007, s. 7, 101. ISBN 978-83-01-15232-1.

Linki zewnętrzne

• Algorytm odnajdujący wszystkie podzbiory zbioru stosowany w programowaniu