Câte elemente sunt în setul de alimentare?

set de putere a unui set A reprezintă colecția tuturor subseturilor de A. Când lucrați cu un finit a stabilit 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.

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 pentru seturi 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 valori mai mari de n.

Dar acest model continuă. Pentru a arăta că acesta este într-adevăr cazul, vom folosi dovada 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.

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ă prin operarea 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}) și 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}).

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ă reține declarația 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)și, prin ipoteza inductivă, există 2ⁿ din acestea. Apoi adăugăm elementul x la fiecare din aceste subseturi de Brezultând încă 2ⁿ subseturi de B. Aceasta epuizează lista subseturilor din B, și deci totalul este de 2ⁿ + 2ⁿ = 2(2ⁿ) = 2^{n + 1} elemente ale setului de putere din A.