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 $𝒮(X)$,$𝒫(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=𝒫(A)\equiv \mathrm{\forall }x(x\in B\iff 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 $𝒫(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$

$|𝒫(A)|=2^{|A|},$

gdzie $|𝒫(A)|,|A|$ oznaczają moc (liczbę kardynalną) zbioru, odpowiednio, $𝒫(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 $𝒫(A)$ jest większej mocy (ma „więcej elementów”).

Przykłady

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

• Szablon:Cytuj książkę

Linki zewnętrzne

• Algorytm odnajdujący wszystkie podzbiory zbioru stosowany w programowaniu