# Prove that $f$ is onto if and only if $g$ is onto

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!

-
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
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

A picture like this one may help a bit:

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$.

-
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