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: Can someone teach me this problem of sets.

  1. Oct 28, 2005 #1

    S&S

    User Avatar

    Let A and B be sets and Let f:A---->B be a function. Define a function G: Power set (B)------->Power (A) by declaring that, for C is part of B or equal to B:
    G(C)={x is element of A: f(x) is element of C}
    Show that G is 1-1 if and only if f is onto. :cry:

    Can anyone teach me this problem? Hopefully I can get some feelings about set theory. I just don't feel right.

    Thank you so much for your good tips.
     
  2. jcsd
  3. Oct 28, 2005 #2

    HallsofIvy

    User Avatar
    Science Advisor

    When you look at a problem like this and it means nothing to you, look at simple examples. Suppose A is the set {1,2,3} and B is {a,b}.
    1) First example. Define f by f(1)= a, f(2)= a, f(3)= a (f is neither 1-1 nor onto). The power set of B is {{}, {a}, {b}, {a,b}}. G({})= {}, of course, because every member of A is mapped into something. G({a})= {1, 2, 3} because every member of A is mapped into a. G({b})= {} because no member of A is mapped into b. G({a,b})= {1,2,3} because every member of A is mapped into a which is in {a,b}. This is not 1-1 because two different sets, {} and {a} are mapped into {} and, also, two different sets, {a} and {a,b} are mapped into {1, 2, 3}. It is not onto because there is no set which is mapped into, for example, {1}, a set in the powerset of A.
    2) Second example. g(1)= a, g(2)= a, g(3)= b (g is onto but not 1-1).
    G({})= {}, G({a})= {1,2}, G({b})= {3}, G({a,b})= {1, 2, 3}. Now G is 1-1 since no two members of the power set of B are mapped into the same thing. It is NOT onto because no set is mapped into, for example, {1, 2}.

    We can't give an example with these two sets of a 1-1 function because A has too many elements. Take A= {1,2}, B= {a,b,c} and define f(1)= a, f(2)= b. Now f is 1-1 but not onto. G({})= {}, G({a})= {1}, G({b})= {2}, G({c})= {}, G({a,b})= {1,2}, G({a,c})= {1}, G({b,c})= {2}, G({a,b,c})= {1,2}. G is onto but not 1-1.

    That's interesting. Perhaps we can simplify the problem by doing it as two separate parts:
    (1) the function G is 1-1 if and only if f is 1-1 and
    (2) the function G is onto if and only if f is onto.
     
  4. Oct 29, 2005 #3

    S&S

    User Avatar

    just say cheers

    I'm getting better.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook