# Prove that $|P(X)| = 2^{|X|}$ [closed]

Prove that for any finite set $X$, $|P(X)| = 2^{|X|}$. The solution should use induction.

• This is a problem statement, not a question. Please include your own effort and a specific question reagarding it. – Raphael Sep 23 '13 at 7:29

Basis $$|X| = 0$$ $$|P(X)| = 2^{|X|} = 2^0 = 1$$ True. Any set with zero elements takes the form $\{\}$, and thus its power set will be $\{\{\}\}$. One element.
We must show: $$|P(X+1)| = 2^{|X+1|}$$ Thus: $$|P(X+1)| = 2^{|X+1|} = 2*2^{|X|} = 2*|P(X)|$$ This is true because, if $X$ as a set grows by one, the power set, for every member in its set now has a new binary choice: include the new element or not. Thus the power set doubles.