0
$\begingroup$

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

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

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.

Inductive Step

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.

$\endgroup$