Un insieme con n elementi ha 2^n sottoinsiemi: dimostrazione per induzione
Chiamo p(n) il numero dei sottoinsiemi. Voglio dimostrare che $p(n)=2^n$.
1) Verifico che sia $p(1)=2$, ed è vero.
2) suppongo che $p(n)=2^n$ sia vero, quindi dico che $p(n+1)=$...?
Mi sono bloccata qui. Il libro ovviamente continua con $p(n+1)=2p(n)=2*2^n=2^(n+1)$, che verifica il tutto, ma io non capisco il perché dei passaggi, o comunque perché non posso dire che $p(n+1)=2^n+2$ (è una somma, no?).
Scusate la domanda probabilmente idiota, ma credo sia meglio che questi dubbi vengano estirpati alla radice. Grazie mille!
1) Verifico che sia $p(1)=2$, ed è vero.
2) suppongo che $p(n)=2^n$ sia vero, quindi dico che $p(n+1)=$...?
Mi sono bloccata qui. Il libro ovviamente continua con $p(n+1)=2p(n)=2*2^n=2^(n+1)$, che verifica il tutto, ma io non capisco il perché dei passaggi, o comunque perché non posso dire che $p(n+1)=2^n+2$ (è una somma, no?).
Scusate la domanda probabilmente idiota, ma credo sia meglio che questi dubbi vengano estirpati alla radice. Grazie mille!
Risposte
Per ogni sottoinsieme che hai al passo \(n\) ne puoi formare due al passo \(n+1\): il sottoinsieme stesso oppure quello che ottieni aggiungendo l'\((n+1)\)-esimo elemento.
I sottoinsiemi che non contengono $ n+1 $ sono $ 2^n $.
Quali altri sottoinsiemi ci sono?
$ [n+1]uu A\\ Asube [1,2,3...n] $ ovvero $ 2^n $ sottoinsiemi, per ipotesi induttiva.
$ 2^n+2^n=2^n+1 $
La relazione è vera $ ∀nin N $ .
Quali altri sottoinsiemi ci sono?
$ [n+1]uu A\\ Asube [1,2,3...n] $ ovvero $ 2^n $ sottoinsiemi, per ipotesi induttiva.
$ 2^n+2^n=2^n+1 $
La relazione è vera $ ∀nin N $ .
Io trovo molto confusionario identificare il predicato da provare con il contenuto di tale predicato. Io imposterei nel modo seguente, che trovo molto più chiaro. Indicherò la cardinalità di un insieme $X$ con $|X|$ e con $\mathcal{P}(X)$ la famiglia di sottoinsiemi di $X$ (insieme delle parti).
Fissato un insieme $X$, definisco il predicato $p$[nota]Attenzione, il mio $p$ è diverso dal tuo![/nota]:
\[p(n): = \text{"$|X| = n$ $\implies |\mathcal{P}(X)| = 2^n$"}\]
Si vuole dimostrare che $\forall n \in \mathbb{N}, \ p(n)$ è vera.
Articoliamo il ragionamento in 2 passi:
[list=i]
[*:39x7gynx] Mostriamo che \(p(0)\) è vera[/*:m:39x7gynx]
[*:39x7gynx] Mostriamo che \(p(n) \implies p(n+1)\)[/*:m:39x7gynx][/list:o:39x7gynx]
Se facciamo ciò abbiamo concluso, perché per la i $p(0)$ è vera, e per la ii $p(0+1) = p(1)$ è vera, e avanti così.
Passo 1
\[p(0): = \text{"$|X| = 0$ $\implies |\mathcal{P}(X)| = 2^0 = 1$"}\]
Questo è senz'altro vero perché l'unico insieme con nessun elemento è l'insieme vuoto $\emptyset$ che ha solo un sottoinsieme: se stesso.
Passo 2
Assumiamo vera $p(n)$ per un fissato $n$ e mostriamo che da ciò segue che è vera anche $p(n+1)$.
Sia $X$ un insieme con cardinalità $n$, sia \(\star \not \in X\). Allora $Y := X \cup \{\star\}$ avrà cardinalità $n+1$. Seguendo il ragionamento indicato da Rigel avrai che:
\[\mathcal{P}(Y) = \bigcup_{A \in \mathcal{P}(X)} (A \cup (A \cup \{\star\})) = \mathcal{P}(X) \cup (\bigcup_{A \in \mathcal{P}(X)} (A \cup \{\star\}))\]
dove queste unioni sono tutte ovviamente disgiunte. Quindi hai che:
\[|\mathcal{P}(Y)| =|\mathcal{P}(X)| + |\mathcal{P}(X)| = 2\cdot |\mathcal{P}(X)|\]
Sfruttando l'ipotesi induttiva:
\[|\mathcal{P}(Y)| = 2\cdot |\mathcal{P}(X)| = 2 \cdot 2^n = 2^{n+1}\]
Ovvero $p(n+1)$ è vera, che conclude la dimostrazione.
Ovviamente questo è molto formale è nella pratica di tutti i giorni si può "accorciare", però ho voluto risponderti in questo modo perché mi era sembrato di sentirti un po' incerto non tanto riguardo al risultato in esame ma al principio di induzione in generale. Se questo non è il caso pazienza, magari aiuterà qualcun altro
Fissato un insieme $X$, definisco il predicato $p$[nota]Attenzione, il mio $p$ è diverso dal tuo![/nota]:
\[p(n): = \text{"$|X| = n$ $\implies |\mathcal{P}(X)| = 2^n$"}\]
Si vuole dimostrare che $\forall n \in \mathbb{N}, \ p(n)$ è vera.
Articoliamo il ragionamento in 2 passi:
[list=i]
[*:39x7gynx] Mostriamo che \(p(0)\) è vera[/*:m:39x7gynx]
[*:39x7gynx] Mostriamo che \(p(n) \implies p(n+1)\)[/*:m:39x7gynx][/list:o:39x7gynx]
Se facciamo ciò abbiamo concluso, perché per la i $p(0)$ è vera, e per la ii $p(0+1) = p(1)$ è vera, e avanti così.
Passo 1
\[p(0): = \text{"$|X| = 0$ $\implies |\mathcal{P}(X)| = 2^0 = 1$"}\]
Questo è senz'altro vero perché l'unico insieme con nessun elemento è l'insieme vuoto $\emptyset$ che ha solo un sottoinsieme: se stesso.
Passo 2
Assumiamo vera $p(n)$ per un fissato $n$ e mostriamo che da ciò segue che è vera anche $p(n+1)$.
Sia $X$ un insieme con cardinalità $n$, sia \(\star \not \in X\). Allora $Y := X \cup \{\star\}$ avrà cardinalità $n+1$. Seguendo il ragionamento indicato da Rigel avrai che:
\[\mathcal{P}(Y) = \bigcup_{A \in \mathcal{P}(X)} (A \cup (A \cup \{\star\})) = \mathcal{P}(X) \cup (\bigcup_{A \in \mathcal{P}(X)} (A \cup \{\star\}))\]
dove queste unioni sono tutte ovviamente disgiunte. Quindi hai che:
\[|\mathcal{P}(Y)| =|\mathcal{P}(X)| + |\mathcal{P}(X)| = 2\cdot |\mathcal{P}(X)|\]
Sfruttando l'ipotesi induttiva:
\[|\mathcal{P}(Y)| = 2\cdot |\mathcal{P}(X)| = 2 \cdot 2^n = 2^{n+1}\]
Ovvero $p(n+1)$ è vera, che conclude la dimostrazione.
Ovviamente questo è molto formale è nella pratica di tutti i giorni si può "accorciare", però ho voluto risponderti in questo modo perché mi era sembrato di sentirti un po' incerto non tanto riguardo al risultato in esame ma al principio di induzione in generale. Se questo non è il caso pazienza, magari aiuterà qualcun altro
Ringrazio moltissimo tutti e tre, credo proprio di aver capito!
Queste sono le mie primissime dimostrazioni per induzione (e non solo, ahimè), quindi mi sono un po' persa nella formalizzazione di Emar (passo 2...), però mi sembra di afferrato bene il concetto generale. Ci ritornerò tra qualche settimana, nella speranza di essere migliorata nel frattempo!
Queste sono le mie primissime dimostrazioni per induzione (e non solo, ahimè), quindi mi sono un po' persa nella formalizzazione di Emar (passo 2...), però mi sembra di afferrato bene il concetto generale. Ci ritornerò tra qualche settimana, nella speranza di essere migliorata nel frattempo!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo