Hoeveel elementen zitten er in de Power Set?

De krachtset van een set EEN is de verzameling van alle subsets van A. Bij het werken met een eindige set met n elementen, een vraag die we ons kunnen stellen is: "Hoeveel elementen zijn er in de machtset 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 zullen een patroon zoeken door het aantal elementen in de machtset van te observeren EEN, waar EEN heeft n elementen:

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

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

Maar dit patroon gaat door. Om aan te tonen dat dit inderdaad het geval is, zullen we bewijs door inductie gebruiken.

Bewijs door inductie

Bewijs door inductie is nuttig om beweringen over alle natuurlijke getallen te bewijzen. We bereiken dit in twee stappen. Voor de eerste stap verankeren we ons bewijs door een echte verklaring te tonen voor de eerste waarde van n dat we willen overwegen. De tweede stap van ons bewijs is om aan te nemen dat de verklaring geldt n = k, en de show dat dit impliceert, houdt de verklaring in n = k + 1.

Nog een observatie

Om ons bewijs te helpen, hebben we nog een observatie nodig. Uit de bovenstaande voorbeelden kunnen we zien dat P (a) een subset is van P (a, b). De subsets van a vormen exact de helft van de subsets van a, b. We kunnen alle subsets van a, b verkrijgen door element b toe te voegen aan elk van de subsets van a. Deze set-toevoeging wordt bereikt door middel van de set-operatie van unie:

Set leeg U b = b
a U b = a, b

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

We zien een vergelijkbare gebeurtenis voor P (a, b, c). We beginnen met de vier sets van P (a, b), en aan elk van deze voegen we het element c toe:

Set leeg U c = c
a U c = a, c
b U c = b, c
a, b U c = a, b, c

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

Het bewijs

We zijn nu klaar om de verklaring te bewijzen: “Als de set EEN bevat n elementen, dan het vermogen VADER) heeft 2ⁿ elementen.”

We beginnen met op te merken dat het bewijs van inductie al verankerd is voor de gevallen n = 0, 1, 2 en 3. We veronderstellen door inductie dat de verklaring geldt k. Laat nu de set EEN bevatten n + 1 elementen. We kunnen schrijven EEN = B U x en overweeg hoe u subsets van kunt maken EEN.

We nemen alle elementen van P (B), en volgens de inductieve hypothese zijn er 2ⁿ van deze. Vervolgens voegen we het element x toe aan elk van deze subsets van B, resulterend in nog een 2ⁿ subsets van B. Dit put de lijst met subsets van uit B, en dus is het totaal 2ⁿ + 2ⁿ = 2 (2ⁿ) = 2^{n + 1} elementen van de power set van EEN.

Wetenschap