Az tápkészlet egy készletből A az A összes részhalmaza. Amikor véges dolgozik készlet val vel n elemek, az egyik kérdés, amelyet feltehetünk: „Hány elem van a hatalomkészletben A ?” Látni fogjuk, hogy erre a kérdésre a válasz 2n és igazolja matematikailag, hogy miért igaz ez.
A minta megfigyelése
A mintát azáltal fogjuk megfigyelni, hogy megfigyeljük az elemek számát a A, hol A van n elemek:
- Ha A = {} (az üres készlet), akkor A nincs eleme, de P (A) = {{}}, egy elemmel rendelkező készlet.
- Ha A = {a}, akkor A egy elemmel rendelkezik és P (A) = {{}, {a}}, két elemből álló készlet.
- Ha A = {a, b}, akkor A két elemből áll és P (A) = {{}, {a}, {b}, {a, b}}, két elemből álló készlet.
Mindezen helyzetekben egyszerűen látni kell készletek kis számú elemmel, amelyek véges száma esetén n elemek benne A, majd a tápfeszültség beállítva P (A) 2n elemekkel. De folytatódik ez a minta? Csak azért, mert egy minta igaz n = 0, 1 és 2 nem feltétlenül jelenti azt, hogy a minta igaz a magasabb értékekre n.
De ez a minta folytatódik. Annak bizonyítására, hogy valóban ez a helyzet, indukciós bizonyítékot használunk.
Indukciós bizonyítás
Az indukcióval történő bizonyítás hasznos az összes természetes számra vonatkozó állítások bizonyításához. Ezt két lépésben érjük el. Az első lépésben rögzítjük bizonyítékunkat azáltal, hogy egy valós állítást mutatunk be az első értékére n amit figyelembe akarunk venni. Bizonyításunk második lépése annak feltételezése, hogy az állítás helytálló n = k, és azt mutatják, hogy ez magában foglalja az állítást n = k + 1.
Újabb megfigyelés
A bizonyítás megkönnyítéséhez újabb megfigyelésre van szükségünk. A fenti példákból láthatjuk, hogy P ({a}) a P ({a, b}) részhalmaza. A (z) {a} részhalmazok pontosan a {a, b} részhalmazainak felét alkotják. A {a, b} összes részhalmazát megszerezhetjük, ha a b elemet hozzáadjuk a {a} minden egyes részhalmazához. Ez a készletteljesítés az unió meghatározott műveletével valósul meg:
- Üres készlet U {b} = {b}
- {a} U {b} = {a, b}
Ez a P ({a, b}) két új eleme, amelyek nem voltak a P ({a}) elemei.
Hasonló előfordulást látunk P ({a, b, c}) esetében. A négy P halmazból ({a, b}) kezdjük, és mindegyikhez hozzáadjuk a c elemet:
- Üres készlet U {c} = {c}
- {a} U {c} = {a, c}
- {b} U {c} = {b, c}
- {a, b} U {c} = {a, b, c}
Így végül összesen nyolc elem van a P-ben ({a, b, c}).
A bizonyíték
Készen állunk, hogy bebizonyítsuk a következő állítást: „Ha a készlet A tartalmaz n elemeket, majd a tápegységet P (A) rendelkezik 2n elemek.”
Először azt vesszük észre, hogy az indukciós bizonyíték már rögzítve volt az esetekhez n = 0, 1, 2 és 3. Feltételezzük, hogy indukcióval az állítás érvényes k. Most hagyja a készüléket A tartalmaz n + 1 elem. Tudunk írni A = B U {x}, és fontolja meg a A.
Minden elemét figyelembe vesszük P (B), és az induktív hipotézis szerint vannak 2n Ezeknek a. Ezután hozzáadjuk az x elemet ezen alcsoportok mindegyikéhez B, ami további 2-et eredményezn alcsoportjai B. Ez kimeríti a B, és így az összeg 2n + 2n = 2(2n) = 2n + 1 A teljesítménykészlet elemei A.