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

    HallsofIvy

    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?
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook