Koľko prvkov je v súprave napájania?
The napájací set súboru A je súbor všetkých podmnožín A. Pri práci s konečným nastaviť s n prvkov, jedna otázka, ktorú by sme si mohli položiť, je, koľko prvkov je v množine sily A ? Uvidíme, že odpoveď na túto otázku je 2 n a matematicky dokázať, prečo je to pravda.
Pozorovanie vzoru
Vzor budeme hľadať pozorovaním počtu prvkov v mocnine A , kde A má n prvky:
- Ak A = { } (prázdna množina), teda A nemá žiadne prvky, ale P (A) = { { } }, množina s jedným prvkom.
- Ak A = {a} teda A má jeden prvok a P (A) = { { }, {a}}, množina s dvoma prvkami.
- Ak A = {a, b}, teda A má dva prvky a P (A) = { { }, {a}, {b}, {a,b}}, množina s dvoma prvkami.
Vo všetkých týchto situáciách je to jednoduché súpravy s malým počtom prvkov, že ak existuje konečný počet n prvky v A , potom nastavte výkon P ( A ) má 2 n prvkov. Ale pokračuje tento vzorec? Len preto, že vzor je pravdivý pre n = 0, 1 a 2 nevyhnutne neznamená, že vzor platí pre vyššie hodnoty n .
Ale tento vzorec pokračuje. Aby sme ukázali, že je to skutočne tak, použijeme dôkaz indukciou.
Dôkaz indukciou
Dôkaz indukciou je užitočný na dokazovanie tvrdení týkajúcich sa všetkých prirodzených čísel. Dosiahneme to v dvoch krokoch. V prvom kroku ukotvíme náš dôkaz ukázaním pravdivého tvrdenia pre prvú hodnotu n ktoré chceme zvážiť. Druhým krokom nášho dôkazu je predpokladať, že tvrdenie platí n = k , a ukážu, že z toho vyplýva, že vyhlásenie platí n = k + 1.
Ďalšie pozorovanie
Aby sme pomohli pri našom dôkaze, budeme potrebovať ďalšie pozorovanie. Z vyššie uvedených príkladov môžeme vidieť, že P({a}) je podmnožinou P({a, b}). Podmnožiny {a} tvoria presne polovicu podmnožín {a, b}. Všetky podmnožiny {a, b} môžeme získať pridaním prvku b do každej z podmnožín {a}. Toto sčítanie množiny sa vykonáva pomocou množinovej operácie zjednotenia:
- Prázdna množina U {b} = {b}
- {a} U {b} = {a, b}
Toto sú dva nové prvky v P({a,b}), ktoré neboli prvkami P({a}).
Podobný výskyt vidíme pre P({a, b, c}). Začneme štyrmi množinami P({a,b}) a ku každej z nich pridáme prvok c:
- Prázdna množina 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}).
Dôkaz
Teraz sme pripravení dokázať tvrdenie, Ak je súbor A obsahuje n prvky, potom výkonovú súpravu P(A) má 2 n prvkov.
Začneme konštatovaním, že dôkaz indukciou už bol pre prípady zakotvený n = 0, 1, 2 a 3. Indukciou predpokladáme, že tvrdenie platí k . Teraz nechajte súbor A obsahujú n + 1 prvok. Môžeme si písať A = B U {x} a zvážte, ako vytvoriť podmnožiny A .
Berieme všetky prvky P(B) a podľa indukčnej hypotézy sú 2 n z nich. Potom do každej z týchto podmnožín pridáme prvok x B , výsledkom čoho sú ďalšie 2 n podmnožiny B . Toto vyčerpáva zoznam podmnožín B , takže súčet je 2 n + 2 n = 2(2 n ) = 2 n + 1prvky výkonovej sady A .