Hi
My question is
Prove by induction that if A has n elements, then $\displaystyle P(A)$ has $\displaystyle 2^{n}$elements.
thanks
If we do it by induction, we have only $\displaystyle n$ number to consider, but Drexel suggested it by number of ways to partition, in which case the empty set $\displaystyle \emptyset$ must be added into consideration, which is why he said $\displaystyle n+1$ instead of $\displaystyle n$.
If the empty set is not considered, we will end up getting $\displaystyle 2^{n-1} - 1$, instead of $\displaystyle 2^n$.
By induction, we need to name the set. Let $\displaystyle A$ be the set such that $\displaystyle x \in A$
By induction, we can begin with the base case, n=0, where $\displaystyle \emptyset$ is the only member, i.e. When $\displaystyle n= 0$, $\displaystyle P(A_0)$ contains $\displaystyle 2^n = 2^0 = 1$ members. The subscript denotes the number of elements in the set $\displaystyle A$.
Next, assume it is true that the set $\displaystyle A$ containing $\displaystyle n$ members, written $\displaystyle A_n$ to have the Power set containing $\displaystyle 2^n$.
The prove $\displaystyle P(A_{n+1})$ contain $\displaystyle 2^{n+1}$ members.
We know $\displaystyle P(A_n)$ contains $\displaystyle n$ number of elements. Since $\displaystyle x \in A$, we need to introduce an element that is not in $\displaystyle A$, say $\displaystyle y \notin A$ so that
$\displaystyle
P(A_{n+1}) = P(A_n \cup \{y\})
$
The set $\displaystyle P(A_n \cup \{y\})$ will have additional members that look like this:
$\displaystyle \{\{\emptyset \} \cup \{y\}, \{1\} \cup \{y\}, \{2\} \cup \{y\}, ......\{......(n-2),(n-1),n\} \cup \{y\}\}$ which gives an additional $\displaystyle 2^n$ members to the original set, $\displaystyle P(A)$ .
I just cannot see how this can be considered proof by induction. It seems to me that by partitioning we get to it by binomial theorem. I cannot see where the $\displaystyle n+1$ goes.
The only way I can think off is as follows:
Let $\displaystyle A$ be a set of $\displaystyle n$ elements, then in the Power set $\displaystyle P(A)$ there are:
$\displaystyle \binom{n}{0}$ number of {$\displaystyle \emptyset$ }
$\displaystyle \binom{n}{1}$ number of singleton sets, {1}, {2}, {3}, ....{n}
$\displaystyle \binom{n}{2}$ number of doublets, {1,2}, {1,3}, {1,4}, ....{n}
$\displaystyle \binom{n}{3}$ number of triplets, {1,2,3}, {1,2,4}, {1,2,5}, ....{n}
.
.
.
$\displaystyle \binom{n}{n}$ number of {$\displaystyle A$}
All together $\displaystyle |P(A_n)| =\Sigma_{i=0}^n \binom{n}{i}a^i b^{n-i}= 2^n$, where $\displaystyle a = 1$ and $\displaystyle b=1$
I know for sure that my method is not by induction.
Drexel, I am think of a different thing?
Theorem: For a finite set $\displaystyle E$ with $\displaystyle \text{card }E=n$ we have that $\displaystyle \text{card }\wp\left(E\right)=2^n$
Proof: Let $\displaystyle p(n)$ be the number of subsets of $\displaystyle \left\{1,\cdots,n\right\}$. Consider the set $\displaystyle \left\{1,\cdots,n,n+1\right\}=E'$. Partition $\displaystyle E'$ into two cells $\displaystyle B_1,B_2$ where $\displaystyle B_1$ contains all subsets $\displaystyle S$ of $\displaystyle \left\{1,\cdots,n,n+1\right\}$ such that
$\displaystyle n+1\notin S$ and $\displaystyle B_2=E'-B_1$. Evidently, we have that $\displaystyle \text{card }B_1$ is the number of subsets one can form from $\displaystyle \left\{1,\cdots,n\right\}$ which is $\displaystyle p(n)$. We have two choices for the elements $\displaystyle S'$, either $\displaystyle S'=\{n+1\}$
or it contains some element of $\displaystyle \{1,\cdots,n\}$. Clearly, the latter case tells us that there is an element of $\displaystyle B_2$ for each non-empty subset in $\displaystyle B_1$ which is $\displaystyle p(n)-1$. And, it clearly follows that the number
of elements of $\displaystyle B_2$ is the $\displaystyle p(n)-1$ with the addition of $\displaystyle \{n+1\}$ so that $\displaystyle \text{card }B_2=p(n)$. Thus, $\displaystyle \text{card}\{1,\cdots,n,n+1\}=\text{card }B_1+\text{card }B_2=p(n)+p(n)=2p(n)$. But,
$\displaystyle \text{card }\left\{1,\cdots,n,n+1\right\}=p(n+1)$, so that $\displaystyle p(n+1)=2p(n)$. This is a simple linear homogeneous recurrence relation with solution $\displaystyle p(n)=C\cdot 2^n$ for some constant. But, seeing that $\displaystyle p(0)$ is the
number of subsets of $\displaystyle \varnothing$ which is zero we see that $\displaystyle 1=p(0)=C\cdot2^0=C$ from where it follows that $\displaystyle p(n)=2^n$. The conclusion follows since any set of $\displaystyle n$ elements is, by definition, equipotent to
$\displaystyle \left\{1,\cdots,n\right\}$. $\displaystyle \blacksquare$
Remark: The induction was implicitly used in solving the recurrence relation.
We don't necessary have to make things overcomplicated:
Let $\displaystyle A_n = \left\{1,\cdots ,n \right\}$
Step 1.
card $\displaystyle \mathcal{P}(A_0))= 2^0 = 1$ is satisfied.
step 2. Fix some $\displaystyle N > 0$. Assume for all $\displaystyle n \leq N$ we have card($\displaystyle \mathcal{P}(A_n)) = 2^n$.
From $\displaystyle \mathcal{P}(A_n)$ we can construct $\displaystyle \mathcal{P}(A_{n+1})$. Namely by doing the following:
Let $\displaystyle P = \emptyset $.
Let $\displaystyle S \in\mathcal{P}(A_n)$:
1. Add a copy of $\displaystyle S$ in $\displaystyle P$.
2. Take another copy of $\displaystyle S $and let $\displaystyle n+1\in S$ and add it to $\displaystyle P$.
We don't have to sit here and discuss for hours that we constructed $\displaystyle P = \mathcal{P}(A_{N+1})$.
Now evidently card$\displaystyle \mathcal{P}(A_{N+1}) = 2\cdot $card$\displaystyle \mathcal{P}(A_N) = 2\cdot 2^N = 2^{N+1}$ by the induction hypothesis.
step 3. By induction follows from step 1+step 2 that for all $\displaystyle n\in \mathbb{N}$ we have card$\displaystyle \mathcal{P}(A_n) = 2^n$
Well I clearly hold to the induction-procedure ;p
Aside from that, I took some extra unnecessary steps and construct an extra Set P.
However from the induction-hypothesis and the observation that for every element of $\displaystyle \mathcal{P}(A_n)$ we can choose to add or not add an extra element N+1, the conclusion follows.
I think that's clearly more straightforward approach.