Results 1 to 7 of 7

Math Help - Induction with power sets

  1. #1
    MHF Contributor
    Joined
    Oct 2005
    From
    Earth
    Posts
    1,599

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by Jameson View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    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}.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2005
    From
    Earth
    Posts
    1,599
    Quote Originally Posted by Isomorphism View Post
    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!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by Jameson View Post
    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 View Post
    #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}

    Quote Originally Posted by Jameson View Post
    #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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2005
    From
    Earth
    Posts
    1,599
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Cardinality of Sets and Power Sets
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 8th 2011, 05:26 PM
  2. Power Sets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 9th 2009, 02:27 AM
  3. Induction proof: Cardinality of power sets
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 10th 2009, 04:59 PM
  4. Power Sets
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 22nd 2008, 08:43 AM
  5. Power sets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 22nd 2007, 07:21 PM

Search Tags


/mathhelpforum @mathhelpforum