Sia A un insieme con cardinalità n. Dimostrare che la cardinalità dell'insieme delle parti di A è $ 2^n $.
Buon divertimento!
(Non dovrebbe essere difficile...)
insieme delle parti
Dimostrazione più scolastica che fa uso del noto binomio di Newton...
Sia $ \displaystyle s_k $ il numero dei sottoinsiemi di A costituiti da k elementi con $ \displaystyle k\in\{0,1,...,n\} $
$ \displaystyle |P(A)|=s_0+s_1+...+s_k+...+s_n $
Se $ \displaystyle k=0 \ s_0={n \choose 0} =1 $ perchè $ \O $ è unico
Se $ \displaystyle k>0 \ s_k=C_{n,k}={n \choose k} $
Quindi $ \displaystyle |P(A)|={n \choose 0}+{n \choose 1}+...+{n \choose k}+...+{n \choose n}= $
$ \displaystyle =\sum_{k=0}^{n}{n \choose k}=\sum_{k=0}^{n}{n \choose k}\cdot 1^{n-k}\cdot 1^k=(1+1)^n=2^n $
Sia $ \displaystyle s_k $ il numero dei sottoinsiemi di A costituiti da k elementi con $ \displaystyle k\in\{0,1,...,n\} $
$ \displaystyle |P(A)|=s_0+s_1+...+s_k+...+s_n $
Se $ \displaystyle k=0 \ s_0={n \choose 0} =1 $ perchè $ \O $ è unico
Se $ \displaystyle k>0 \ s_k=C_{n,k}={n \choose k} $
Quindi $ \displaystyle |P(A)|={n \choose 0}+{n \choose 1}+...+{n \choose k}+...+{n \choose n}= $
$ \displaystyle =\sum_{k=0}^{n}{n \choose k}=\sum_{k=0}^{n}{n \choose k}\cdot 1^{n-k}\cdot 1^k=(1+1)^n=2^n $