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

1 Answer 1

up vote 3 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
    
Maybe I could ask you: following your hint, if $c\in$ LHS, then there was an $x\in X$ s.t. it is also in $f^{-1}(C))$ so that $f(c) \in C$. But since at this point, "onto" is not assumed, what is the meaning of $f^{-1}(C)$. Thanks. Regards, –  Andrew May 30 at 17:53
    
@Andrew You mean “$f(x) ∈ C$”. Other than that, the preimage of $C$ under $f$ is defined as $f^{-1}(C) = \{x ∈ X;~f(x) ∈ C\}$ and can be defined for any map $f$ – it doesn’t need to be surjective. (Maybe you thought of $f^{-1}(C)$ as the image of an inverse $f^{-1}$ of $f$ which would only exist if $f$ was already bijective. But that’s not how the symbol “$f^{-1}$” is used in this case.) –  k.stm May 31 at 0:39
    
Thanks - big help. –  Andrew May 31 at 1:10

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.