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.

I am struggling to prove this map statement on sets.

The statement is:

Let $f:X \rightarrow Y$ be a map.

i) $\forall_{A,B \subset X}: f(A \cup B)=f(A) \cup f(B)$
ii) $\forall_{A,B \subset X}: f(A \cap B) \subset f(A) \cap f(B)$
iii) $f$ is injective $ \Longleftrightarrow$ $\forall_{A,B \subset X}: f(A \cap B)=f(A) \cap f(B)$

My problem is: I know how to operate on sets, I know how to operate on sets, but I don't know how and where to start the proof, the biggest problem in mathematics, I think.

Thanks for help!

share|improve this question
    
There must be some mistake in (ii). Check this. –  DonAntonio Nov 18 '12 at 12:43
2  
To show that two sets $U$ and $V$ are equal, usually one introduces a letter, denoting an arbitrary element of $U$ and shows that it is also an element of $V$, and vice-versa.\ –  Berci Nov 18 '12 at 12:52
    
see my update, it was typo –  doniyor Nov 18 '12 at 13:43

3 Answers 3

up vote 4 down vote accepted

For the first $y \in f(A \cup B) \iff y=f(x)$ for some $x \in A \cup B \iff y = f(x)$ for some $x \in A$ or $x \in B \iff y \in f(A)$ or $y \in f(B) \iff y \in f(A)\cup f(B).$

The second should be $f(A\cap B)\subseteq f(A)\cap f(B)$ and the proof is similar.

For the third if $f(A \cap B) = f(A) \cap f(B) \Rightarrow$ for every $x,y \in X$ with $x \neq y, \ \emptyset=f(\emptyset)=f(\{x\} \cap \{y\}) = f(\{x\}) \cap f(\{y\})$. Thus $f(x)\neq f(y)$ and $f$ is injective. Can you prove the other direction?

This is the difficult one. In case you give up here is the solution:

Its enough to show that if $f(A \cap B) \subset f(A) \cap f(B)$ for some $A,B \subseteq X$ then $f$ is not injective. So we suppose that there is a $y \in f(A) \cap f(B)$ s.t. $y \not \in f(A \cap B)$. So $y=f(x_1)=f(x_2)$ for some $x_1 \in A-(A\cap B)$ and $x_2 \in B-(A\cap B)$. I believe now is finished.

share|improve this answer
    
Thanks Pambos , thats you again! :D –  doniyor Nov 18 '12 at 13:47
    
@doniyor Anytime. –  P.. Nov 18 '12 at 14:00
    
yeah, let me try the other direction now –  doniyor Nov 18 '12 at 14:21
    
$f(x) \neq f(y) \Longrightarrow f(\{x\}) \cap f(\{y\}) = \emptyset \Longrightarrow x \neq y$ for $x,y \in X $ –  doniyor Nov 18 '12 at 14:31
    
Not exactly. What did you prove here? I think you proved here that $f$ is a function (i.e. if $x=y$ then $f(x)=f(y)$). –  P.. Nov 18 '12 at 14:41

$$(i)\;\;\;\;\forall x\in f(A\cup B)\Longrightarrow \exists z\in A\cup B\,\,s.t.\,\,f(z)=x\,.$$

$$\,\,\text{If}\,\,z\in A\Longrightarrow x\in f(A)\;;\;\text{if}\,\,z\in B\Longrightarrow x\in f(B)\Longrightarrow x\in f(A)\cup f(B)$$

Now you do the other direction

Now prove $\,f(A\cap B)\subset f(A)\cap f(B)\,$ , and equality can be proved only if $\,f\,$ is $\,1-1$

share|improve this answer
    
thanks a lot, nicely explained! –  doniyor Nov 18 '12 at 13:49

Recall that $y\in f(C)\iff \exists x\in C:f(x)=y$. Using this you should be able to show that $y\in f(A\cup B)\iff y\in f(A)\text{ or }y\in f(B)\iff y\in f(A)\cup f(B)$ and so on.

share|improve this answer

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.