Sappiamo, per definizione, che, dato un insieme X, il suo insieme delle parti, indicato con P(X), è l'insieme di tutti i sottoinsiemi dell'insieme X.
Per l'insieme A = {a,b,c}, si ha P(A) = {∅,a,b,c,{a,b},{b,c},{a,c},{a,b,c}}.
 
In generale, dato un insieme X la cui cardinalità è n, la cardinalità del suo insieme delle parti è 2^n.
Dimostrazione. Usiamo il principio di induzione. La proprietà è vera per n=0, dacché l'insieme delle parti dell'insieme vuoto è l'insieme contenente l'insieme vuoto.
Si deve mostrare che è vera per ogni n. Supponiamola vera per n-1; l'insieme delle parti di un insieme con n elementi può essere considerato l'unione dell'insieme delle parti di un insieme con n-1 elementi, e di un insieme costituito dal prodotto cartesiano dell'insieme delle parti appena considerato e dall'elemento x non considerato prima. Entrambi questi insiemi hanno cardinalità, per ipotesi, uguale a 2^(n-1); la cardinalità dell'insieme delle parti è la somma di quella dei due, e cioè 2^n. ∎
 
Ora l'altra richiesta.
Dimostrazione. B, per definizione, è il risultato dell'unione di A e dell'insieme differenza B\A, che chiamiamo, per comodità, Y. 
Per il teorema appena dimostrato, se la cardinalità di B è n, la cardinalità del suo insieme delle parti è 2^n.
Se il teorema che si vuole dimostrare valesse, si avrebbe che l'insieme delle parti di B sarebbe il risultato dell'unione dell'insieme vuoto, dell'insieme delle parti di A meno l'insieme vuoto, dell'insieme delle parti di Y meno l'insieme vuoto e del prodotto cartesiano di questi ultimi due insiemi.
Supponiamo, per assurdo, che il teorema non sia vero. L'insieme delle parti di B non conterrebbe allora l'insieme delle parti di A; dato un generico insieme X, sia P'(X) = P(X)\∅; allora, per la relazione espressa prima, corretta con l'ipotesi per assurdo, si ha
               P(B) = P'(Y) ⋃ P'(A) x P'(Y);
passando alla cardinalità, con |A|=m e |Y|=n-m
               2^n = (2^(n-m) - 1) + (2^m - 1)*(2^(n-m) - 1);
sviluppando, si ha
               2^n = 2^(n-m) - 1 + 2^n - 2^m - 2^(n-m) + 1;
eliminando i termini opposti al secondo membro, rimane
               2^n = 2^n - 2^m,
da cui
               2^m = 0,
che è assurdo. È provato, allora, che P(A) è sottoinsieme di P(B). ∎
 
Buona settimana,
Samuele