# 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$. Commented Nov 5, 2011 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. Commented Nov 5, 2011 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. Commented Nov 5, 2011 at 18:47
• @asaf, yes, sorry, you are right, it's actually only written "prove the following statements: 1, 2, 3" Commented Nov 5, 2011 at 18:56
• @IasafroMaesman thanks for the example! Commented Nov 5, 2011 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 :) Commented Nov 5, 2011 at 19:59
• You have some $\inf$ instead of $\in f$, I think. ($1\Leftrightarrow 2$) Commented Nov 5, 2011 at 20:26
• @Asaf: Thanks as well. Commented Nov 5, 2011 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 Commented Nov 5, 2011 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]$? Commented Nov 5, 2011 at 22:56