4
$\begingroup$

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!

  • 0
    see my update, it was typo2012-11-18

3 Answers 3

6

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)$. The proof now is finished.

  • 0
    wow, thanks man, what a beautiful mathematics! :)2012-11-18
3

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

  • 0
    thanks a lot, nicely explained!2012-11-18
2

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.