📂Lemmas

The Number of Subsets of a Finite Set with n Elements

Formula

For a finite set $X$, if $n(X)=n$ then $n(P(X))=2^{ n }$.

Derivation

The number of subsets selecting $k$ elements out of $n$ elements is $_{ n }{ C }_{ k }$. Using the binomial theorem to sum up all possible cases, $\displaystyle \sum _{ k=0 }^{ n }{_{ n }{ C }_{ k } }=2^{ n }$, hence $n(P(A))=2^{ n }$.

■