Quanti elementi ci sono nel set di alimentazione?
Il set di potenza di un insieme UN è la raccolta di tutti i sottoinsiemi di A. Quando si lavora con un finito impostare insieme a n elementi, una domanda che potremmo porci è: quanti elementi ci sono nell'insieme di potere di UN ? Vedremo che la risposta a questa domanda è 2 n e dimostrare matematicamente perché questo è vero.
Osservazione del modello
Cercheremo uno schema osservando il numero di elementi nell'insieme di potenze di UN , dove UN ha n elementi:
- Se UN = { } (l'insieme vuoto), quindi UN non ha elementi ma PAPÀ) = { { } }, un insieme con un elemento.
- Se UN = {a}, allora UN ha un elemento e PAPÀ) = { { }, {a}}, un insieme con due elementi.
- Se UN = {a, b}, allora UN ha due elementi e PAPÀ) = { { }, {a}, {b}, {a,b}}, un insieme con due elementi.
In tutte queste situazioni, è facile da vedere imposta con un piccolo numero di elementi che se c'è un numero finito di n elementi in UN , quindi la potenza impostata P ( UN ) ha 2 n 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 è effettivamente il caso, useremo la dimostrazione per induzione.
Dimostrazione per induzione
La dimostrazione per induzione è utile per dimostrare 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 vogliamo considerare. Il secondo passo della nostra dimostrazione è assumere che l'affermazione valga n = K , e la dimostrazione che ciò implica che l'affermazione vale n = K + 1.
Un'altra osservazione
Per aiutare nella nostra dimostrazione, avremo bisogno di un'altra osservazione. Dagli esempi sopra, 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 somma di insiemi si ottiene mediante l'operazione di unione degli insiemi:
- Insieme 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 insiemi di P({a, b}), e ad ognuno di questi aggiungiamo l'elemento c:
- Insieme 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
Siamo ora pronti per dimostrare l'affermazione, Se l'insieme UN contiene n elementi, quindi il set di potenza PAPÀ) ha 2 n elementi.
Cominciamo col notare che la dimostrazione per induzione è già stata ancorata per i casi n = 0, 1, 2 e 3. Supponiamo per induzione che l'enunciato valga 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 per l'ipotesi induttiva, ci sono 2 n di questi. Quindi aggiungiamo l'elemento x a ciascuno di questi sottoinsiemi di B , risultando in un altro 2 n sottoinsiemi di B . Questo esaurisce l'elenco dei sottoinsiemi di B , quindi il totale è 2 n + 2 n = 2(2 n ) = 2 n + 1elementi dell'insieme di potere di UN .