WisFaq!

Aantal deelverzamelingen

Hallo, kan iemand mij helpen bij het begrijpen van deze theoretische opbouw van de formule voor het berekenen van het aantal deelverzamelingen?

g: D(A) $\to$ {0.1}tot de A : D $\to$ g(D) = f(d)

is een bijectie

D(A) = delenverzameling
A= een verzameling
f(d)=karakteristieke vergelijking

Hoe weetje nu dat dat een bijectie is?

Dank bij voorbaat,
Thomas

Thomas
5-9-2007

Antwoord

Een bijectie is een afbeelding van een verzameling V (hier D(A)) naar een verzameling W (hier {0,1}^A), op zo een manier dat elk element van V juist één beeld heeft in W, en elk element van W het beeld is van juist één element van V.

Dat moet je hier nagaan, dus: je neemt een willekeurig element uit D(A), dit is dus een deelverzameling van A. Argumenteer dat door de definitie van g, dit juist één beeld heeft in {0,1}^A. Dit volgt eigenlijk meteen uit de definitie van g met het gebruik van de karakteristieke functie.

En omgekeerd: neem een element van {0,1}^A, dat is dus een geordend A-tal van nullen en enen. Leg dan uit welke (unieke) deelverzameling van A, dit A-tal als beeld heeft.

Een bijectie heeft als eigenschap dat beide verzamelingen evenveel elementen hebben, zodat je hieruit kan besluiten dat een verzameling met A elementen, exact 2^A deelverzamelingen heeft.

Groeten,
Christophe.

Christophe
5-9-2007