Ciao a tutti. Dopo aver seguito una lezione all'università sugli insiemi, ho provato a ricostruire questa dimostrazione di cui mi ero perso alcuni pezzi, e vorrei conferma che sia corretta.
Parlando di insieme delle parti, vogliamo dimostrare che l'affermazione P(A) contiene 2^n elementi è valida per ogni n >= (maggiore o uguale) 1; dove n è il numero di elementi dell'insieme A.
Partiamo assumendo la verità di queste due affermazioni:
- P(A) contiene 2^n elementi è vera per n=1
- P(A) contiene 2^n elementi è vera per n=k (la mia prof ha usato questa lettera, immagino come si userebbe x o y o z...)
di conseguenza supponiamo che P(A) contiene 2^n elementi sarà vera anche per n=k+1 (in pratica la nostra ipotesi).
Procediamo prendendo un insieme A=(1,k,k+1) e lo dividiamo in due sottoinsiemi A1=(1,k) e A2=(k+1)
A questo punto sappiamo che:
- P(A1) contiene 2^k elementi
- P(A2) contiene 2^k elementi
- P(A1) è incluso in P(A)
- P(A2) è incluso in P(A)
Quindi uniamo i due sottoinsiemi per tornare a A, che come numero di elementi avrà quindi:
2^k + 2^k = 2^k (1+1) = 2^k+1
quindi 2^k = 2^k+1
per cui l'ipotesi iniziale è corretta.
Grazie in anticipo a chi saprà aiutarmi.