1. PF Contest - Win "Conquering the Physics GRE" book! Click Here to Enter
    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
    Science Advisor

    Okay, so how does "phi(u)= U" lead to a contradiction?
  4. Jun 11, 2012 #3
    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 Threads - Power sets cardinalities Date
Set theory: proofs regarding power sets Jul 24, 2014
Finding Cardinality of Power Set May 20, 2014
Power Set Unions and inclusion Aug 3, 2012
Power of set of choice functions Dec 4, 2011
Null sets and Power sets Jun 9, 2011