# Induction with power sets

• Apr 28th 2008, 04:21 AM
Jameson
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.
• Apr 28th 2008, 05:38 AM
Isomorphism
Quote:

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) $\displaystyle \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) $\displaystyle \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 $\displaystyle |\text{Pow}(A')|$ subsets. Again use Induction Hypothesis.

4) Sum up both possibilities and wrap it up :)
• Apr 28th 2008, 06:32 AM
ThePerfectHacker
Let $\displaystyle |X|=n+1$ then we can think of $\displaystyle X$ as $\displaystyle Y\cup Z$ where $\displaystyle |Y| = n$ and $\displaystyle |Z| = 1$ with $\displaystyle Y\cap Z = \emptyset$. Now show that $\displaystyle |\mathcal{P}(Y\cup Z)| = |A \cup B|$ where $\displaystyle A = \{ x\in \mathcal{P}(X)| x\cap Y = \emptyset\}$ and $\displaystyle B = \{x\in \mathcal{P}(X)| x\cap Y \not = \emptyset\}$. And then show $\displaystyle A\cap B = \empty$. Then by induction since $\displaystyle A,B$ are powersets it means the number of elements is $\displaystyle 2^n+2^n= 2^{n+1}$.
• Apr 28th 2008, 06:33 AM
Jameson
Quote:

Originally Posted by Isomorphism
Claim: P(k) = "the power set of A={1,...,k} has 2^k elements of A".
Steps:
1) $\displaystyle \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) $\displaystyle \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 $\displaystyle |\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! :)
• Apr 28th 2008, 06:48 AM
Isomorphism
Quote:

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.

Quote:

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 $\displaystyle |\text{Pow}(A')|$. But by the Induction Hypothesis $\displaystyle |\text{Pow}(A')| = 2^{k-1}$

Quote:

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 $\displaystyle \{k\} \cup S'$ where $\displaystyle S' \in \text{Pow}(A')$. But again by Induction Hypothesis we have $\displaystyle |\text{Pow}(A')| = 2^{k-1}$ elements.

So the total number of ways is:
$\displaystyle |\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 :)
• Apr 28th 2008, 06:55 AM
ThePerfectHacker
Here is another way to prove it. Let $\displaystyle 2=\{0,1\}$. Let $\displaystyle 2^X$ be the set of all functions from $\displaystyle X\mapsto 2$ with $\displaystyle |X| = n$. There are $\displaystyle \underbrace{2\cdot ... \cdot 2}_n = 2^n$ such functions. Now we need to define a bijection between $\displaystyle 2^X$ and $\displaystyle \mathcal{P}(X)$. Define $\displaystyle \theta: \mathcal{P}(X)\mapsto 2^X$ as follows: let $\displaystyle a\in \mathcal{P}(X)$ define $\displaystyle \theta(a) = \mu_a$ where $\displaystyle \mu_a: X\mapsto \{0,1\}$ as $\displaystyle \mu_a(x) = 1$ if $\displaystyle x\in a$ and $\displaystyle \mu_a(x) = 0$ if $\displaystyle x\not \in a$.

I know this is not by induction but this is another way of proving $\displaystyle |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.
• Apr 28th 2008, 07:17 AM
Jameson
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 $\displaystyle 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. (Rofl)