Results 1 to 7 of 7

Math Help - equinumerous power sets

  1. #1
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    equinumerous power sets

    Hi

    I am trying to prove that if A\sim B then
    \mathcal{P}(A)\sim \mathcal{P}(B)

    Now A\sim B means that there is some bijection from A to B. And I need
    to prove that there is also some bijection from \mathcal{P}(A) to
    \mathcal{P}(B). So first thing, I need to come up with some function and then prove that its one to one and onto.

    Can people provide me some hints to begin with to come up with such a function ?

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778

    Re: equinumerous power sets

    Suppose you have a group of people each of whom has his/her passport. You need to show that there are as many subgroups of people as there are subsets of passports. Given a subgroup of people, don't you have an idea which passports you want to associate with this subgroup?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Aug 2011
    Posts
    127

    Re: equinumerous power sets

    The function is the easy part, as emakarov hints. If you have f: A <--> B, creating a bijection g: P(A) <--> P(B) is not hard to figure out. For a given subset of A, you can get a unique corresponding subset of B by taking the image of f on the members of the subset.

    The remainder of the proof involves showing that this is a bijection. Since f is a bijection, g by its definition is defined everywhere on P(A), so it's a left-total relation. Since f is a function, g is right-definite (g only assigns one subset of B to each subset of A). These two properties imply that g is a function. It remains to show that g is left-definite (injective or one-to-one) and right-total (surjective or onto), but you should be able to figure that out on your own.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    Re: equinumerous power sets

    Since  A\sim B there is a bijection,

    f:A\to B

    Now consider the set,

    h=\{(s_1,s_2)\in \mathcal{P}(A)\times\mathcal{P}(B)\;|\;s_2=f(s_1) \}

    This is a relation from \mathcal{P}(A) to \mathcal{P}(B).
    First we prove that

    h:\mathcal{P}(A)\to \mathcal{P}(B)

    and then we prove that its one to one and onto. So h is a bijection. So

    \mathcal{P}(A) \sim \mathcal{P}(B)

    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Aug 2011
    Posts
    127

    Re: equinumerous power sets

    That's on the right track but there are details you have wrong. It's not the case that (s1, s2) is necessarily in P(A) x P(B) if s2 = f(s1). f operates on the domain A, while h operates on the domain P(A), so that doesn't make any sense as it is written. Try defining h so that it is the (s, t) in P(A) x P(B) where the elements of t are determined by taking each element in s and applying f.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778

    Re: equinumerous power sets

    Quote Originally Posted by Annatala View Post
    f operates on the domain A, while h operates on the domain P(A), so that doesn't make any sense as it is written.
    I assume the OP redefined the notation f(s) to mean \{f(x)\mid x\in s\} when s\in\mathcal{P}(A). This is sometimes done. I've also seen people use f[s] to distinguish it from f(x).
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    Re: equinumerous power sets

    if  s \in \mathcal{P}(A) \Rightarrow s \subseteq A

    and since f:A\to B , we have

    f(s)=\{f(x)\mid x\in s\} . This is how Velleman defines it in his book
    "How to prove it". So Annatala , I don't understand what you are trying to say.
    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. Equinumerous Sets
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 6th 2009, 08:37 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

/mathhelpforum @mathhelpforum