Hoeveel elementen zitten er in de vermogensset?

conceptdraw.com

De vermogensset van een set EEN is de verzameling van alle deelverzamelingen van A. Bij het werken met een eindige set met n elementen, een vraag die we zouden kunnen stellen is: Hoeveel elementen zijn er in de machtsverzameling van? EEN ? We zullen zien dat het antwoord op deze vraag 2 . is ⁿ en wiskundig bewijzen waarom dit waar is.

Observatie van het patroon

We gaan op zoek naar een patroon door het aantal elementen in de machtsverzameling van te observeren EEN , waar EEN heeft n elementen:

• Als EEN = { } (de lege verzameling), dan EEN heeft geen elementen maar VADER) = { { } }, een verzameling met één element.
• Als EEN = {a}, dan EEN heeft één element en VADER) = { { }, {a}}, een verzameling met twee elementen.
• Als EEN = {a, b}, dan EEN heeft twee elementen en VADER) = { { }, {a}, {b}, {a,b}}, een verzameling met twee elementen.

In al deze situaties is het eenvoudig om te zien of sets met een klein aantal elementen dat als er een eindig aantal is n elementen in EEN , dan het vermogen P ( EEN ) heeft 2 n elementen. Maar zet dit patroon zich voort? Gewoon omdat een patroon waar is voor n = 0, 1 en 2 betekent niet noodzakelijk dat het patroon waar is voor hogere waarden van n .

Maar dit patroon zet zich voort. Om aan te tonen dat dit inderdaad het geval is, gebruiken we bewijs door inductie.

Bewijs door inductie

Bewijs door inductie is nuttig voor het bewijzen van uitspraken over alle natuurlijke getallen. Dit realiseren we in twee stappen. Voor de eerste stap verankeren we ons bewijs door een ware verklaring te tonen voor de eerste waarde van n die we willen overwegen. De tweede stap van ons bewijs is aan te nemen dat de bewering geldt voor: n = k , en de show dat dit impliceert dat de verklaring geldt voor n = k + 1.

Nog een observatie

Om te helpen bij ons bewijs, hebben we nog een observatie nodig. Uit de bovenstaande voorbeelden kunnen we zien dat P({a}) een deelverzameling is van P({a, b}). De deelverzamelingen van {a} vormen precies de helft van de deelverzamelingen van {a, b}. We kunnen alle deelverzamelingen van {a, b} verkrijgen door het element b toe te voegen aan elk van de deelverzamelingen van {a}. Deze set toevoeging wordt bereikt door middel van de set operatie van vereniging:

• Lege verzameling U {b} = {b}
• {a} U {b} = {a, b}

Dit zijn de twee nieuwe elementen in P({a, b}) die geen elementen waren van P({a}).

Een soortgelijk verschijnsel zien we voor P({a, b, c}). We beginnen met de vier verzamelingen van P({a, b}), en aan elk daarvan voegen we het element c toe:

• Lege verzameling U {c} = {c}
• {a} U {c} = {a, c}
• {b} U {c} = {b, c}
• {a, b} U {c} = {a, b, c}

En zo eindigen we met in totaal acht elementen in P({a, b, c}).

Het bewijs

We zijn nu klaar om de bewering te bewijzen, Als de set EEN bevat n elementen, dan de macht set VADER) heeft 2 ⁿ elementen.

We beginnen met op te merken dat het bewijs door inductie al is verankerd voor de gevallen n = 0, 1, 2 en 3. We veronderstellen door inductie dat de bewering geldt voor k . Laat nu de set EEN bevatten n + 1 elementen. We kunnen schrijven EEN = B U {x}, en bedenk hoe je deelverzamelingen van kunt vormen EEN .

We nemen alle elementen van P(B) , en volgens de inductieve hypothese zijn er 2 ⁿ van deze. Dan voegen we het element x toe aan elk van deze subsets van B , resulterend in nog eens 2 ⁿ subsets van B . Hiermee is de lijst met subsets van uitgeput B , en dus is het totaal 2 ⁿ + 2 ⁿ = 2(2 ⁿ ) = 2 ^{n + 1}elementen van de machtsverzameling van EEN .