Differenze tra le versioni di "Insieme delle parti"

m
nessun oggetto della modifica
m (Bot: Aggiungo: sk:Potenčná množina)
m
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 ''S'' 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>.
 
Quindi i sottoinsiemi di S sono in tutto <math>2^{n-1} + 2^{n-1} = 2 \cdot 2^{n-1} = 2^{n}</math>.
1

contributo