Koliko elementov je v naboru moči?

conceptdraw.com

The nabor moči kompleta A je zbirka vseh podmnožic A. Pri delu s končnim set z n elementov, eno vprašanje, ki bi ga lahko vprašali, je, koliko elementov je v nizu moči A ? Videli bomo, da je odgovor na to vprašanje 2 ⁿ in matematično dokažite, zakaj je to res.

Opazovanje vzorca

Vzorec bomo iskali z opazovanjem števila elementov v naboru moči A , kje A ima n elementi:

• če A = { } (prazna množica), potem A nima elementov ampak P (A) = { { } }, množica z enim elementom.
• če A = {a}, torej A ima en element in P (A) = { { }, {a}}, množica z dvema elementoma.
• če A = {a, b}, torej A ima dva elementa in P (A) = { { }, {a}, {b}, {a,b}}, množica z dvema elementoma.

V vseh teh situacijah je preprosto videti kompleti z majhnim številom elementov, ki če jih je končno število n elementi v A , nato nastavite moč p ( A ) ima 2 n elementi. Toda ali se ta vzorec nadaljuje? Samo zato, ker vzorec velja za n = 0, 1 in 2 ne pomeni nujno, da vzorec velja za višje vrednosti n .

Toda ta vzorec se nadaljuje. Da bi dokazali, da je temu res tako, bomo uporabili dokaz z indukcijo.

Dokaz z indukcijo

Dokaz z indukcijo je uporaben za dokazovanje trditev o vseh naravnih številih. To dosežemo v dveh korakih. Za prvi korak naš dokaz zasidramo s prikazom prave izjave za prvo vrednost n ki jih želimo upoštevati. Drugi korak našega dokaza je predpostavka, da izjava velja za n = k in pokažite, da to pomeni, da izjava velja n = k + 1.

Še eno opazovanje

Za pomoč pri našem dokazu bomo potrebovali še eno opazovanje. Iz zgornjih primerov lahko vidimo, da je P({a}) podmnožica P({a, b}). Podmnožice {a} tvorijo točno polovico podmnožic {a, b}. Vse podmnožice {a, b} lahko dobimo tako, da vsaki podmnožici {a} dodamo element b. To seštevanje nabora je doseženo s pomočjo naborne operacije združevanja:

• Prazen niz U {b} = {b}
• {a} U {b} = {a, b}

To sta dva nova elementa v P({a, b}), ki nista bila elementa P({a}).

Podoben pojav vidimo za P({a, b, c}). Začnemo s štirimi nizi P({a, b}) in vsakemu dodamo element c:

• Prazen niz U {c} = {c}
• {a} U {c} = {a, c}
• {b} U {c} = {b, c}
• {a, b} U {c} = {a, b, c}

In tako končamo s skupaj osmimi elementi v P({a, b, c}).

Dokaz

Zdaj smo pripravljeni dokazati izjavo, Če niz A vsebuje n elementov, nato nabor moči P( A) ima 2 ⁿ elementi.

Začnemo z ugotovitvijo, da je bil dokaz z indukcijo že zasidran za primere n = 0, 1, 2 in 3. Z indukcijo predpostavimo, da trditev velja za k . Zdaj pa pustite set A vsebujejo n + 1 element. Lahko pišemo A = B U {x} in razmislite, kako oblikovati podmnožice A .

Vzamemo vse elemente P(B) , in po induktivni hipotezi sta 2 ⁿ teh. Nato vsaki od teh podmnožic dodamo element x B , kar ima za posledico še 2 ⁿ podskupine B . S tem je seznam podnaborov izčrpan B , in tako je skupno 2 ⁿ + 2 ⁿ = 2(2 ⁿ ) = 2 ^{n + 1}elementi nabora moči A .