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!
Best Answer
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$.