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!

Power sets and cardinalities (proof)

  1. Jun 11, 2012 #1
    1. The problem statement, all variables and given/known data

    Let A be a set. Show that there is no surjective function phi: A --> P(A), where P(A) is the power set of A. What does this say about the cardinalities of A and P(A)?

    2. Relevant equations
    Assume that phi is a surjection of A onto P(A) and consider the set U= {a in A : a not in phi(a)} of A. Since phi is a surjection there must be a u in A satisfying phi(u)=U.

    3. The attempt at a solution
  2. jcsd
  3. Jun 11, 2012 #2


    User Avatar
    Staff Emeritus
    Science Advisor

    Okay, so how does "phi(u)= U" lead to a contradiction?
  4. Jun 11, 2012 #3


    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    That's not an effort, that is the hint that was given.
    Anyway, think about whether u is an element of U.
  5. Jun 11, 2012 #4
    From those 2 replies i feel as if im trying to overthink this problem. Is it that u does not need to be an element of U but it has to be an element of A? or something to that extent?
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Power sets and cardinalities (proof)
  1. Power Sets (Replies: 3)

  2. Cardinalities of Sets (Replies: 3)