Koliko elementov je v naboru moči?

The nabor moči nabora A je zbirka vseh podvrste A. Pri delu s končnim nabor s n elementov, ki bi si jih lahko zastavili je, »koliko elementov je v naboru moči A? " Videli bomo, da je odgovor na to vprašanje 2ⁿ in matematično dokazati, zakaj je to res.

Vzorec bomo iskali tako, da bomo opazovali število elementov v naboru moči A, kje A je n elementi:

• Če A = {} (prazen niz), torej A nima elementov ampak P (A) = {{}}, niz z enim elementom.
• Če A = {a}, torej A ima en element in P (A) = {{}, {a}} niz z dvema elementoma.
• Če A = {a, b}, torej A ima dva elementa in P (A) = {{}, {a}, {b}, {a, b}}, niz z dvema elementoma.

V vseh teh situacijah je enostavno videti kompleti z majhnim številom elementov, ki jih, če obstaja končno število n elementi v A, nato nastavite moč P (A) ima 2n elementi. A se ta vzorec nadaljuje? Samo zato, ker vzorec velja za n = 0, 1 in 2 ne pomeni nujno, da vzorec velja za višje vrednosti n.

Toda ta vzorec se še vedno nadaljuje. Če želimo pokazati, da je res tako, bomo uporabili dokaz z indukcijo.

Dokazovanje z indukcijo je koristno za dokazovanje trditev o vseh naravnih številkah. To dosežemo v dveh korakih. Za prvi korak zasidramo svoj dokaz s prikazom resnične izjave za prvo vrednost n ki jih želimo upoštevati. Drugi korak našega dokazila je domneva, da izjava velja n = k, in kažejo, da to pomeni, da izjava drži n = k + 1.

Za lažje dokazovanje bomo potrebovali še eno opazovanje. Iz zgornjih primerov lahko razberemo, da je P ({a}) podvrsta P ({a, b}). Podmnožice {a} tvorijo natančno polovico podskupin {a, b}. Vse podmnožice {a, b} lahko pridobimo tako, da elementu b dodamo vsako podvrsto {a}. Ta dodatek niza se izvede s pomočjo nastavljenega delovanja zveze:

• Prazen niz U {b} = {b}
• {a} U {b} = {a, b}

To sta dva nova elementa v P ({a, b}), ki nista bila elementa P ({a}).

Podoben pojav vidimo pri P ({a, b, c}). Začnemo s štirimi nizi P ({a, b}) in vsakemu od njih dodamo element c:

• Prazen niz U {c} = {c}
• {a} U {c} = {a, c}
• {b} U {c} = {b, c}
• {a, b} U {c} = {a, b, c}

In tako zaključimo s skupno osmimi elementi v P ({a, b, c}).

Zdaj smo pripravljeni dokazati izjavo: "Če je nabor A vsebuje n elementi, nato pa nabor moči P (A) ima 2ⁿ elementi. "

Začnemo z ugotovitvijo, da je dokaz z indukcijo že zasidran za primere n = 0, 1, 2 in 3. Domnevamo z indukcijo, za katero velja izjava k. Zdaj pustite komplet A vsebujejo n + 1 element. Lahko pišemo A = B U {x} in razmislite, kako oblikovati podmnožice A.

Vzamemo vse elemente P (B)in po induktivni hipotezi obstajata 2ⁿ teh. Nato dodamo element x vsaki od teh podskupin B, kar ima za posledico še 2ⁿ podvrsti B. To izčrpa seznam podskupin B, in tako je skupno 2ⁿ + 2ⁿ = 2(2ⁿ) = 2^{n + 1} elementi nabora moči A.