Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
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
3  
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
add comment

1 Answer 1

up vote 7 down vote accepted

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

share|improve this answer
    
@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
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.