Expert: Sherry Wallin - 3/24/2009

Question
Let S be an arbitrary non-empty set and let P(S) denote its power set.  Prove by contradiction that there is no surjective mapping f: S -> P(S).

Obviously I start by assuming there is a surjective mapping but where to from there??

Answer
Steve~
    Yes, assume there is a surjective mapping f from S --> P(S).  By definition then every element in P(S) is mapped to by an element in S. But how can this be? The power set of any set has to be larger than the set itself. The 'elements' in the power set are sets. There is a theorem that says if A is a set of n elements then P(A) is a set with 2^n elements. The other thing is that S is a non-empty set so {} does not exist in S whereas in P(S) one of the elements is the {}, therefore  you have found an element in P(S) that does not get mapped to, hence your contradiction.

Math Prof