Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

For any function $f:A\rightarrow B$, define a new function $g:P(A)\rightarrow P(B)$ as follows: for every $S \subseteq A$, define $g(S)=\{f(x) \mid x\in S\}$. Prove that $f$ is onto if and only if $g$ is onto.

I'm not sure how to begin, and I'm particularly confused about what exactly $g(S)$ means. Is there any insight that may help me on my way to solve this? How can I show $f$ is onto $ \leftrightarrow g$ is onto?

Thank you!

share|improve this question
    
Draw potato pictures and arrows, and use the definition of onto and powerset.. –  Berci Oct 10 '12 at 1:47
    
@Berci, potato pictures? –  Gerry Myerson Oct 10 '12 at 1:54
1  
Bob, $g(S)$ means exactly what it says it means. If, for example, $S=\{{3,17,{\rm dog}\}}$, then $g(S)=\{{f(3),f(17),f({\rm dog})\}}$. –  Gerry Myerson Oct 10 '12 at 1:56
    
How can I show that $g$ is onto if it's domain is just the power set of $A$? –  Bob John Oct 10 '12 at 2:03
    
Sets can be elements as well, why does it disturb you? Just suppose an element of $P(B)$ is given and find for that a preimage in $P(A)$. –  Berci Oct 10 '12 at 2:11
show 2 more comments

1 Answer

A picture like this one may help a bit:

enter image description here

The black arrows show the function $f:A\to B$; the colored blobs show elements of $\wp(A)$ on the left and their images under $g$ in $\wp(B)$ on the right. The colored arrows show the action of $g$ on these sets.

Added: I’ll do one direction and leave the other to you. Suppose that $f$ maps $A$ onto $B$. To show that $g$ is onto, I must show that for each $Y\subseteq B$ there is some $X\subseteq A$ such that $g(X)=Y$, so let $Y$ be an arbitrary subset of $B$. Let $X=\{x\in A:f(x)\in Y\}$. (In other words, $X=f^{-1}[Y]$.) I claim that $g(X)=Y$.

To see this, recall that $g(X)=\{f(x):x\in X\}$; clearly $f(x)\in Y$ for each $x\in X$, since we chose $X$ to make that true, so $g(X)\subseteq Y$. On the other hand, the map $f$ is onto, so for each $y\in Y$ there is an $x\in A$ such that $f(x)=y$. Clearly this $x_y\in X$, so for each $y\in Y$ there is an $x\in X$ such that $f(x)=y$. Thus, $g(X)\supseteq Y$. Combining the inclusions, we see that $g(X)=Y$, so $Y$ is in the range of $g$. $Y$ was an arbitrary subset of $B$, so every subset of $B$ is in the range of $g$, and therefore $g$ must map $\wp(A)$ onto $\wp(B)$.

Now see if you can show that if $g$ is onto, so is $f$.

share|improve this answer
    
I understand the image, but I don't know how to apply the math behind it. –  Bob John Oct 10 '12 at 3:36
    
@Bob: I’ve added half of the proof; take a look, and then see if you can come up with the other half. –  Brian M. Scott Oct 10 '12 at 4:47
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.