Koľko prvkov je v súprave napájania?

sada napájania súboru je zbierka všetkých podskupín A. Pri práci s obmedzeným sada s n Prvok, ktorý by sme si mohli položiť, je: „Koľko prvkov je v súprave moci ? " Uvidíme, že odpoveď na túto otázku je 2ⁿ a matematicky dokázať, prečo je to pravda.

Budeme hľadať vzor pozorovaním počtu prvkov v sade moci , kde má n prvky:

• ak = {} (prázdna množina) nemá prvky, ale P (A) = {{}}, súprava s jedným prvkom.
• ak = {a} má jeden prvok a P (A) = {{}, {a}}, súprava s dvoma prvkami.
• ak = {a, b} má dva prvky a P (A) = {{}, {a}, {b}, {a, b}}, súprava s dvoma prvkami.

Vo všetkých týchto situáciách je ľahké sa o to presvedčiť súpravy s malým počtom prvkov, ktoré, ak existuje konečný počet n prvky v , potom sa nastaví napájanie P () má 2n prvky. Ale pokračuje tento model? Len preto, že vzor je pravdivý n = 0, 1 a 2 nemusí nevyhnutne znamenať, že vzor je platný pre vyššie hodnoty n.

Tento model však pokračuje. Na preukázanie toho, že tomu tak skutočne je, použijeme dôkaz indukciou.

Dôkaz indukciou je užitočný na preukázanie tvrdení týkajúcich sa všetkých prirodzených čísel. Dosahujeme to v dvoch krokoch. V prvom kroku zakotvíme náš dôkaz tým, že ukážeme pravdivé vyjadrenie prvej hodnoty n čo by sme chceli zvážiť. Druhým krokom nášho dôkazu je predpoklad, že vyhlásenie platí n = ka ukazujú, že z toho vyplýva, že vyhlásenie platí n = k + 1.

Aby sme pomohli pri dokazovaní, potrebujeme ďalšie pozorovanie. Z vyššie uvedených príkladov vidíme, že P ({a}) je podmnožinou P ({a, b}). Podmnožiny {a} tvoria presne polovicu podmnožín {a, b}. Môžeme získať všetky podmnožiny {a, b} pridaním prvku b do každej z podmnožín {a}. Toto pridanie množiny sa dosiahne pomocou nastavenej operácie únie:

• Prázdna súprava U {b} = {b}
• {a} U {b} = {a, b}

Toto sú dva nové prvky v P ({a, b}), ktoré neboli prvkami P ({a}).

Vidíme podobný výskyt pre P ({a, b, c}). Začneme štyrmi sadami P ({a, b}) a ku každej z nich pridáme prvok c:

• Prázdna súprava U {c} = {c}
• {a} U {c} = {a, c}
• {b} U {c} = {b, c}
• {a, b} U {c} = {a, b, c}

A tak skončíme s celkom ôsmimi prvkami v P ({a, b, c}).

Teraz sme pripravení dokázať vyhlásenie „Ak je sada obsahuje n prvkov, potom výkon P (A) má 2ⁿ prvky. "

Začneme konštatovaním, že dôkaz indukciou už bol v prípadoch zakotvený n = 0, 1, 2 a 3. Predpokladáme tým, že tvrdenie platí k. Teraz nechaj set obsahovať n + 1 prvky. Môžeme písať = B U {x} a zvážte, ako vytvoriť podmnožiny .

Berieme všetky prvky P (B)a podľa indukčnej hypotézy existujú 2ⁿ z nich. Potom pridáme prvok x do každej z týchto podmnožín B, čo vedie k ďalším 2ⁿ podmnožiny B. Týmto sa vyčerpá zoznam podmnožín B, a teda súčet 2ⁿ + 2ⁿ = 2(2ⁿ) = 2^{n + 1} prvky súpravy napájania z .