# Thread: Induction with power sets

1. ## Induction with power sets

For all natural numbers, n, prove that the power set of A={1,...,n} has 2^n elements of the original set.
--------------
Mmmmk.

So let P(n) be the propositional statement "the power set of A={1,...,n} has 2^n elements of A". P(0) = "The power set of A={1} has 2^0 elements", which seems to be true so P(0) holds. Now assume that P(j) is true for all j<k.

What now? I'm stuck.

2. Originally Posted by Jameson
For all natural numbers, n, prove that the power set of A={1,...,n} has 2^n elements of the original set.
--------------
Mmmmk.

So let P(n) be the propositional statement "the power set of A={1,...,n} has 2^n elements of A". P(0) = "The power set of A={1} has 2^0 elements", which seems to be true so P(0) holds. Now assume that P(j) is true for all j<k.

What now? I'm stuck.
Claim: P(k) = "the power set of A={1,...,k} has 2^k elements of A".
Steps:
1) $\forall S \in \text{Pow}(A), k \in S \text{ or } k \not\in S$

2) If we forget k, then there are k-1 elements. So use induction hypothesis.

3) $\text{Let }A' = \{1,2,3,...,k-1\}\,\,\,\,
\\ \forall S \in \text{Pow}(A'), S \cup \{k\} \in \text{Pow}(A)$

These are the only subsets with k as their elements. But clearly there are $|\text{Pow}(A')|$ subsets. Again use Induction Hypothesis.

4) Sum up both possibilities and wrap it up

3. Let $|X|=n+1$ then we can think of $X$ as $Y\cup Z$ where $|Y| = n$ and $|Z| = 1$ with $Y\cap Z = \emptyset$. Now show that $|\mathcal{P}(Y\cup Z)| = |A \cup B|$ where $A = \{ x\in \mathcal{P}(X)| x\cap Y = \emptyset\}$ and $B = \{x\in \mathcal{P}(X)| x\cap Y \not = \emptyset\}$. And then show $A\cap B = \empty$. Then by induction since $A,B$ are powersets it means the number of elements is $2^n+2^n= 2^{n+1}$.

4. Originally Posted by Isomorphism
Claim: P(k) = "the power set of A={1,...,k} has 2^k elements of A".
Steps:
1) $\forall S \in \text{Pow}(A), k \in S \text{ or } k \not\in S$

2) If we forget k, then there are k-1 elements. So use induction hypothesis.

3) $\text{Let }A' = \{1,2,3,...,k-1\}\,\,\,\,
\\ \forall S \in \text{Pow}(A'), S \cup \{k\} \in \text{Pow}(A)$

These are the only subsets with k as their elements. But clearly there are $|\text{Pow}(A')|$ subsets. Again use Induction Hypothesis.

4) Sum up both possibilities and wrap it up
Wow. To be honest, I'm lost with this method but I'll try to work it out.

#1) So you defining a new set, S, which is for all purposes a subset of Pow(A), right? So for all of these subsets of the powerset of A, k will either be in S or it won't be in S. If I haven't said anything wrong yet I believe I got this part.

#2) Does "forget k" mean assume k is not in S? Or are you talking about P(k) and P(k-1). I'm lost here. This seems to be the part where P(k-1) ->P(k), but I'm really lost.

#3) Just plain lost.

Sorry to be so slow. My prof. uses a very strict and repetitive method for all of our induction problems and I'm not used to doing these kinds of proofs in a slightly different way. Thanks for all the help!

5. Originally Posted by Jameson
Wow. To be honest, I'm lost with this method but I'll try to work it out.

#1) So you defining a new set, S, which is for all purposes a subset of Pow(A), right? So for all of these subsets of the powerset of A, k will either be in S or it won't be in S. If I haven't said anything wrong yet I believe I got this part.
Yes, you are right.

Originally Posted by Jameson
#2) Does "forget k" mean assume k is not in S? Or are you talking about P(k) and P(k-1). I'm lost here. This seems to be the part where P(k-1) ->P(k), but I'm really lost.
Yes that is what I meant. If a subset does not contain k,then it can only contain elements from A'. That means the number of subsets without k is $|\text{Pow}(A')|$. But by the Induction Hypothesis $|\text{Pow}(A')| = 2^{k-1}$

Originally Posted by Jameson
#3) Just plain lost.
I did not write a rigorous argument here. To count the number of subsets which have 'k' as their element, observe that such a subset is formed by k and elements other than k .
But where are these "elements other than k" coming from? Precisely A'. That is because each subset with k as an element can be written as $\{k\} \cup S'$ where $S' \in \text{Pow}(A')$. But again by Induction Hypothesis we have $|\text{Pow}(A')| = 2^{k-1}$ elements.

So the total number of ways is:
$|\text{Pow}(A)|= |k \in S| + |k \not \in S|\bigg{|}_{\forall S \in \text{Pow}(A)} = 2^{k-1}+2^{k-1} = 2^k$

So claim proved

6. Here is another way to prove it. Let $2=\{0,1\}$. Let $2^X$ be the set of all functions from $X\mapsto 2$ with $|X| = n$. There are $\underbrace{2\cdot ... \cdot 2}_n = 2^n$ such functions. Now we need to define a bijection between $2^X$ and $\mathcal{P}(X)$. Define $\theta: \mathcal{P}(X)\mapsto 2^X$ as follows: let $a\in \mathcal{P}(X)$ define $\theta(a) = \mu_a$ where $\mu_a: X\mapsto \{0,1\}$ as $\mu_a(x) = 1$ if $x\in a$ and $\mu_a(x) = 0$ if $x\not \in a$.

I know this is not by induction but this is another way of proving $|2^X| = |\mathcal{P}(X)|$. The nice part of the above proof is that we never need the fact that the set is finite, it works for infinite sets too.

7. Wow thank you very much Isomorphism.

That was a great explanation and it pretty much all makes sense. So the total number of elements in the Pow(A) can be expressed by terms with k and without k. Very clever. I fully get that if k is not in S, then the total number of these "non-k" elements is by induction hypothesis $2^{k-1}$. But you're saying also to basically account for all the "k terms", which is the sum of elements of the power set minus the sum of elements of non-k terms, it turns out to be the same number of elements as all the non-k terms? I think I just had a breakthrough.

Thank you very, very much. I get it all now.