toitekomplekt komplekti A on A kõigi alamhulkade kogu. Kui töötada piiratud seatud koos n Üks küsimus, mida me võiksime küsida, on: „Kui palju elemente on võimsuskomplektis A? ” Näeme, et vastus sellele küsimusele on 2n ja tõestage matemaatiliselt, miks see tõsi on.
Mustri vaatlus
Otsime mustrit, jälgides elementide arvu toitekomplektis A, kus A on n elemendid:
- Kui A = {} (tühi komplekt), siis A pole elemente, kuid P (A) = {{}}, ühe elemendiga komplekt.
- Kui A = {a}, siis A on üks element ja P (A) = {{}, {a}}, kahe elemendiga komplekt.
- Kui A = {a, b}, siis A koosneb kahest elemendist ja P (A) = {{}, {a}, {b}, {a, b}}, kahe elemendiga komplekt.
Kõigis neis olukordades on seda lihtne näha komplekti väikese arvu elementidega, mida on piiratud arvu korral n elemendid sisse A, siis toitekomplekt Lk (A) on 2n elemente. Kuid kas see muster jätkub? Just seetõttu, et muster vastab tõele n = 0, 1 ja 2 ei tähenda tingimata, et muster vastab tõele kõrgemate väärtuste korral n.
Kuid see muster jätkub. Näitamaks, et see tõepoolest nii on, kasutame tõendit sissejuhatuse kaudu.
Tõestus induktsiooni teel
Induktsiooni abil tõestamine on kasulik kõigi naturaalarvude väidete tõestamiseks. Selle saavutame kahes etapis. Esimese sammuna kinnistame oma tõestuse, näidates tõese avalduse esimese väärtuse jaoks n mida me soovime kaaluda. Meie tõestuse teine samm on eeldada, et avaldus kehtib n = k, ja näitavad, et see tähendab, et väide kehtib n = k + 1.
Veel üks tähelepanek
Tõendite koostamiseks vajame veel ühte tähelepanekut. Ülaltoodud näidetest näeme, et P ({a}) on P ({a, b}) alamhulk. {A} alamhulgad moodustavad täpselt poole {a, b} alamhulkadest. Kõigi {a, b} alamhulkade saamiseks saame elemendi b lisada igasse {a} alamhulka. See komplekti lisamine toimub liitkomplekti toimimise abil:
- Tühi komplekt U {b} = {b}
- {a} U {b} = {a, b}
Need on kaks uut elementi P ({a, b}), mis ei olnud P ({a}) elemendid.
Sarnast esinemist näeme ka P ({a, b, c}) korral. Alustame nelja P-komplektiga ({a, b}) ja igasse neist lisame elemendi c:
- Tühi komplekt U {c} = {c}
- {a} U {c} = {a, c}
- {b} U {c} = {b, c}
- {a, b} U {c} = {a, b, c}
Ja kokku on P-s kokku kaheksa elementi ({a, b, c}).
Tõend
Oleme nüüd valmis tõestama väidet: “Kui komplekt A sisaldab n elemendid, siis võimsuse komplekt P (A) on 2n elemente. ”
Alustuseks märkame, et sissejuhatav tõendusmaterjal on juhtumite jaoks juba kinnitatud n = 0, 1, 2 ja 3. Eeldame sissejuhatuses, et see väide kehtib k. Nüüd laske komplekt A sisaldama n + 1 elementi. Me võime kirjutada A = B U {x} ja kaaluge, kuidas moodustada A.
Võtame kõik elemendid P (B), ja induktiivse hüpoteesi järgi on 2n nendest. Seejärel lisame elemendi x nendesse alamkomplektidesse x B, mille tulemuseks on veel 2n alamhulgad B. See ammendab jaotise Alamrühmade loetelu B, ja seega kokku on 2n + 2n = 2(2n) = 2n + 1 võimsuskomplekti elemendid A.