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: Onto Mappings from a Set to Its Power Set

  1. Sep 6, 2008 #1
    The problem statement, all variables and given/known data
    Prove that there are no mappings from a set S onto S*, where S* is the power set of S.

    The attempt at a solution
    This begs proof by contradiction: Let f be a mapping from S onto S*. Then for every A in S*, there is an a in S with f(a) = A. I don't know how to proceed from here. Any tips?
     
  2. jcsd
  3. Sep 6, 2008 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Can you construct a subset of S (call it B) that is different from all of the other subsets f(a)? Hint: a is either in f(a) or not in f(a). Whichever it is, make B the opposite. Think 'Cantor diagonal'.
     
  4. Sep 6, 2008 #3
    Hmm...let B = {a in S : a not in f(a)}. B belongs to S* and since f is onto there must be an x in S for which f(x) = B.

    I guess I should now ask if x is in B? Suppose it is. Then x is not in f(x) = B. Contradiction. If x is not in B, then x is in f(x) = B. Contradiction. Hence, f can't be onto.

    Thanks a lot!
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook