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!

  • $\begingroup$ Draw potato pictures and arrows, and use the definition of onto and powerset.. $\endgroup$ – Berci Oct 10 '12 at 1:47
  • $\begingroup$ @Berci, potato pictures? $\endgroup$ – Gerry Myerson Oct 10 '12 at 1:54
  • 1
    $\begingroup$ 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})\}}$. $\endgroup$ – Gerry Myerson Oct 10 '12 at 1:56
  • $\begingroup$ How can I show that $g$ is onto if it's domain is just the power set of $A$? $\endgroup$ – Bob John Oct 10 '12 at 2:03
  • $\begingroup$ 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)$. $\endgroup$ – Berci Oct 10 '12 at 2:11

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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