Zbiór potęgowy

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

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

${\displaystyle 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 ${\displaystyle A}$ jest zbiorem ${\displaystyle n}$-elementowym, to ${\displaystyle {\mathcal {P}}(A)}$ ma dokładnie ${\displaystyle 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 ${\displaystyle 2^{0}=1}$ element. Ogólniej, dla dowolnego zbioru ${\displaystyle A}$

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

gdzie ${\displaystyle |{\mathcal {P}}(A)|,|A|}$ oznaczają moc (liczbę kardynalną) zbioru, odpowiednio, ${\displaystyle {\mathcal {P}}(A)}$ i ${\displaystyle 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 ${\displaystyle A,}$ jego zbiór ${\displaystyle {\mathcal {P}}(A)}$ jest większej mocy (ma „więcej elementów”).

Przykłady

• ${\displaystyle {\mathcal {P}}(\varnothing )=\{\varnothing \}}$
• ${\displaystyle {\mathcal {P}}(\{\varnothing \})=\{\varnothing ,\{\varnothing \}\}}$
• ${\displaystyle {\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

Przypisy

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