Hvor mange elementer er det i strømsettet?

conceptdraw.com

De kraftsett av et sett EN er samlingen av alle delmengder av A. Når du arbeider med en endelig sett med n elementer, et spørsmål vi kan stille er, hvor mange elementer er det i kraftsettet til EN ? Vi vil se at svaret på dette spørsmålet er 2 ⁿ og bevis matematisk hvorfor dette er sant.

Observasjon av mønsteret

Vi vil se etter et mønster ved å observere antall elementer i potensmengden til EN , hvor EN har n elementer:

• Hvis EN = { } (det tomme settet), deretter EN har ingen elementer men P (A) = { { } }, et sett med ett element.
• Hvis EN = {a}, da EN har ett element og P (A) = { { }, {a}}, et sett med to elementer.
• Hvis EN = {a, b}, deretter EN har to elementer og P (A) = { { }, {a}, {b}, {a,b}}, et sett med to elementer.

I alle disse situasjonene er det enkelt å se etter settene med et lite antall elementer som hvis det er et begrenset antall n elementer i EN , deretter strømmen satt P ( EN ) har 2 n elementer. Men fortsetter dette mønsteret? Bare fordi et mønster er sant for n = 0, 1 og 2 betyr ikke nødvendigvis at mønsteret er sant for høyere verdier av n .

Men dette mønsteret fortsetter. For å vise at dette faktisk er tilfelle, vil vi bruke bevis ved induksjon.

Bevis ved induksjon

Bevis ved induksjon er nyttig for å bevise utsagn om alle de naturlige tallene. Dette oppnår vi i to trinn. For det første trinnet forankrer vi beviset vårt ved å vise et sant utsagn for den første verdien av n som vi ønsker å vurdere. Det andre trinnet i beviset vårt er å anta at utsagnet holder for n = k , og showet som dette innebærer at uttalelsen gjelder n = k + 1.

En annen observasjon

For å hjelpe med beviset vårt, trenger vi en annen observasjon. Fra eksemplene ovenfor kan vi se at P({a}) er en delmengde av P({a, b}). Delmengdene til {a} utgjør nøyaktig halvparten av delmengdene til {a, b}. Vi kan få alle delmengdene til {a, b} ved å legge til elementet b til hver av delmengdene til {a}. Dette settetilføyelsen oppnås ved hjelp av settedriften til union:

• Tomt sett U {b} = {b}
• {a} U {b} = {a, b}

Dette er de to nye elementene 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 settene av P({a, b}), og til hver av disse legger vi elementet c:

• Tomt sett U {c} = {c}
• {a} U {c} = {a, c}
• {b} U {c} = {b, c}
• {a, b} U {c} = {a, b, c}

Og så ender vi opp med totalt åtte elementer i P({a, b, c}).

Beviset

Vi er nå klare til å bevise påstanden, Hvis settet EN inneholder n elementer, deretter kraftsettet P( A) har 2 ⁿ elementer.

Vi begynner med å merke oss at beviset ved induksjon allerede er forankret for sakene n = 0, 1, 2 og 3. Vi antar ved induksjon at utsagnet holder for k . La nå settet EN inneholde n + 1 elementer. Vi kan skrive EN = B U {x}, og vurder hvordan du danner delsett av EN .

Vi tar alle elementer av P(B) , og ved den induktive hypotesen er det 2 ⁿ av disse. Deretter legger vi til elementet x til hver av disse delmengdene av B , noe som resulterer i ytterligere 2 ⁿ delmengder av B . Dette uttømmer listen over undergrupper av B , og så totalt er 2 ⁿ + 2 ⁿ = 2(2 ⁿ ) = 2 ^{n + 1}elementer i kraftsettet til EN .