Câte elemente sunt în setul de alimentare?

Setul de putere al unui set A reprezintă colecția tuturor subseturilor de A. Când lucrați cu un set finit cu n elemente, o întrebare pe care ne-am putea-o pune este: „Câte elemente există în setul de putere A ?Vom vedea că răspunsul la această întrebare este 2ⁿ și dovedește matematic de ce acest lucru este adevărat.

Observarea modelului

Vom căuta un model prin observarea numărului de elemente din setul de putere al A, Unde A are n elemente:

• Dacă A = (setul gol), apoi A nu are elemente, dar P (A) = , un set cu un singur element.
• Dacă A = a, atunci A are un element și P (A) = , a, un set cu două elemente.
• Dacă A = a, b, atunci A are două elemente și P (A) = , a, b, a, b, un set cu două elemente.

În toate aceste situații, este simplu de a vedea seturile cu un număr mic de elemente care, dacă există un număr finit de n elemente în A, apoi setul de putere P (A) are 2n elemente. Dar acest model continuă? Doar pentru că un model este valabil pentru n = 0, 1 și 2 nu înseamnă neapărat că modelul este adevărat pentru valorile mai mari ale n.

Dar acest model continuă. Pentru a arăta că acesta este într-adevăr cazul, vom folosi dovada prin inducție.

Dovadă prin inducție

Dovada prin inducție este utilă pentru dovedirea enunțurilor referitoare la toate numerele naturale. Obținem acest lucru în doi pași. Pentru primul pas, ne ancorăm dovada arătând o afirmație adevărată pentru prima valoare a n pe care dorim să-l luăm în considerare. Al doilea pas al dovezii noastre este să presupunem că declarația ține n = k, și demonstrația că acest lucru implică menținerea declarației n = k + 1.

O altă observație

Pentru a ajuta la dovedirea noastră, vom avea nevoie de o altă observație. Din exemplele de mai sus, putem vedea că P (a) este un subset de P (a, b). Subseturile de a formează exact jumătate din subseturile de a, b. Putem obține toate subseturile de a, b adăugând elementul b la fiecare dintre subseturile din a. Această adăugare a unui set se realizează cu ajutorul funcționării setului de unire:

• Set gol U b = b
• a U b = a, b

Acestea sunt cele două elemente noi din P (a, b) care nu au fost elemente ale lui P (a).

Vedem o apariție similară pentru P (a, b, c). Începem cu cele patru seturi de P (a, b), iar la fiecare dintre acestea adăugăm elementul c:

• Set gol U c = c
• a U c = a, c
• b U c = b, c
• a, b U c = a, b, c

Și astfel încheiem cu un număr de opt elemente în P (a, b, c).

Dovada

Acum suntem gata să demonstrăm afirmația, „Dacă setul A conține n elemente, apoi setul de putere P (A) are 2ⁿ elemente.“

Începem prin a observa că dovada prin inducție a fost deja ancorată pentru cazuri n = 0, 1, 2 și 3. Presupunem prin inducție că afirmația ține k. Acum lasă setul A conține n + 1 elemente. Putem scrie A = B U x și luați în considerare modul de formare a subseturilor din A.

Luăm toate elementele P (B), iar prin ipoteza inductivă există 2ⁿ din acestea. Apoi adăugăm elementul x la fiecare din aceste subseturi de B, rezultând alte 2ⁿ subseturi de B. Aceasta epuizează lista subseturilor din B, deci totalul este de 2ⁿ + 2ⁿ = 2 (2ⁿ) = 2^{n + 1} elemente ale setului de putere din A.