| Line 3: | Line 3: | ||
Assume that for a finite but arbitrary <math>\scriptstyle n=\mid S\scriptstyle\mid</math>, <math>\scriptstyle\mid P(S)\mid=2^n</math>. Now consider adding an extra element to <math>\scriptstyle S</math> to create <math>\scriptstyle S^'</math>. Obviously <math>\scriptstyle P(S^')</math> contains all subsets of <math>\scriptstyle S</math>. However, for every subset of <math>\scriptstyle S</math>, we may choose to either include to exclude the extra element. This constitutes 2 choices over <math>\scriptstyle\mid P(S)\mid=2^n</math> elements. So the total number of subsets of <math>\scriptstyle S'</math> is <math>\scriptstyle2\cdot2^n=2^{n+1}</math>. | Assume that for a finite but arbitrary <math>\scriptstyle n=\mid S\scriptstyle\mid</math>, <math>\scriptstyle\mid P(S)\mid=2^n</math>. Now consider adding an extra element to <math>\scriptstyle S</math> to create <math>\scriptstyle S^'</math>. Obviously <math>\scriptstyle P(S^')</math> contains all subsets of <math>\scriptstyle S</math>. However, for every subset of <math>\scriptstyle S</math>, we may choose to either include to exclude the extra element. This constitutes 2 choices over <math>\scriptstyle\mid P(S)\mid=2^n</math> elements. So the total number of subsets of <math>\scriptstyle S'</math> is <math>\scriptstyle2\cdot2^n=2^{n+1}</math>. | ||
| − | We have shown that <math>\textstyle(\scriptstyle\mid S\mid=n\ \rightarrow\ \mid P(S)\mid=2^n\textstyle)\rightarrow(\scriptstyle\mid S^'\mid=n+1\ \rightarrow\ \mid P(S^')\mid=2^{n+1}\textstyle)</math>, so by induction, <math>\scriptstyle\mid S\mid=n\ \rightarrow\ \mid P(S)\mid=2^n</math> for all <math>\scriptstyle n\in\mathbb{N}</math>. | + | We have shown that <math>\textstyle(\scriptstyle\mid S\mid=n\ \rightarrow\ \mid P(S)\mid=2^n\textstyle)\rightarrow(\scriptstyle\mid S^'\mid=n+1\ \rightarrow\ \mid P(S^')\mid=2^{n+1}\textstyle)</math>, so by induction, <math>\scriptstyle\mid S\mid=n\ \rightarrow\ \mid P(S)\mid=2^n</math> for all <math>\scriptstyle n\in\mathbb{N}</math>. <math>\scriptstyle\Box</math> |
:--[[User:Narupley|Nick Rupley]] 00:16, 22 January 2009 (UTC) | :--[[User:Narupley|Nick Rupley]] 00:16, 22 January 2009 (UTC) | ||
Revision as of 20:29, 21 January 2009
Consider $ \scriptstyle n=1 $. For a set $ \scriptstyle S\textstyle\mid\scriptstyle\mid S\mid=1 $, there are two subsets: the empty set and $ \scriptstyle S $ itself. Indeed, there are $ \scriptstyle2^n=2^1=2 $ subsets.
Assume that for a finite but arbitrary $ \scriptstyle n=\mid S\scriptstyle\mid $, $ \scriptstyle\mid P(S)\mid=2^n $. Now consider adding an extra element to $ \scriptstyle S $ to create $ \scriptstyle S^' $. Obviously $ \scriptstyle P(S^') $ contains all subsets of $ \scriptstyle S $. However, for every subset of $ \scriptstyle S $, we may choose to either include to exclude the extra element. This constitutes 2 choices over $ \scriptstyle\mid P(S)\mid=2^n $ elements. So the total number of subsets of $ \scriptstyle S' $ is $ \scriptstyle2\cdot2^n=2^{n+1} $.
We have shown that $ \textstyle(\scriptstyle\mid S\mid=n\ \rightarrow\ \mid P(S)\mid=2^n\textstyle)\rightarrow(\scriptstyle\mid S^'\mid=n+1\ \rightarrow\ \mid P(S^')\mid=2^{n+1}\textstyle) $, so by induction, $ \scriptstyle\mid S\mid=n\ \rightarrow\ \mid P(S)\mid=2^n $ for all $ \scriptstyle n\in\mathbb{N} $. $ \scriptstyle\Box $
- --Nick Rupley 00:16, 22 January 2009 (UTC)
