Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

More proof on sets help

  1. Sep 14, 2007 #1
    Hey all,

    As I said in one of my earlier posts I'm not that good with proofs, hence why I have another post.

    Here is the one I'm on now....

    Prove using mathematical induction that |2[tex]^{A}[/tex]| = 2[tex]^{|A|}[/tex] where A is a finite set.

    ..Here is what I have so far


    Any help is greatly appreciated.

  2. jcsd
  3. Sep 15, 2007 #2
    You might look at a proof this way.

    Let's let |S| = n and S' = S U {a} (where a is not in S). Clearly, |S'| = n+1.
    Let P(S) and P(S') denote their powersets.
    Let A = {B U {a} | B is in P(S)}.

    In the induction step, the induction hypothesis says |P(S)| = 2^n.
    So if you can show the following

    1. P(S') = P(S) U A,
    2. P(S) and A are disjoint,
    3. |A| = 2^n,

    you'll be home.

    Of course, induction isn't the only approach.
    You might think about a proof based on characteristic maps.
  4. Sep 15, 2007 #3


    User Avatar
    Science Advisor

    2A means, of course, the collection of all subsets of A. |A| is the number of elements in A and |2A| is the number of elements in 2A, i.e. the number of subsets of A. And, of course, we are assuming A is a finite set.

    Assume, as you did in the induction, that |2A|= 2|A| for all sets with k members: |A|= k. Now let B be a set with k+1 members: |B|= k+1. Let x be a specific member of B (since |B|= k+1> 0, there exist such a member). Every subset of B either includes x or it does not. Those subsets that do not include x are subsets of B\{x} which has k members. How many of them are there? Those subsets that do include x can be thought of as [itex]C\cup {x}[/itex] where C is a subset of B that does not include x. How of them are there? How many subsets does B have?
    Last edited by a moderator: Sep 15, 2007
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook