Machtsverzameling

De machtsverzameling van een verzameling S, genoteerd als P(S) of 2^S, is de verzameling van alle deelverzamelingen van S.

Voorbeeld: Zij S = {A,B,C}, dan is {A,C} een deelverzameling van S, evenals {A,B} etc. De gehele lijst is:

{} (de lege verzameling)
{A}
{B}
{C}
{A, B}
{A, C}
{B, C}
{A, B, C} (S zelf)

De machtsverzameling is dus de verzameling van deze verzamelingen, oftewel:
P(S) = { {}, {A}, {B}, {C}, {A, B}, {A, C}, {B, C}, {A, B, C} }

Zij n = |S|, dus n is het aantal elementen in S, dan geldt voor de machtsverzameling: |P(S)| = 2ⁿ. Dit is als volgt in te zien: bij elk element kun je kiezen of je het 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 2ⁿ 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 cardinaliteit 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 de bewerkingen vereniging, doorsnede en complement, vormt het standaardvoorbeeld van een boolse algebra. Het is zelfs mogelijk om aan te tonen dat elke eindige boolse algebra isomorf is met een boolse algebra van een machtsverzameling voor een bepaalde verzameling S. Voor oneindige boolse algebra's geldt dit niet, maar wel geldt dat elke oneindige boolse algebra een subalgebra van een machtsverzameling van een boolse algebra is.

verzamelingenleer

Gourt Home::Gourt :: Machtsverzameling