Induction with power sets

**Jameson** · April 28th 2008, 04:21 AM

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.

**Isomorphism** · April 28th 2008, 05:38 AM

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\}\,\,\,\,<br /> \\ \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

**ThePerfectHacker** · April 28th 2008, 06:32 AM

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}$ .

**Jameson** · April 28th 2008, 06:33 AM

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\}\,\,\,\,<br /> \\ \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!

**Isomorphism** · April 28th 2008, 06:48 AM

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

**ThePerfectHacker** · April 28th 2008, 06:55 AM

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.

**Jameson** · April 28th 2008, 07:17 AM

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.

Thread: Induction with power sets

LinkBack

Thread Tools

Display

Induction with power sets

Similar Math Help Forum Discussions

[SOLVED] Cardinality of Sets and Power Sets

Power Sets

Induction proof: Cardinality of power sets

Power Sets

Power sets

Search Tags