Can someone teach me this problem of sets.

1. Oct 28, 2005

S&S

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.

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. Oct 28, 2005

HallsofIvy

Staff Emeritus
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.

3. Oct 29, 2005

S&S

just say cheers

I'm getting better.