Prove that for any finite set $X$, $|P(X)| = 2^{|X|}$. The solution should use induction.
1
-
$\begingroup$ This is a problem statement, not a question. Please include your own effort and a specific question reagarding it. $\endgroup$– Raphael ♦Sep 23, 2013 at 7:29
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
