napájení sady A je kolekce všech podmnožin A. Při práci s konečnou soubor s n prvků, jedna otázka, kterou bychom si mohli položit, zní: „Kolik prvků je v sadě moci A? “ Uvidíme, že odpověď na tuto otázku je 2n a matematicky dokázat, proč je to pravda.
Pozorování vzoru
Budeme hledat vzorek sledováním počtu prvků v sadě moci A, kde A má n Prvky:
- Li A = {} (prázdná množina) A nemá žádné prvky, ale P (A) = {{}}, sada s jedním prvkem.
- Li A = {a} A má jeden prvek a P (A) = {{}, {a}}, sada se dvěma prvky.
- Li A = {a, b} A má dva prvky a P (A) = {{}, {a}, {b}, {a, b}}, sada se dvěma prvky.
Ve všech těchto situacích je snadné to vidět sady s malým počtem prvků, které, pokud existuje konečný počet n prvky v A, pak napájení P (A) má 2n Prvky. Ale pokračuje tento vzorec? Jen proto, že vzor je pravdivý n = 0, 1 a 2 nemusí nutně znamenat, že vzor je platný pro vyšší hodnoty n.
Ale tento vzorec pokračuje. Abychom ukázali, že tomu tak skutečně je, použijeme důkaz indukcí.
Důkaz indukcí
Důkaz indukcí je užitečný pro prokázání tvrzení týkajících se všech přirozených čísel. Toho dosahujeme ve dvou krocích. V prvním kroku zakotvíme náš důkaz tím, že ukážeme pravdivé tvrzení pro první hodnotu
n které chceme zvážit. Druhým krokem našeho důkazu je předpokládat, že prohlášení platí n = ka ukázat, že z toho vyplývá, že prohlášení platí n = k + 1.Další pozorování
Abychom pomohli v našem důkazu, potřebujeme další pozorování. Z výše uvedených příkladů můžeme vidět, že P ({a}) je podmnožinou P ({a, b}). Podmnožiny {a} tvoří přesně polovinu podmnožin {a, b}. Všechny podmnožiny {a, b} můžeme získat přidáním prvku b do každé z podmnožin {a}. Toto přidání sady se provádí pomocí množinové operace spojení:
- Prázdná sada U {b} = {b}
- {a} U {b} = {a, b}
Toto jsou dva nové prvky v P ({a, b}), které nebyly prvky P ({a}).
Vidíme podobný výskyt pro P ({a, b, c}). Začneme čtyřmi sadami P ({a, b}) a ke každé z nich přidáme prvek c:
- Prázdná sada U {c} = {c}
- {a} U {c} = {a, c}
- {b} U {c} = {b, c}
- {a, b} U {c} = {a, b, c}
A tak v P ({a, b, c}) skončíme celkem osmi prvky.
Důkaz
Nyní jsme připraveni prokázat prohlášení: „Pokud je sada A obsahuje n prvky, pak napájení P (A) má 2n Prvky."
Začínáme tím, že důkaz indukcí již byl pro tyto případy ukotven n = 0, 1, 2 a 3. Předpokládáme, že to prohlášení platí k. Nyní nechte set A obsahovat n + 1 prvky. Můžeme psát A = B U {x} a zvažte, jak vytvořit podmnožiny A.
Bereme všechny prvky P (B)a podle induktivní hypotézy existují 2n z nich. Pak přidáme prvek x do každé z těchto podmnožin B, což má za následek další 2n podmnožiny B. Tím se vyčerpá seznam podmnožin B, a tak je celkem 2n + 2n = 2(2n) = 2n + 1 prvky energetické sady A.