1. Not finding help here? Sign up for a free 30min 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 set / surjection

  1. Sep 8, 2008 #1

    nicksauce

    User Avatar
    Science Advisor
    Homework Helper

    1. The problem statement, all variables and given/known data
    Suppose that f is a mapping from a finite set X to P(X) (the power set of X). Prove that f is not surjective.


    2. Relevant equations



    3. The attempt at a solution
    My proof strategy is
    1) Show that P(X) always has more elements than X
    2) Show that a mapping from X->Y cannot be surjective if Y has more elements than X.
    (Unless someone can suggest a better strategy ;)

    1)We'll prove this by induction. Let |X| represent the number of elements in a finite set X. For the base case, X={a} and P(x)={ {a}, {a,0} }, so it holds (0 means the null set here). For the inductive step suppose X={a1,...,an} and |P(x)| > |X|. Let Y = {a1,...an,a_n+1}, where we have added a new element a_n+1. Then |Y|=|X|+1. But P(Y)=P(X) (union) {a_n+1} (union) {a_n+1,0} (union) Possibly some other sets including a_n+1. Thus
    |P(Y)| >= |P(X)| + 2 > |P(X)| + 1 > |X| + 1 = |Y|.

    2)Suppose X={x1,...,xn} and Y={y1,...,ym} where m>n. Let f:X->Y. Then the image of f has at most n distinct elements, so there are at the fewest m-n elements of Y that aren't in the image of f. Since m-n > 0, this means that f is not surjective, as there m-n elements of Y that cannot be written as f(x) for some x in X.

    Just a rough outline of the proof, but does that seem okay?
     
  2. jcsd
  3. Sep 8, 2008 #2

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Hi nicksauce! :smile:

    The object is to construct an A in P(X) such that A is not an f(x) …

    Do you know the proof that the real numbers are not countable?

    You can adapt it to this. :smile:

    (if you don't know it, come back for a specific hint :wink:)
     
  4. Sep 8, 2008 #3

    nicksauce

    User Avatar
    Science Advisor
    Homework Helper

    I don't know that proof, so that specific hint might be helpful. Thanks.
     
  5. Sep 8, 2008 #4

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    ok…

    For a given f, you need to construct a subset of X which is not an f(x).

    Hint: for a given f, for each x, either x ε f(x), or x ε X - f(x). :smile:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Power set / surjection
  1. The Power Set (Replies: 1)

  2. Power set (Replies: 2)

  3. Power set? (Replies: 4)

Loading...