(New page: 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> it...) |
|||
| Line 5: | Line 5: | ||
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>. | ||
| − | :--[[User:Narupley| | + | :--[[User:Narupley|Nick Rupley]] 00:16, 22 January 2009 (UTC) |
Revision as of 19:16, 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} $.
- --Nick Rupley 00:16, 22 January 2009 (UTC)
