1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Cardinality and Powersets

  1. Apr 16, 2008 #1
    Hi there, I'm having alot of trouble understanding this particular problem, and I hope the fine people of this forum can help me out =)

    1. The problem statement, all variables and given/known data

    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.

    2. Relevant equations

    3. The attempt at a solution

    To be honest, I have absolutely no idea on how to even approach this problem. After the 3+ hours of Office hours (bless my T.A's heart, being patient with me and all), all I could come up with is:

    We know that g:A -> B is a bijection and we have to show that f:P(A) ->P(B) is a bijection. I also know that I have to somehow find this bijective function for P(A) and P(B), and when I do that, I have show that the function is one-to-one and onto.

    So since g:A->B is bijective we know we could have something like

    a1 ---> b1
    a2 ---> b2 and so on.

    My T.A. also wrote down:

    {a} ---> {b}
    {a1, a2} ---> {b1, b2}
    {b2} ---> {b2}
    Which he said could possibly help in finding the bijective function (which he said should probably be in set builder form). Any help would be greatly appreciated.
  2. jcsd
  3. Apr 16, 2008 #2


    User Avatar
    Science Advisor
    Homework Helper

    That's like, pretty easy. P(A) is the set of all subsets of A, ditto for P(B). If you have a bijection from A to B, it should be pretty easy to write down a bijection from a subset of A to a subset of B. Map all of the elements of A in the subset to elements of B, creating a subset of B. Now show it's a bijection.
  4. Apr 16, 2008 #3
    I really don't get what you're trying to say. So if I take the elements of the Subset of A and map them to elements of B, making a new subset for B, how does help with the Powerset of A mapping to the powerset of B, as well as creating a bijective function? My only guess as to why you could do this is if there exists a bijection within subsets, then the set itself must be a bijection(but that doesn't sound right at all to me, I will skim my notes and the chapter again just to make sure). Again, I apologize for my lack of understanding, for some reason this is just like a brick wall to me.
  5. Apr 16, 2008 #4
    since f:A->B is a bijection f restricted to to any subset of A is a bijection to a subset of B. this is a mapping from P(A) -> P(B). proving that the sum of all these bijections is a bijection is probably easy so if you want i'll fill it in the rest of the way.
    Last edited: Apr 16, 2008
  6. Apr 16, 2008 #5


    User Avatar
    Science Advisor
    Homework Helper

    Ok, the powerset of A IS the set of all subsets of A. Ditto for B. To create a bijection between the two, I need to create a bijection between the subsets. Ok, I already have a bijection say f, between A and B. If I have a subset of A, say {a1,a2,a3} I would map that to the subset of B {f(a1),f(a2),f(a3)}. I think that was what your T.A. was trying to write down for you. Sorry, but I'm have trouble expressing this any more clearly. Sorry you are blocking, but it is so obvious.
  7. Apr 16, 2008 #6
    alright no need to make the kid feel dumb
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook