| Line 1: | Line 1: | ||
[[Category:MA453Spring2009Walther]]Consider <math>\scriptstyle n=1</math>. For a set <math>\scriptstyle S\textstyle\mid\scriptstyle\mid S\mid=1</math>, there are two subsets: the empty set and <math>\scriptstyle S</math> itself. Indeed, there are <math>\scriptstyle2^n=2^1=2</math> subsets. | [[Category:MA453Spring2009Walther]]Consider <math>\scriptstyle n=1</math>. For a set <math>\scriptstyle S\textstyle\mid\scriptstyle\mid S\mid=1</math>, there are two subsets: the empty set and <math>\scriptstyle S</math> itself. Indeed, there are <math>\scriptstyle2^n=2^1=2</math> subsets. | ||
| − | 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 | + | 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 or 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>. <math>\scriptstyle\Box</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) | ||
Latest revision as of 03:29, 22 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 or 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)
