Results 1 to 5 of 5

Math Help - Cardinality and Powersets

  1. #1
    Newbie
    Joined
    Apr 2008
    Posts
    6

    Cardinality and Powersets

    I've been racking my brain on this one and I have no idea on where to even start, so any help would be appreciated!

    Let A and B be infinite sets with the same cardinality. Prove that P(A) and P(B) have the same cardinality. Do this by giving explicitly a bijective function from P(A) to P(B). You must also prove that your function is indeed a bijection (show that it is 1-1 and onto).
    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
    Since A and B have the same cardinality, there must exist a bijection f:A -> B.

    Now \forall X \in P(A) , f(X) \in P(B)
    Now define f:P(A) -> P(B). This must be a bijection

    You can fill the details
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2008
    Posts
    6
    \forall X \in P(A) , f(X) \in P(B)


    Okay so I understand what that is trying to show, but is that my bijective function that I am trying to give? So let's say I wanted that in set builder notation, how do I go about that? Also, what steps do you recommend in showing that it is one-to-one and onto? (again I apologize, for some reason I just cant wrap my head around this problem).
    Last edited by opt!kal; April 16th 2008 at 10:31 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Prove that f(X) = f(Y) \Rightarrow X = Y

    f(X) = f(Y) \Rightarrow f(X) \subset f(Y)
    Since f is 1-1, this implies X \subset Y(Try proving this)

    Similarly,
    f(X) = f(Y) \Rightarrow f(Y) \subset f(X)
    Since f is 1-1, this implies Y \subset X

    Thus X = Y
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Apr 2008
    Posts
    6
    Okay I think I'm starting to see what you say.

    So for the one to one case since we know that the power set is just the set of all subsets, we can take certain subsets of A, and map them to elements in B, creating a subset itself. So for example:

    {a1} ---> {b1}
    {a2} ---> {b2}
    {a2, a3} ---> {b2, b3}
    .
    .
    .

    and so on right? So we have shown that the subsets of A can be mapped to elements to B in a one-to-one fashion. Since we know that all Subsets of A are one-to-one , we know that it must have the same cardinality. And since the set of all subsets is the Powerset, we now know that P(A) is one to one with P(B)? Does that make any sense? But that onto case still slips me. Thanks in advance.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Cardinality
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 11th 2010, 08:08 AM
  2. Cardinality of R, [0,1], R^2, [0,1] x [0,1]
    Posted in the Differential Geometry Forum
    Replies: 11
    Last Post: March 18th 2010, 03:20 PM
  3. Cardinality
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 31st 2009, 04:56 PM
  4. Cardinality
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 7th 2009, 01:34 PM
  5. Cardinality of a Set
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 27th 2009, 04:33 PM

Search Tags


/mathhelpforum @mathhelpforum