Hvor mange elementer er der i strømforsyningen?

Det strøm sæt af et sæt EN er samlingen af ​​alle undergrupper af A. Når du arbejder med en endelig sæt med n elementer, et spørgsmål, som vi måske stiller, er, ”Hvor mange elementer er der i kraftsættet af EN ?” Vi vil se, at svaret på dette spørgsmål er 2ⁿ og bevise matematisk, hvorfor dette er sandt.

Vi ser efter et mønster ved at observere antallet af elementer i kraftsættet af EN, hvor EN har n elementer:

• Hvis EN = {} (det tomme sæt), derefter EN har ingen elementer, men P (A) = {{}}, et sæt med et element.
• Hvis EN = {a}, derefter EN har et element og P (A) = {{}, {a}}, et sæt med to elementer.
• Hvis EN = {a, b}, derefter EN har to elementer og P (A) = {{}, {a}, {b}, {a, b}}, et sæt med to elementer.

I alle disse situationer er det let at se efter sæt med et lille antal elementer, der, hvis der er et endeligt antal på n elementer i EN, derefter strømforsyningen P (EN) har 2n elementer. Men fortsætter dette mønster? Bare fordi et mønster er sandt for n = 0, 1 og 2 betyder ikke nødvendigvis, at mønsteret er sandt for højere værdier af n.

Men dette mønster fortsætter. For at vise, at dette virkelig er tilfældet, bruger vi bevis ved induktion.

Bevis ved induktion er nyttigt til at bevise udsagn om alle de naturlige tal. Vi opnår dette i to trin. For det første trin forankrer vi vores bevis ved at vise en sand erklæring for den første værdi af n som vi ønsker at overveje. Det andet trin i vores bevis er at antage, at erklæringen gælder n = k, og viser, at dette indebærer, at udsagnet gælder n = k + 1.

For at hjælpe med vores bevis, har vi brug for en anden observation. Fra eksemplerne ovenfor kan vi se, at P ({a}) er en undergruppe af P ({a, b}). Delmængderne af {a} udgør nøjagtigt halvdelen af ​​undergrupperne til {a, b}. Vi kan få alle delmængderne af {a, b} ved at tilføje elementet b til hver af delmængderne af {a}. Denne sættilsætning opnås ved hjælp af den indstillede drift af unionen:

• Tom sæt U {b} = {b}
• {a} U {b} = {a, b}

Dette er de to nye elementer i P ({a, b}), som ikke var elementer i P ({a}).

Vi ser en lignende forekomst for P ({a, b, c}). Vi starter med de fire sæt P ({a, b}), og til hvert af disse tilføjer vi elementet c:

• Tom sæt U {c} = {c}
• {a} U {c} = {a, c}
• {b} U {c} = {b, c}
• {a, b} U {c} = {a, b, c}

Og så ender vi med i alt otte elementer i P ({a, b, c}).

Vi er nu klar til at bevise udsagnet, "Hvis sættet EN indeholder n elementer, derefter strømforsyningen P (A) har 2ⁿ elementer.”

Vi begynder med at bemærke, at beviset ved induktion allerede er forankret i sagerne n = 0, 1, 2 og 3. Vi antager ved induktion, at erklæringen gælder k. Lad nu sættet EN indeholde n + 1 elementer. Vi kan skrive EN = B U {x}, og overvej, hvordan du opretter undergrupper af EN.

Vi tager alle elementer af P (B), og ved den induktive hypotese er der 2ⁿ af disse. Derefter tilføjer vi elementet x til hver af disse undergrupper af B, hvilket resulterer i yderligere 2ⁿ undergrupper af B. Dette udtømmer listen med undergrupper af B, og det samlede beløb er således 2ⁿ + 2ⁿ = 2(2ⁿ) = 2^{n + 1} elementer i kraftsættet af EN.