0
$\begingroup$

Let $f:X\rightarrow Y$ a function. Prove that $f$ is injective if and only if, for every pair of subsets $A$ and $B$ in $X$, we have $f(A\backslash B)=f(A)\backslash f(B)$.

The first part ($\Rightarrow$) I found easy to do. But the second part ($\Leftarrow$), all the ideas I had got me nowhere. For example, one of the ideas I had is making $f(x_1)=f(x_2)$ and try to prove that $x_1=x_2$. But I don't know how to start it. Should I separate in cases, like $f(x_1)$ and $f(x_2)$ belongs to $f(A)$ but not $f(B)$, and then the other cases...? I tried that but I got confused. The other way I tried is supposing and absurd that $f(x_1)=f(x_2)$ but $x_1\neq x_2$. And again I got stuck.

I am only asking here for a tip. Thanks.

$\endgroup$
  • 1
    $\begingroup$ The advantage of using the contrapositive approach is that $\lnot \forall$ becomes $\exists \lnot$, so you just need to find one particular $A,B$ counterexample given your $x_1,x_2$ counterexample. $\endgroup$ – aschepler Aug 13 at 17:01
  • 1
    $\begingroup$ In your example let $A = \{x_1,x_2\}$ and $B = \{x_1\}$ $f(A\setminus B) = f(\{x_2\})= \{f(x_2)\} = \{f(x_1)\}$. But $f(A) = \{f(x_1),f(x_2)\} = \{f(x_2)\} = \{f(x_1)\}$ whil $f(B) = f(\{x_1\})=\{f(x_1)\} = \{f(x_2)\}$. So $f(A)\setminus f(B) = \{f(x_1)\}\setminus \{f(x_1)\} =\emptyset$. So $f(A\setminus B)=\{f(x_1)\}\ne \emptyset =f(A)\setminus f(B)$. $\endgroup$ – fleablood Aug 13 at 19:11
2
$\begingroup$

Suppose $f(x)=f(y)$ and $x\neq y$. Use $A = \{x,y\}$ and $B=\{y\}$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Simple and easy. I did the contrapositive. Thanks. $\endgroup$ – Dunck Aug 13 at 17:41
  • $\begingroup$ Isn't it enough to use $A=\{x\},B=\{y\}$, since $f(A\backslash B)=f(\{x\})=\{y\}$ and $f(A)\backslash f(B)=\{y\}\backslash \{y\}=\phi$? $\endgroup$ – Mandelbrot Aug 13 at 17:52
  • $\begingroup$ Let $y\in f(A\setminus B)$. Then $y=f(x)$, $x\in A\setminus B$. So $y\in f(A)$. We need to show that $y\notin f(B)$. If $y\in f(B)$, then $y=f(x')$ for some $x'\in B$. Then $f(x')=y=f(x)$. Since $f$ is injective, $x=x'\in B$. This is a contradiction. Indeed, $y\in f(A)\setminus f(B)$. $\endgroup$ – morphy22 Sep 10 at 7:48
1
$\begingroup$

Suppose: for all $A,B \subset X$ that $f(A\setminus B) = f(A)\setminus f(B)$.

Let $x \in X$.

Let $A = f^{-1}(f(x)) = \{v \in X| f(v) = f(x)\}$ and let $B= \{x\}$

Note: $x \in A$ obvious, and if $f$ is injective that imply that $A = \{x\}$ and has no other elements. That is what we will prove.

Then $f(A\setminus B) = \{f(v)| f(v)=f(x);v\ne x\}$. If $f$ is injective this will be empty. And if this is not empty then $f$ is not injective.

And $f(A) = \{f(v)|f(v)=f(x)\} = \{f(x)\}$. And $f(B) =\{f(x)\}$. So $f(A) \setminus f(B) = \emptyset$.

And that's that. $f(A\setminus B)= f(A) \setminus f(B) = \emptyset$ so there is no $v\ne x$ so that $f(v) = f(x)$

and this is true for all $x\in X$ (and therefore for all $f(x) \in f(X)$) and $f$ is injective.

| cite | improve this answer | |
$\endgroup$

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.