Cik elementu ir komplektā?

barošanas komplekts komplekta A ir visu A apakšgrupu kolekcija. Strādājot ar ierobežotu komplekts ar n Elementi, viens jautājums, ko mēs varētu uzdot, ir: “Cik elementu ir enerģijas komplektā A? ” Mēs redzēsim, ka atbilde uz šo jautājumu ir 2ⁿ un matemātiski pierādiet, kāpēc tā ir taisnība.

Mēs meklēsim modeli, novērojot elementu skaitu jaudas komplektā A, kur A ir n elementi:

• Ja A = {} (tukšais komplekts), pēc tam A nav elementu, bet P (A) = {{}}, kopa ar vienu elementu.
• Ja A = {a}, tad A ir viens elements un P (A) = {{}, {a}}, komplekts ar diviem elementiem.
• Ja A = {a, b}, tad A ir divi elementi un P (A) = {{}, {a}, {b}, {a, b}}, komplekts ar diviem elementiem.

Visās šajās situācijās to ir viegli redzēt komplekti ar nelielu skaitu elementu, kas, ja ir ierobežots skaits n elementi A, tad jaudas komplekts Lpp (A) ir 2n elementi. Bet vai šis modelis turpinās? Tikai tāpēc, ka modelis ir taisnība n = 0, 1 un 2 nebūt nenozīmē, ka shēma ir taisnība augstākām vērtībām n.

Bet šis modelis joprojām turpinās. Lai parādītu, ka tas patiešām tā ir, mēs izmantosim pierādījumus ar indukcijas palīdzību.

Indukcijas pierādījums ir noderīgs, lai pierādītu apgalvojumus par visiem dabiskajiem skaitļiem. Mēs to panākam divos posmos. Pirmajā solī mēs nostiprinām pierādījumu, parādot patiesu paziņojumu par pirmo vērtību n kuru mēs vēlamies apsvērt. Otrais mūsu pierādīšanas solis ir pieņemt, ka paziņojums ir spēkā n = k, un liecina, ka tas nozīmē, ka apgalvojums ir spēkā n = k + 1.

Lai palīdzētu pierādījumos, mums būs vajadzīgs vēl viens novērojums. No iepriekšminētajiem piemēriem mēs redzam, ka P ({a}) ir P ({a, b}) apakškopa. {A} apakšgrupas veido tieši pusi no {a, b} apakšgrupām. Mēs varam iegūt visas {a, b} apakškopas, pievienojot elementu b katrai {a} apakškopai. Šis komplekta papildinājums tiek veikts, izmantojot savienības iestatīto darbību:

• Tukšs komplekts U {b} = {b}
• {a} U {b} = {a, b}

Šie ir divi jauni elementi P ({a, b}), kas nebija P ({a}) elementi.

Līdzīgu gadījumu mēs redzam arī P ({a, b, c}). Mēs sākam ar četrām P ({a, b}) kopām, un katram no tiem mēs pievienojam elementu c:

• Tukšs komplekts U {c} = {c}
• {a} U {c} = {a, c}
• {b} U {c} = {b, c}
• {a, b} U {c} = {a, b, c}

Tātad kopā P ({a, b, c}) ir astoņi elementi.

Mēs tagad esam gatavi pierādīt paziņojumu: “Ja komplekts A satur n elementi, pēc tam jaudas komplekts P (A) ir 2ⁿ elementi. ”

Sākumā atzīmējam, ka indukcijas pierādījumi jau ir nostiprināti šajos gadījumos n = 0, 1, 2 un 3. Mēs domājam, ka ar indukciju, uz kuru apgalvojums attiecas k. Tagad ļaujiet komplektam A saturēt n + 1 elementi. Mēs varam rakstīt A = B U {x} un apsveriet, kā izveidot A.

Mēs ņemam vērā visus elementus P (B), un pēc induktīvās hipotēzes ir 2ⁿ no šiem. Tad katram no šiem apakšgrupām pievienojam elementu x B, iegūstot vēl 2ⁿ apakšgrupas B. Tas izsmeļošas B, un tātad kopsumma ir 2ⁿ + 2ⁿ = 2(2ⁿ) = 2^{n + 1} enerģijas komplekta elementi A.