Machtsverzameling

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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

\mathcal{P}(S)=\{A|A\subseteq S\}.
Voorbeeld

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

  1. { } = Ø, de lege verzameling)
  2. {a}
  3. {b}
  4. {c}
  5. {a,b}
  6. {a, c}
  7. {b, c}
  8. {a, b, c} = S

De machtsverzameling is nu de verzameling van deze verzamelingen, oftewel:

\mathcal{P}(S) =  \left\{\ \{\}, \{a\}, \{b\}, \{c\}, \{a,b\}, \{a, c\}, \{b, c\}, \{a,b,c\}\ \right\}.

Zij n = |S|, dus n is het aantal elementen in S, dan geldt voor de machtsverzameling: |\mathcal{P}(S)| = 2n. Dit is als volgt in te zien: bij elk element kun je kiezen of je dit element wel of niet opneemt in de deelverzameling; dat geeft 2×2×2×...×2 mogelijkheden in totaal.

Zodoende kun je (en computers doen dit) elke deelverzameling als n-bitjes weergeven, de 0 geeft aan dat een element niet in de deelverzameling zit en een 1 dat deze er wel inzit. In bovengenoemd voorbeeld correspondeert '000' (3 elementen, dus 3 bits) met de lege verzameling, en 101 met {a, c} en 111 met {a,b,c}. Er zijn zo uiteraard ook 2n zulke getallen te maken.

Het is wiskundig ook mogelijk om de machtsverzameling van een oneindige verzameling te beschouwen. 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). 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 machtsverzameling van een verzameling 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 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 \mathcal{P}(S) en {0,1}S, de verzameling van alle functies van S naar het paar {0,1}. Dit verklaart de notatie 2S.

De relatie "is een deelverzameling van" vormt op een machtsverzameling een partiële ordening.