Koliko je elemenata u skupu snage?

skup snage od skupa je zbirka svih podskupova A. Kad radite s konačnim set s n elemenata, jedno pitanje koje bismo mogli postaviti je: „Koliko elemenata ima u skupu snage ?” Vidjet ćemo da je odgovor na ovo pitanje 2ⁿ i matematički dokazati zašto je to istina.

Potražit ćemo obrazac promatrajući broj elemenata u skupu snage , gdje ima n elementi:

• Ako = {} (prazan skup), dakle nema elemenata ali P (A) = {{}}, skup s jednim elementom.
• Ako = {a}, dakle ima jedan element i P (A) = {{}, {a}}, skup s dva elementa.
• Ako = {a, b}, dakle ima dva elementa i P (A) = {{}, {a}, {b}, {a, b}}, skup s dva elementa.

U svim je tim situacijama jednostavno tražiti setovi s malim brojem elemenata koji ako postoje konačni broj n elementi u , a zatim postavljena snaga P () ima 2n elementi. No, nastavlja li se ovaj obrazac? Samo zato što uzor vrijedi n = 0, 1 i 2 ne znači nužno da je uzorak istinit za veće vrijednosti od n.

Ali ovaj se obrazac i dalje nastavlja. Da bismo pokazali da je to stvarno slučaj, upotrijebit ćemo dokaz indukcijom.

Dokazivanje indukcijom korisno je za dokazivanje tvrdnji koje se tiču ​​svih prirodnih brojeva. To postižemo u dva koraka. Za prvi korak zasidramo svoj dokaz pokazujući istinitu izjavu za prvu vrijednost n koje želimo razmotriti. Drugi je korak našeg dokazanja pretpostavka da izjava vrijedi n = k, i pokazuju da to podrazumijeva da se izjava drži n = k + 1.

Za pomoć u našem dokazu trebat će nam još jedno promatranje. Iz gornjih primjera vidimo da je P ({a}) podskup P ({a, b}). Podskupovi {a} tvore tačno polovinu podskupina {a, b}. Sve podskupove {a, b} možemo dobiti dodavanjem elementa b u svaku od podskupova {a}. Ovaj skup dodavanja ostvaruje se pomoću zadate operacije spajanja:

• Prazan set U {b} = {b}
• {a} U {b} = {a, b}

Ovo su dva nova elementa u P ({a, b}) koji nisu bili elementi P ({a}).

Vidimo sličnu pojavu za P ({a, b, c}). Počinjemo s četiri skupa P ({a, b}), a svakom od njih dodamo element c:

• Prazan set U {c} = {c}
• {a} U {c} = {a, c}
• {b} U {c} = {b, c}
• {a, b} U {c} = {a, b, c}

I tako završimo s ukupno osam elemenata u P ({a, b, c}).

Sada smo spremni dokazati tvrdnju, "Ako je skup sadrži n elemenata, zatim skup snage P (A) ima 2ⁿ elementi."

Započinjemo primjenom da je dokaz indukcijom već bio usidren za slučajeve n = 0, 1, 2 i 3. Pretpostavljamo da je indukcija za koju se izjava odnosi k. Sad pustite set sadržati n + 1 elementa. Možemo pisati = B U {x} i razmislite kako formirati podskupove od .

Uzimamo sve elemente (P) B, a po induktivnoj hipotezi postoje 2ⁿ od ovih. Zatim dodamo element x svakom od tih podskupina B, što rezultira još 2ⁿ podvrsta B. Ovo iscrpljuje popis podskupova B, i tako je ukupno 2ⁿ + 2ⁿ = 2(2ⁿ) = 2^{n + 1} elementi skupa snage .