Machtsverzameling

De machtsverzameling van een verzameling ${\displaystyle S}$, aangegeven door ${\displaystyle {\mathcal {P}}(S)}$ of ${\displaystyle 2^{S}}$, is de verzameling van alle deelverzamelingen van ${\displaystyle S}$. Het symbool ${\displaystyle {\mathcal {P}}}$ staat voor 'power', het Engelse woord voor 'macht'. De definitie is dus:

${\displaystyle {\mathcal {P}}(S)=\{A\mid A\subseteq S\}}$

Voorbeeld

Zij ${\displaystyle S=\{a,b,c\}}$, dan is ${\displaystyle \{a,c\}}$ een deelverzameling van ${\displaystyle S}$, evenals ${\displaystyle \{a,b\}}$, ${\displaystyle S=\{b,c\}}$ etc. De complete lijst van deelverzamelingen van ${\displaystyle S}$ is:

1. ${\displaystyle \{\}=\varnothing }$ de lege verzameling
2. ${\displaystyle \{a\}}$
3. ${\displaystyle \{b\}}$
4. ${\displaystyle \{c\}}$
5. ${\displaystyle \{a,b\}}$
6. ${\displaystyle \{a,c\}}$
7. ${\displaystyle \{b,c\}}$
8. ${\displaystyle \{a,b,c\}=S}$

De machtsverzameling is de verzameling van deze deelverzamelingen:

${\displaystyle {\mathcal {P}}(S)=\{\ \{\},\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\ \}}$

Als ${\displaystyle n}$ het aantal elementen is in ${\displaystyle S}$, dus ${\displaystyle n=|S|}$, dan geldt voor de machtsverzameling:

${\displaystyle |{\mathcal {P}}(S)|=2^{n}}$

Dit is als volgt in te zien: elk element kan wel of niet tot een deelverzameling behoren. Dat geeft 2×2×2×...×2 mogelijkheden in totaal.

De machtsverzameling van een oneindige verzameling kan ook worden gedefinieerd. Het diagonaalbewijs van Cantor toont aan dat de kardinaliteit van de machtsverzameling van een oneindige verzameling altijd strikt groter is dan die van de verzameling zelf. De machtsverzameling is 'oneindiger' dan de oorspronkelijke verzameling.^[1] Tussen enerzijds de machtsverzameling van de natuurlijke getallen en anderzijds de reële getallen is een bijectie te vinden. Dit kan met behulp van oneindige rijen van nullen en enen. De twee machtsverzamelingen van twee verzamelingen met dezelfde kardinaliteit hebben ook dezelfde kardinaliteit.

De machtsverzameling van de lege verzameling is een singleton, met als enige element de lege verzameling.

De machtsverzameling van een verzameling ${\displaystyle S}$, met daarop de bewerkingen vereniging, doorsnede en complement, vormt het standaardvoorbeeld van een booleaanse algebra. Het is zelfs mogelijk om aan te tonen dat elke eindige booleaanse algebra isomorf is met een booleaanse algebra van een machtsverzameling voor een bepaalde verzameling ${\displaystyle S}$. Voor oneindige booleaanse algebra's geldt dit niet, maar wel geldt dat elke oneindige booleaanse algebra een deelalgebra van een machtsverzameling van een booleaanse algebra is.

Door ieder element van de machtsverzameling te associëren met zijn indicatorfunctie ontstaat een bijectie tussen ${\displaystyle {\mathcal {P}}(S)}$ en ${\displaystyle \{0,1\}^{S}}$, de verzameling van alle functies van ${\displaystyle S}$ naar het paar ${\displaystyle \{0,1\}}$. Dit verklaart de notatie ${\displaystyle 2^{S}}$. De relatie 'is een deelverzameling van' vormt op een machtsverzameling een partiële ordening.

Het binomium van Newton ${\displaystyle {n \choose k}}$ somt de kardinaliteit van de deelverzamelingen met ${\displaystyle k}$ elementen van een verzameling ${\displaystyle S}$ van ${\displaystyle n}$ elementen op. Dus is

${\displaystyle \left|2^{S}\right|=\sum _{k=0}^{n}{\binom {n}{k}}=2^{n}=2^{|S|}}$