Insieme delle parti: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m Bot: sposto wikilink a Anello (algebra) |
Nessun oggetto della modifica |
||
Riga 29:
Se ''n = 0'' necessariamente <math>S \equiv \emptyset</math>. E quindi <math>\mathcal{P}(S) = \{ \emptyset \} \Rightarrow |\mathcal{P}(S)| = 2^0 = 1</math>. Vera.
Sia ''n > 0'', e supponiamo l'asserto vero per ''n-1''. Cioè se ''T'' è un insieme
Poiché adesso si ipotizza che <math>|T| = n > 0</math> necessariamente <math>T \neq \emptyset</math> e dovrà avere almeno un elemento. Sia <math>x_0</math> un elemento dell'insieme. Un qualunque sottoinsieme di ''T'' può contenerlo o meno:
* I sottoinsiemi che non contengono <math>x_0</math>, sono sottoinsiemi di <math>T \backslash \{ x_0 \}</math>; poiché <math>|T \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>T \backslash \{ x_0 \}</math>; quindi anche tali sottoinsiemi sono, per l'ipotesi induttiva <math>2^{n-1}</math>.
| |||