Hur många element finns i strömmen?

De strömförsörjning av en uppsättning EN är samlingen av alla undergrupper av A. När du arbetar med en finite uppsättning med n element, en fråga som vi kan ställa oss är: ”Hur många element finns det i kraftsättningen EN ?” Vi ser att svaret på denna fråga är 2ⁿ och bevisa matematiskt varför detta är sant.

Vi letar efter ett mönster genom att observera antalet element i kraften EN, var EN har n element:

• Om EN = {} (den tomma uppsättningen), sedan EN har inga element men P (A) = {{}}, en uppsättning med ett element.
• Om EN = {a}, då EN har ett element och P (A) = {{}, {a}}, en uppsättning med två element.
• Om EN = {a, b}, då EN har två element och P (A) = {{}, {a}, {b}, {a, b}}, en uppsättning med två element.

I alla dessa situationer är det enkelt att se efter uppsättningar med ett litet antal element som om det finns ett begränsat antal n element i EN, sedan strömmen P (EN) har 2n element. Men fortsätter detta mönster? Bara för att ett mönster är sant för n = 0, 1 och 2 betyder inte nödvändigtvis att mönstret är sant för högre värden på n.

Men detta mönster fortsätter. För att visa att detta verkligen är fallet kommer vi att använda bevis genom induktion.

Bevis genom induktion är användbart för att bevisa påståenden om alla naturliga siffror. Vi uppnår detta i två steg. För det första steget förankrar vi vårt bevis genom att visa ett riktigt uttalande för det första värdet på n som vi vill överväga. Det andra steget i vårt bevis är att anta att uttalandet gäller n = koch visa att detta innebär att uttalandet gäller n = k + 1.

För att hjälpa till med vårt bevis behöver vi en ny observation. Från exemplen ovan kan vi se att P ({a}) är en delmängd av P ({a, b}). Delmängderna av {a} bildar exakt hälften av delmängderna av {a, b}. Vi kan få alla delmängderna till {a, b} genom att lägga till elementet b till var och en av delmängderna av {a}. Denna settillägg åstadkoms med hjälp av den inställda driften av unionen:

• Tom uppsättning U {b} = {b}
• {a} U {b} = {a, b}

Dessa är de två nya elementen i P ({a, b}) som inte var delar av P ({a}).

Vi ser en liknande förekomst för P ({a, b, c}). Vi börjar med de fyra uppsättningarna av P ({a, b}), och till var och en av dessa lägger vi till elementet c:

• Tom uppsättning U {c} = {c}
• {a} U {c} = {a, c}
• {b} U {c} = {b, c}
• {a, b} U {c} = {a, b, c}

Och så slutar vi med totalt åtta element i P ({a, b, c}).

Vi är nu redo att bevisa uttalandet, "Om uppsättningen EN innehåller n element, sedan strömmen P (A) har 2ⁿ element.”

Vi börjar med att notera att beviset genom induktion redan har förankrats för fallen n = 0, 1, 2 och 3. Vi antar genom induktion att uttalandet gäller k. Låt nu uppsättningen EN innehålla n + 1 element. Vi kan skriva EN = B U {x}, och överväga hur du skapar delmängder av EN.

Vi tar alla delar av P (B)och genom den induktiva hypotesen finns det 2ⁿ av dessa. Sedan lägger vi till elementet x till var och en av dessa delmängder av B, vilket resulterar i ytterligare 2ⁿ delmängder av B. Detta uttömmer listan med undergrupper av Boch så är summan 2ⁿ + 2ⁿ = 2(2ⁿ) = 2^{n + 1} delar av kraftsättningen av EN.