Dimostrazione dell'Insieme delle parti
Buonasera, mentre leggevo un testo di analisi matematica, il cui primo capitolo è dedicato all'insiemistica e alla logica, mi sono imbattuto nell'insieme delle parti, esso è così definito:
Subito dopo si chiede di dimostrare che se \(X\) ha \(n\) elementi, allora \( \wp(X)\) ha \(2^n\) elementi.
Come procedere per questa dimostrazione?
Dato un insieme \(X\) , si chiama insieme delle parti, quell'insieme che ha per elementi tutti i sottoinsiemi di \(X\).
L'insieme delle parti si indica con \( \wp(X)\).
Subito dopo si chiede di dimostrare che se \(X\) ha \(n\) elementi, allora \( \wp(X)\) ha \(2^n\) elementi.
Come procedere per questa dimostrazione?
Risposte
Direi per induzione 
Innanzitutto, fatti un paio di esempi, partendo da insiemi con $n=0,1,2,3$ elementi, prova a scrivere esplicitamente l'insieme delle parti e constata che il fatto è vero. Ciò costituisce la base dell'induzione .
Dopodiché, analizza i casi concreti che hai già esaminato e cerca di capire come si può dimostrare il passo induttivo, i.e. come si può fare a provare che dal fatto che un insieme di $n$ elementi ha $2^n$ sottoinsiemi segue che un insieme di $n+1$ elementi ha $2^(n+1)$ sottoinsiemi.
Dopodiché, analizza i casi concreti che hai già esaminato e cerca di capire come si può dimostrare il passo induttivo, i.e. come si può fare a provare che dal fatto che un insieme di $n$ elementi ha $2^n$ sottoinsiemi segue che un insieme di $n+1$ elementi ha $2^(n+1)$ sottoinsiemi.
Grazie per i consigli, ho provato a scrivere questa proprietà in linguaggio matematico (non sono sicuro che sia giusto),
\( \forall n \in \mathbb{N} (X=\{\{k_0\},\{k_1\},\{k_2\},...,\{k_n\}\} \Longrightarrow \wp(X)=\{\{2^0\},\{2^1\},\{2^2\},...,\{2^n\}\}) \)
Dopodiché ho provato a fare il primo passo del procedimento di induzione, ovvero ho sviluppato per \( n=0,1,2,3 \)
\(n=0 \)
\(X= \emptyset \)
\(2^0=1 \)
\( \wp(X)=\{\emptyset\} \)
poi,
\(n=1 \)
\(X= \{1\} \)
\(2^1=2 \)
\( \wp(X)=\{\emptyset,\{1\}\} \)
poi,
\(n=2 \)
\(X= \{1,2\} \)
\(2^2=4 \)
\( \wp(X)=\{\emptyset,\{1\},\{2\},X\} \)
poi,
\(n=3 \)
\(X= \{1,2,3\} \)
\(2^3=8 \)
\( \wp(X)=\{\emptyset,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},X\} \)
\( \forall n \in \mathbb{N} (X=\{\{k_0\},\{k_1\},\{k_2\},...,\{k_n\}\} \Longrightarrow \wp(X)=\{\{2^0\},\{2^1\},\{2^2\},...,\{2^n\}\}) \)
Dopodiché ho provato a fare il primo passo del procedimento di induzione, ovvero ho sviluppato per \( n=0,1,2,3 \)
\(n=0 \)
\(X= \emptyset \)
\(2^0=1 \)
\( \wp(X)=\{\emptyset\} \)
poi,
\(n=1 \)
\(X= \{1\} \)
\(2^1=2 \)
\( \wp(X)=\{\emptyset,\{1\}\} \)
poi,
\(n=2 \)
\(X= \{1,2\} \)
\(2^2=4 \)
\( \wp(X)=\{\emptyset,\{1\},\{2\},X\} \)
poi,
\(n=3 \)
\(X= \{1,2,3\} \)
\(2^3=8 \)
\( \wp(X)=\{\emptyset,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},X\} \)
"Gregorius":
ho provato a scrivere questa proprietà in linguaggio matematico (non sono sicuro che sia giusto),
\( \forall n \in \mathbb{N} (X=\{\{k_0\},\{k_1\},\{k_2\},...,\{k_n\}\} \Longrightarrow \wp(X)=\{\{2^0\},\{2^1\},\{2^2\},...,\{2^n\}\}) \)
Così com'è scritta non significa quello che vuoi ed, anzi, è proprio sbagliata.
"Gregorius":
Dopodiché ho provato a fare il primo passo del procedimento di induzione, ovvero ho sviluppato per \( n=0,1,2,3 \)
\(n=0 \)
\(X= \emptyset \)
\(2^0=1 \)
\( \wp(X)=\{\emptyset\} \)
poi,
\(n=1 \)
\(X= \{1\} \)
\(2^1=2 \)
\( \wp(X)=\{\emptyset,\{1\}\} \)
poi,
\(n=2 \)
\(X= \{1,2\} \)
\(2^2=4 \)
\( \wp(X)=\{\emptyset,\{1\},\{2\},X\} \)
poi,
\(n=3 \)
\(X= \{1,2,3\} \)
\(2^3=8 \)
\( \wp(X)=\{\emptyset,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},X\} \)
E quindi tutto funziona... Ora ti manca il passo induttivo.
Così è scritto bene?
\(
\forall n \in \mathbb{N} (X=\{n\} \Longrightarrow \wp(X)=\{2^n\})
\)
Questa è l'implicazione universale che voglio dimostrare, per farlo sia l'ipotesi che la tesi devono essere soddisfate...
\(
\forall n \in \mathbb{N} (X=\{n\} \Longrightarrow \wp(X)=\{2^n\})
\)
Questa è l'implicazione universale che voglio dimostrare, per farlo sia l'ipotesi che la tesi devono essere soddisfate...
ipotesi:
\(
X=\{n\}
\)
tesi:
\(
\wp(X)=\{2^n\}
\)
No, stai facendo confusione ... confondi un insieme con la sua cardinalità (ovvero il numero dei suoi elementi, volgarmente parlando)
Tra parentesi graffe vanno messi solamente gli elementi di un insieme; in pratica stai dicendo che l'insieme $X$ è formato dal solo elemento $n$ mentre l'insieme $P(X)$ è formato dal solo elemento $2^n$
Quello che intendevi dire, probabilmente, era $|X|=n\ ->\ |P(X)|=2^n$ cioè dato un insieme con $n$ elementi, allora il suo insieme delle parti ha $2^n$ elementi.
Ti faccio notare però che questa è la tesi che devi dimostrare.
Cordialmente, Alex
Tra parentesi graffe vanno messi solamente gli elementi di un insieme; in pratica stai dicendo che l'insieme $X$ è formato dal solo elemento $n$ mentre l'insieme $P(X)$ è formato dal solo elemento $2^n$
Quello che intendevi dire, probabilmente, era $|X|=n\ ->\ |P(X)|=2^n$ cioè dato un insieme con $n$ elementi, allora il suo insieme delle parti ha $2^n$ elementi.
Ti faccio notare però che questa è la tesi che devi dimostrare.
Cordialmente, Alex
"axpgn":
No, stai facendo confusione ... confondi un insieme con la sua cardinalità (ovvero il numero dei suoi elementi, volgarmente parlando)
Tra parentesi graffe vanno messi solamente gli elementi di un insieme; in pratica stai dicendo che l'insieme $X$ è formato dal solo elemento $n$ mentre l'insieme $P(X)$ è formato dal solo elemento $2^n$
Quello che intendevi dire, probabilmente, era $|X|=n\ ->\ |P(X)|=2^n$ cioè dato un insieme con $n$ elementi, allora il suo insieme delle parti ha $2^n$ elementi.
Ti faccio notare però che questa è la tesi che devi dimostrare.
Cordialmente, Alex
Grazie mille, mi sfuggiva la notazione per la cardinalità degli insiemi.
Dunque l'implicazione universale diventa così:
\(
\forall n \in \mathbb{N} (|X|=n \Longrightarrow |\wp(X)|=2^n)
\)
ipotesi:
\(
|X|=n
\)
tesi:
\(
|\wp(X)|=2^n
\)
Come detto, un modo per dimostrarla è quello "per induzione" che consiste in due passi:
- il passo base che consiste nel dimostrare la verità dell'implicazione per il "primo della lista", in questo caso per $n=0$
- il passo induttivo che consiste nell'assumere per vera l'implicazione per un generico $n$ e sfruttando ciò, dimostrare che è vera per il successivo valore $n+1$
Cordialmente, Alex
- il passo base che consiste nel dimostrare la verità dell'implicazione per il "primo della lista", in questo caso per $n=0$
- il passo induttivo che consiste nell'assumere per vera l'implicazione per un generico $n$ e sfruttando ciò, dimostrare che è vera per il successivo valore $n+1$
Cordialmente, Alex
"axpgn":
Come detto, un modo per dimostrarla è quello "per induzione" che consiste in due passi:
- il passo base che consiste nel dimostrare la verità dell'implicazione per il "primo della lista", in questo caso per $n=0$
- il passo induttivo che consiste nell'assumere per vera l'implicazione per un generico $n$ e sfruttando ciò, dimostrare che è vera per il successivo valore $n+1$
Cordialmente, Alex
Non riesco a capire come fare...
Passo base:
Dobbiamo dimostrare che la proposizione è vera per "il primo della lista" cioè per $n=0$.
Qual è l'insieme che non ha elementi? L'insieme vuoto.
Quanti sottoinsiemi ha l'insieme vuoto? Solo uno, sé stesso.
Cosa dice la nostra proposizione in questo caso? Che la cardinalità dell'insieme vuoto deve essere $2^n=2^0=1$
Ok, fatto.
Passo induttivo:
Assumendo che la nostra proposizione sia vera per un generico insieme di cardinalità $n$, dobbiamo dimostrare che sia vera per un insieme di cardinalità $n+1$
Poniamo di avere un insieme $X$ di cardinalità $|X|=n$; se gli aggiungiamo un elemento, poniamo $z$, otteniamo un insieme $Y$ di cardinalità $|Y|=n+1$
Quanti sono i sottoinsiemi di $Y$? Cominciamo col notare che i sottoinsiemi di $Y$ o contengono $z$ o non lo contengono; ok?
Quelli che non lo contengono non sono altro che i sottoinsiemi di $X$ cioè $2^n$; d'accordo?
Quelli che contengono $z$ sono tanti quanto quelli che non lo contengono perché basta prendere questi ultimi e aggiungergli $z$ e quindi sono $2^n$.
In totale i sottoinsiemi di $Y$ sono $|P(Y)|=2^n+2^n=2*2^n=2^(n+1)$
CVD
Cordialmente, Alex
P.S.: Non citare interamente i messaggi (a maggior ragione se è quello precedente); quota solo la parte che eventualmente ti interessa ...
Dobbiamo dimostrare che la proposizione è vera per "il primo della lista" cioè per $n=0$.
Qual è l'insieme che non ha elementi? L'insieme vuoto.
Quanti sottoinsiemi ha l'insieme vuoto? Solo uno, sé stesso.
Cosa dice la nostra proposizione in questo caso? Che la cardinalità dell'insieme vuoto deve essere $2^n=2^0=1$
Ok, fatto.
Passo induttivo:
Assumendo che la nostra proposizione sia vera per un generico insieme di cardinalità $n$, dobbiamo dimostrare che sia vera per un insieme di cardinalità $n+1$
Poniamo di avere un insieme $X$ di cardinalità $|X|=n$; se gli aggiungiamo un elemento, poniamo $z$, otteniamo un insieme $Y$ di cardinalità $|Y|=n+1$
Quanti sono i sottoinsiemi di $Y$? Cominciamo col notare che i sottoinsiemi di $Y$ o contengono $z$ o non lo contengono; ok?
Quelli che non lo contengono non sono altro che i sottoinsiemi di $X$ cioè $2^n$; d'accordo?
Quelli che contengono $z$ sono tanti quanto quelli che non lo contengono perché basta prendere questi ultimi e aggiungergli $z$ e quindi sono $2^n$.
In totale i sottoinsiemi di $Y$ sono $|P(Y)|=2^n+2^n=2*2^n=2^(n+1)$
CVD
Cordialmente, Alex
P.S.: Non citare interamente i messaggi (a maggior ragione se è quello precedente); quota solo la parte che eventualmente ti interessa ...
Grazie Alex!
Io non ci sarei mai arrivato da solo... forse lo studio della matematica non fa per me...
Io non ci sarei mai arrivato da solo... forse lo studio della matematica non fa per me...
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo