Differenze tra le versioni di "Insieme delle parti"

Nessun cambiamento nella dimensione ,  12 anni fa
Sia ''n > 0'', e supponiamo l'asserto vero per ''n-1''. Cioè se ''S'' è un insieme tale che <math>|S| = n-1</math> allora <math>|\mathcal{P}(S)| = 2^{n-1}</math>.
 
Poiché adesso si ipotizza che <math>|S| = n > 0</math> necessariamente <math>S \neq \emptyset</math> e dovrà avere almeno un elemento. Sia <math>x_0</math> un elemento dell'insieme. Un qualunque sottoinsieme di ''TS'' può contenerlo o meno:
* I sottoinsiemi che non contengono <math>x_0</math>, sono sottoinsiemi di <math>S \backslash \{ x_0 \}</math>; poiché <math>|S \backslash \{ x_0 \}| = n-1</math>, tali sottoinsiemi sono, per l'ipotesi induttiva <math>2^{n-1}</math>.
* I sottoinsiemi che contengono <math>x_0</math>, sono sottoinsiemi del tipo <math>X \cup {x_0}</math>; con X sottoinsieme di <math>S \backslash \{ x_0 \}</math>; quindi anche tali sottoinsiemi sono, per l'ipotesi induttiva <math>2^{n-1}</math>.
Utente anonimo