4
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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$. $\endgroup$ – Asaf Karagila Nov 5 '11 at 18:37
  • 3
    $\begingroup$ 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. $\endgroup$ – Josué Tonelli-Cueto Nov 5 '11 at 18:37
  • $\begingroup$ +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. $\endgroup$ – Srivatsan Nov 5 '11 at 18:47
  • $\begingroup$ @asaf, yes, sorry, you are right, it's actually only written "prove the following statements: 1, 2, 3" $\endgroup$ – Clash Nov 5 '11 at 18:56
  • $\begingroup$ @IasafroMaesman thanks for the example! $\endgroup$ – Clash Nov 5 '11 at 21:34
10
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ @Srivatsan: Indeed. This is what happens when someone checks mathstackexchange as a break from studying. Thanks :) $\endgroup$ – Apostolos Nov 5 '11 at 19:59
  • $\begingroup$ You have some $\inf$ instead of $\in f$, I think. ($1\Leftrightarrow 2$) $\endgroup$ – Asaf Karagila Nov 5 '11 at 20:26
  • $\begingroup$ @Asaf: Thanks as well. $\endgroup$ – Apostolos Nov 5 '11 at 21:39
  • $\begingroup$ 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 $\endgroup$ – Clash Nov 5 '11 at 22:34
  • $\begingroup$ 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]$? $\endgroup$ – Clash Nov 5 '11 at 22:56

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.