# Conditions Equivalent to Injectivity

Let $A$ and $B$ be sets, where $f : A \rightarrow B$ is a function. Show that the following properties are valid equivalent*:

1. $f$ is injective.
2. For all $X, Y \subset A$ is valid: $f(X \cap Y)=f(X)\cap f(Y)$
3. For all $X \subset Y \subset A$ is valid: $f(X \setminus Y)=f(X) \setminus f(Y)$.

I do know what injective is, but I thought number (2.) and (3.) were valid for any kind of function. Just to see if I understood this right:

$f(X\cap Y)$ means, first, make the intersection from $X$ and $Y$ and then map it to $B$ via $f$.

$f(X)\cap f(Y)$ actually means, map all $f(X)$ and $f(Y)$ and intersect both.

Aren't those both properties valid for all functions? I can't think of a counter example. Thanks in advance guys!

*edited by SN.

-
Are you sure that it was not meant to be "the following properties are equivalent"? A function is injective if it is 1-1, that is $f(x)=f(y)\iff x=y$. –  Asaf Karagila Nov 5 '11 at 18:37
No, they are not; take $A=\{1,2\}$, $B=\{1\}$, and $f:A\rightarrow B$ the constant function. Then we have for $X=\{1\}$ and $Y=\{2\}$ that $f(X\cap Y)=\varnothing\subset\{1\}=f(X)\cap f(Y)$. So the property is not for all functions. –  Josué Tonelli-Cueto Nov 5 '11 at 18:37
+1 for @Asaf's comment. I assumed that the question should read "equivalent" instead of "valid" and edited it to reflect this. Hopefully it's ok. –  Srivatsan Nov 5 '11 at 18:47
@asaf, yes, sorry, you are right, it's actually only written "prove the following statements: 1, 2, 3" –  Clash Nov 5 '11 at 18:56
@IasafroMaesman thanks for the example! –  Clash Nov 5 '11 at 21:34

No they are not true for any function:

Take a function $f:\{0,1\}\to\{0,1\}$ such that $f(0)=1$ and $f(1)=1$. Then $f[\{0\}\cap\{1\}]=f[\varnothing]=\varnothing$ but $f[\{0\}]\cap f[\{1\}]=\{1\}\cap\{1\}=\{1\}$. This function provides a counterexample for the second case as well: $f[\{0,1\}\setminus\{0\}]=\{1\}$, while $f[\{0,1\}]\setminus f[\{0\}]=\{1\}\setminus\{1\}=\varnothing$.

Note that for any function $f$ it is true that $f[X\cap Y]\subseteq f[X]\cap f[Y]$ and it is also true that $f[X]\setminus f[Y]\subseteq f[X\setminus Y]$.

As for the equivalence, a function $f$ is called injective exactly when $x\neq y$ implies $f(x)\neq f(y)$ (or equivalently $f(x)=f(y)$ implies $x=y$). They are sometimes called $1-1$:

$1\Rightarrow 2$. Let $f:A\to B$ be injective. We just need to show that $f[X]\cap f[Y]\subseteq f[X\cap Y]$. Let $x\in f[X]\cap f[Y]$. Then there is some $a\in X$ and some $b\in Y$ such that $f(a)=f(b)=x$. By the definition of injective functions $a=b$ thus $a\in X\cap Y$ or $x\in f[X\cap Y]$.

$2\Rightarrow 1$. Now let $f[X]\cap f[Y]=f[X\cap Y]$. Let $f(a)=f(b)$. We have that $f[\{a\}\cap\{b\}]=f[\{a\}]\cap f[\{b\}]$. Thus $f[\{a\}\cap\{b\}]$ is not empty (since it is equal to $f[\{a\}]\cap f[\{b\}]$ which is not). Therefore $\{a\}\cap\{b\}$ is not empty, which means that $a=b$.

$1\Rightarrow 3$. Let $f:A\to B$ be injective. We just need to show that $f[X\setminus Y]\subseteq f[X]\setminus f[Y]$. Let $x\in f[X\setminus Y]$. Of course $x\in f[X]$. We have that there is some $a\in X\setminus Y$ such that $f(a)=x$. For every $b\in Y$ we have that $a\neq b$ thus $f(a)\neq f(b)$. Thus $x\notin f[Y]$ and thus $x\in f[X]\setminus f[Y]$.

$3\Rightarrow 1$. Conversely assume that $f[X\setminus Y]= f[X]\setminus f[Y]$. Let $f(a)=f(b)$. Then $f[\{a,b\}\setminus\{b\}]=f[\{a,b\}]\setminus f[\{b\}]$. The second set is empty, thus $f[\{a,b\}\setminus\{b\}]$ is empty. Then $\{a,b\}\setminus\{b\}$ is empty, which means $a=b$.

-
@Srivatsan: Indeed. This is what happens when someone checks mathstackexchange as a break from studying. Thanks :) –  Apostolos Nov 5 '11 at 19:59
You have some $\inf$ instead of $\in f$, I think. ($1\Leftrightarrow 2$) –  Asaf Karagila Nov 5 '11 at 20:26
@Asaf: Thanks as well. –  Apostolos Nov 5 '11 at 21:39
Hi Apostolos! Thank you for reply, do you mind explaining me this last part of the first proof? "Thus $f[\{a\}\cap\{b\}]=f[\{a\}]$ is not empty" Why is it that equal to $f[\{a\}]$, is it because $f(a)=f(b)$? Thanks in advance –  Clash Nov 5 '11 at 22:34
I actually don't understand the proof. For the first one, so in the end a=b, how did this prove $f[X]\cap f[Y]\subseteq f[X\cap Y]$? –  Clash Nov 5 '11 at 22:56