• Support PF! Buy your school textbooks, materials and every day products Here!

Cardinality and Powersets

  • Thread starter opt!kal
  • Start date
19
0
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. Homework Statement

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. Homework 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

g:
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.
 

Answers and Replies

Dick
Science Advisor
Homework Helper
26,258
618
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.
 
19
0
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.
 
1,703
5
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:
Dick
Science Advisor
Homework Helper
26,258
618
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.
 
1,703
5
alright no need to make the kid feel dumb
 

Related Threads for: Cardinality and Powersets

  • Last Post
Replies
5
Views
970
Replies
6
Views
5K
  • Last Post
Replies
1
Views
879
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
0
Views
723
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
6
Views
2K
Top