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.

Show that a map $f:X\to Y$ is onto iff $f(f^{-1}(C))=C$ for all subsets $C\subseteq Y$.

My workings so far: Because this is an if and only if proof we need to show it both ways. First let's assume $f$ is onto, that is, $\forall y\in Y\ \ \exists x\in X$ such that $f(x)=y$. Now $$f^{-1}(C)=\{ x\in X| f(x)\in C \}$$ Let $f^{-1}(C)=D \subseteq X$ for simplicity. This means $D$ is the subset of $X$ containing all $x$ that get mapped to an element in $C$ under the map $f$. Now $$f(f^{-1}(C))=f(D)=\{ y\in Y | \exists x \in D | f(x)=y \}$$ We can be sure this set is well defined by the fact that $f$ is onto. By the previous definition of $D$ it seems rather trivial that $f(D)=C$. Is this enough to prove the statement in this direction. Maybe using the more elaborate notation $$f(f^{-1}(C))=\{ y\in Y | (\exists x \in \{ x\in X| f(x)\in C \}) | f(x)=y \}$$ Makes it a little bit more obvious (if possibly more confusing).

Now for the other direction we assume that $f(f^{-1}(C))=C$ for all $C\subseteq Y$. Here I really have no idea how to get started. If anyone could point me in the right direction and possible check if argument for the first part is rigorous enough that would be great!

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

Regarding your workings: The set $f(f^{-1}(C)) = f(D)$ is always defined, even if $f$ isn’t onto. And yes, it can be seen quite easily by looking long enough at the definition of the set that it is indeed $C$ if $f$ is onto. But exercises like this often try to provoke a more low-level approach, as if asked: How low-level can you go? Use the definition of set-equality.

Hint: Show more generally $f(f^{-1}(C)) \subseteq C$ for all $C \subseteq Y$ without assuming the surjectivity of $f$. Do this by following an arbitrary element of the left hand side.

Then, assuming surjectivity of $f$, show for every $c ∈ C$ there is an $b ∈ f^{-1}(C)$ such that $f(b) = c$, so $c ∈ f(f^{-1}(C))$, meaning $C \subseteq f(f^{-1}(C))$.

By definition of equality of sets, the assertion follows.

For the other direction, consider singletons $C = \{y\}$ for $y ∈ Y$.

share|improve this answer
    
Hey, Thanks for your answer. I always get so mixed up in these sorts of proofs. Indeed I usually have trouble going low-level enough. –  Slugger Feb 18 '13 at 18:43
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.