Quanti elementi ci sono nel set di alimentazione?

Il set di potenza di un set UN è la raccolta di tutti i sottoinsiemi di A. Quando si lavora con un set finito con n elementi, una domanda che potremmo porci è: “Quanti elementi ci sono nel gruppo di potere di UN ?"Vedremo che la risposta a questa domanda è 2ⁿ e dimostrare matematicamente perché questo è vero.

Osservazione del modello

Cercheremo uno schema osservando il numero di elementi nel gruppo di potenza di UN, dove UN ha n elementi:

• Se UN = (il set vuoto), quindi UN non ha elementi ma PAPÀ) = , un set con un elemento.
• Se UN = a, quindi UN ha un elemento e PAPÀ) = , a, un set con due elementi.
• Se UN = a, b, quindi UN ha due elementi e PAPÀ) = , a, b, a, b, un set con due elementi.

In tutte queste situazioni, è semplice vedere per i set con un piccolo numero di elementi che se c'è un numero finito di n elementi in UN, quindi la potenza impostata P (UN) ha 2n elementi. Ma questo schema continua? Solo perché uno schema è vero per n = 0, 1 e 2 non significa necessariamente che il modello sia vero per valori più alti di n.

Ma questo schema continua. Per dimostrare che questo è davvero il caso, useremo la prova per induzione.

Prova per induzione

La prova per induzione è utile per dimostrare le affermazioni riguardanti tutti i numeri naturali. Raggiungiamo questo obiettivo in due passaggi. Per il primo passo, ancoriamo la nostra dimostrazione mostrando un'affermazione vera per il primo valore di n che desideriamo considerare. Il secondo passo della nostra dimostrazione è supporre che l'affermazione valga per n = K, e lo spettacolo che questo implica la dichiarazione vale per n = K + 1.

Un'altra osservazione

Per aiutarci nella nostra prova, avremo bisogno di un'altra osservazione. Dagli esempi precedenti, possiamo vedere che P (a) è un sottoinsieme di P (a, b). I sottoinsiemi di a formano esattamente la metà dei sottoinsiemi di a, b. Possiamo ottenere tutti i sottoinsiemi di a, b aggiungendo l'elemento b a ciascuno dei sottoinsiemi di a. Questa aggiunta di set viene eseguita per mezzo dell'operazione set di unione:

• Set vuoto U b = b
• a U b = a, b

Questi sono i due nuovi elementi in P (a, b) che non erano elementi di P (a).

Vediamo un'occorrenza simile per P (a, b, c). Iniziamo con i quattro set di P (a, b) e a ciascuno di questi aggiungiamo l'elemento c:

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

E così finiamo con un totale di otto elementi in P (a, b, c).

La prova

Ora siamo pronti a provare l'affermazione, "Se il set UN contiene n elementi, quindi il potere impostato PAPÀ) ha 2ⁿ elementi."

Cominciamo osservando che la prova per induzione è già stata ancorata per i casi n = 0, 1, 2 e 3. Supponiamo per induzione che l'affermazione valga per K. Ora lascia il set UN contenere n + 1 elementi Possiamo scrivere UN = B U x e considera come formare sottoinsiemi di UN.

Prendiamo tutti gli elementi di P (B), e dall'ipotesi induttiva, ci sono 2ⁿ di questi. Quindi aggiungiamo l'elemento x a ciascuno di questi sottoinsiemi di B, risultante in un altro 2ⁿ sottoinsiemi di B. Questo esaurisce l'elenco dei sottoinsiemi di B, e quindi il totale è 2ⁿ + 2ⁿ = 2 (2ⁿ) = 2^{n + 1} elementi del gruppo di potenza di UN.