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!

  • 1
    $\begingroup$ There must be some mistake in (ii). Check this. $\endgroup$ – DonAntonio Nov 18 '12 at 12:43
  • 2
    $\begingroup$ 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.\ $\endgroup$ – Berci Nov 18 '12 at 12:52
  • $\begingroup$ see my update, it was typo $\endgroup$ – doniyor Nov 18 '12 at 13:43

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.

  • $\begingroup$ Thanks Pambos , thats you again! :D $\endgroup$ – doniyor Nov 18 '12 at 13:47
  • $\begingroup$ @doniyor Anytime. $\endgroup$ – P.. Nov 18 '12 at 14:00
  • $\begingroup$ yeah, let me try the other direction now $\endgroup$ – doniyor Nov 18 '12 at 14:21
  • $\begingroup$ $f(x) \neq f(y) \Longrightarrow f(\{x\}) \cap f(\{y\}) = \emptyset \Longrightarrow x \neq y$ for $x,y \in X $ $\endgroup$ – doniyor Nov 18 '12 at 14:31
  • $\begingroup$ 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)$). $\endgroup$ – 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$

  • $\begingroup$ thanks a lot, nicely explained! $\endgroup$ – 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.


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.