0
$\begingroup$

Let $ f:X \rightarrow Y$ be a map

Show that f is injective if and only if for any $y \in Y$ , the preimage $f^{−1}(y) \subseteq X$ is either empty or a singleton.

Since this is an if and only if question, i know that i would have to show it both ways $\Rightarrow$ and $\Leftarrow$

Starting with $\Rightarrow$ Since f is injective, every $x\in X$ has a unique $y \in Y$. So $\forall y\in Y$ , the preimage $f^{-1}(y) \subseteq X$ is a singleton/empty as every x has a y but not every y has an x.

Continuing with $ \Leftarrow$ The preimage $f^{−1}(y) \subseteq X$ is either empty or a singleton. Suppose that the preimage $f^{−1}(y) \subseteq X$ is not a singleton eg. $ f^{-1}(y) = (x_1, x_2)$. Then $y=f(x_1)=f(x_2)$, but $x_1 \neq x_2$, which shows that f is not injective. Which is a contradiction, thus the preimage $f^{-1}(y) \subseteq X$ has to be a singleton/empty for f to be injective

I'm not very certain about my answers so hoping someone could look through it and point out my mistakes. I think that my argument for $\Rightarrow$ isn't very rigorous but i'm not sure how to present it in a better way. Would appreciate if anyone could help me. Thank you!

edit: my proof for $\Leftarrow$ was actually a proof for $\Rightarrow$.

$\endgroup$
0
$\begingroup$

Actually, you proved "$\Rightarrow$" in twice, and your second attempt is totally fine while your first one is quite hand-waving. So lets do "$\Leftarrow$": Your assumption is, that the preimage of each $y$ is either empty or a singleton. We want to show that then $f$ must be injective. To do this fix $x_1,x_2$ such that $f(x_1)=f(x_2)$. If we choose $y:=f(x_1)$, then $f^{-1}(\{y\})$ is either empty or a singleton. But it cannot be empty, since $x_1$ is mapped to $y$. So it must be a singleton, namely $f^{-1}(\{y\})=\{x_1\}$. But since $x_2$ is also mapped to $y$ we have $x_2\in f^{-1}(\{y\})$, so $x_1=x_2$.

$\endgroup$
  • $\begingroup$ so there is a way to prove $\Leftarrow$ without contradiction. Is there a better way to prove $\Rightarrow$ though? $\endgroup$ – Helpisneeded Nov 30 '14 at 5:49
  • $\begingroup$ its important that you understand that your proof of $\Leftarrow$ was not correct, because you didnt prove $\Leftarrow$ but $\Rightarrow$ again. However, you can do it with a contradiction as well. I like your second attempt, so I would be totally convinced with that. $\endgroup$ – sranthrop Nov 30 '14 at 5:52
  • $\begingroup$ oh my proof for $\Leftarrow$ was actually for $\Rightarrow$? Thanks for pointing that out! $\endgroup$ – Helpisneeded Nov 30 '14 at 6:00
  • $\begingroup$ Yes, because you used that $f$ is injective to show that the preimage is empty or a singleton, and this is what $\Rightarrow$ asked for ;) $\endgroup$ – sranthrop Nov 30 '14 at 6:03
  • $\begingroup$ i see it now. Thanks again! $\endgroup$ – Helpisneeded Nov 30 '14 at 6:06
1
$\begingroup$

Just to point out in more detail what sranthrop already said: your purported proof of $\Leftarrow$ does not do what claims. You can see this from the curious bend that after stating its hypothesis that $f^{-1}(y)$ is always either empty or a singleton, you go assuming that it has two elements anyway (which you should have written as $f^{-1}(y)\supseteq\{x_1,x_2\}$ rather than as $f^{-1}(y)=(x_1,x_2)$, but it is wrong anyway). One doesn't go out contradicting the hypothesis of what one wants to prove; a proof by contradiction presumes the negation of the conclusion.

So your purported proof of $\Leftarrow$ actually shows (after cleaning it up) that for an injective function any $f^{-1}(y)$ cannot contain two distinct elements, hence must be either empty or a singleton. For a not-by-contradction proof of that direction, you could argue that if it is not one case, then it must be the other (a typical strategy for proving an "or" conclusion). In other words assume $y$ is so that $f^{-1}(y)$ is not empty, say $x\in f^{-1}(y)$. Then $f(x)=y$, and by injectivity $f(x')=y$ is only possible if $x'=x$. This shows that $f^{-1}(y)=\{x\}$; QED.

$\endgroup$
  • $\begingroup$ Thank you for pointing out my mistakes and giving another example. I'll keep in mind the part on 'One doesn't go out contradicting the hypothesis of what one wants to prove; a proof by contradiction presumes the negation of the conclusion.' :) $\endgroup$ – Helpisneeded Nov 30 '14 at 7:21

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.