# $f:X\to Y$, $A,B,\subseteq X$. Show that $f(A\setminus B)=f(A)\setminus f(B)$ iff $f(A\setminus B)\cap f(B) =\emptyset$

I tried to prove this but I am not sure if its correct. Please help me out with any tips or advice on how to improve. Here it is:

First let $f(A\setminus B)\cap f(B)=\emptyset$. Now $$f(A\setminus B)=(f(A)\setminus f(B)) \cup \{ y\in Y| \exists (x_1 \in (A\setminus B), x_2\in B) |f(x_1)=f(x_2 ) \}.$$ Now by the hypothesis $f(A\setminus B)\cap f(B)=\emptyset$ we have that $\nexists (x_1 \in (A\setminus B), x_2\in B) |f(x_1)=f(x_2 )$. Thus $$f(A\setminus B)=(f(A)\setminus f(B)) \cup \emptyset=f(A)\setminus f(B).$$ Now for the reverse implication we assume that $f(A\setminus B)=f(A)\setminus f(B)$. We intersect both sides with $f(B)$ to obtain

$$f(A\setminus B)\cap f(B)=(f(A)\setminus f(B))\cap f(B)=\emptyset.$$

So this is my proof. I personally think it's correct but very unclear possible. Any help or verification will be appreciated. Thanks in advance

The first part of the proof is very unclear to me. I personally would like to show that both sets are subsets of each other to prove a set equality. Here's my humble suggestion:

Suppose $f(A \setminus B)∩f(B)= \emptyset$:

$y \in f(A \setminus B) \implies \exists x \in (A \setminus B)$ such that $f(x) = y$. Since $x \in A$, $y = f(x) \in f(A)$. Furthermore due to our hypothesis, $y \in f(A \setminus B) \implies y \notin f(B)$.

Since $y \in f(A)$ and $y \notin f(B)$, $y \in f(A) \setminus f(B)$
$\implies f(A \setminus B) \subseteq f(A) \setminus f(B)$ --------- $(1)$

Now say $y \in f(A) \setminus f(B)$. This says $\exists x \in A$ such that $y = f(x)$ and there is no $x' \in B$ such that $y = f(x')$. Clearly $x \in A$ and $x \notin B \implies x \in A \setminus B \implies y = f(x) \in f(A \setminus B)$

This implies $f(A) \setminus f(B) \subseteq f(A \setminus B)$ ----------------- $(2)$

Equations $(1)$ and $(2)$ provide the set equality.

The second part of the proof is impressive by the way..

• Thanks a lot, your way of showing the first part is indeed a lot clearer than what I had. – Slugger Feb 13 '14 at 20:09
• @Slugger Glad to be of help.. – Ishfaaq Feb 14 '14 at 6:23

Assume that $f\left(A\backslash B\right)=f\left(A\right)\backslash f\left(B\right)$.

If $y\in f\left(A\backslash B\right)$ then $y\in f\left(A\right)\backslash f\left(B\right)$ so that $y\notin f\left(B\right)$ this proves that $f\left(A\backslash B\right)\cap f\left(B\right)=\emptyset$.

Assume that $f\left(A\backslash B\right)\cap f\left(B\right)=\emptyset$ or equivalently $f\left(A\backslash B\right)\subset f\left(B\right)^{c}$.

From $A\backslash B\subset A$ it follows that $f\left(A\backslash B\right)\subset f\left(A\right)$. Then $f\left(A\backslash B\right)\subset f\left(A\right)\cap f\left(B\right)^{c}=f\left(A\right)\backslash f\left(B\right)$. Conversely, if $y\in f\left(A\right)\backslash f\left(B\right)$ then $y=f\left(x\right)$ for some $x\in A$, and $x\in B$ cannot be true (because that would imply that $y\in f\left(B\right)$). So $x\in A/B$ and consequently $y=f\left(x\right)\in f\left(A\backslash B\right)$. This proves that $f\left(A\right)\backslash f\left(B\right)\subset f\left(A\backslash B\right)$.

Hint:

• Use $$X \setminus Y = X \cap Y^c,$$ and $$\big(f(B)\big)^c \cap f(B \cup B^c) \subseteq f(B^c). \tag{\spadesuit}$$
• $(\Rightarrow)$ From the assumption we get $f(A \cap B^c) = f(A) \cap \big(f(B)\big)^c \subseteq \big(f(B)\big)^c.$
• $(\Leftarrow)$ From $f(A \cap B^c) \subseteq \big(f(B)\big)^c$ we get $\subseteq$ and from $(\spadesuit)$ we get $\supseteq$ .

I hope this helps $\ddot\smile$

• @Slugger While the "logic" approach (i.e. translating sets into $x \in X \lor y \in Y$ and other similar expressions) is in most cases easier, I would recommend you, to try translate it back to set-operation way, as this would give you more intuition. I'm not arguing that this is the best way, only that after the first "logic" approach is successful, try to make a second proof using set-operations and relations. It really does help. – dtldarek Feb 13 '14 at 22:14

Here is another full proof, relying more on the symbols than the earlier answers, but therefore more mechanical as well: start at the most complex side, expand the definitions, simplify, and take it from there.

We calculate as follows:

\begin{align} & f[A \setminus B] = f[A] \setminus f[B] \\ = & \qquad \text{"set extensionalify; definition of $\;\setminus\;$"} \\ & \langle \forall y :: y \in f[A \setminus B] \;\equiv\; y \in f[A] \land \lnot (y \in f[B]) \rangle \\ = & \qquad \text{"basic property of $\;\cdot[\cdot]\;$, three times"} \\ & \langle \forall y :: \langle \exists x : f(x) = y : x \in A \land \lnot (x \in B) \rangle \\&\phantom{\langle \forall y :: } \equiv\; \langle \exists x : f(x) = y : x \in A \rangle \land \lnot \langle \exists x : f(x) = y : x \in B \rangle \rangle \\ = & \qquad \text{"the last part is equivalent to $\;\langle \forall x : f(x) = y : \lnot(x \in B) \rangle\;$ by} \\ & \qquad \phantom{\text{"}}\text{DeMorgan: use this to add $\;\lnot(x \in B)\;$ on other side of $\;\land\;$ -- this} \\ & \qquad \phantom{\text{"}}\text{makes the right hand side of $\;\equiv\;$ more similar to the left hand side"} \\ & \langle \forall y :: \langle \exists x : f(x) = y : x \in A \land \lnot (x \in B) \rangle \\&\phantom{\langle \forall y :: } \equiv\; \langle \exists x : f(x) = y : x \in A \land \lnot (x \in B) \rangle \land \lnot \langle \exists x : f(x) = y : x \in B \rangle \rangle \\ = & \qquad \text{"logic: simplify $\;P \equiv P \land \lnot Q\;$ to $\;\lnot (P \land Q)\;$"} \\ & \langle \forall y :: \lnot ( \langle \exists x : f(x) = y : x \in A \land \lnot (x \in B) \rangle \land \langle \exists x : f(x) = y : x \in B \rangle ) \rangle \\ = & \qquad \text{"basic property of $\;\cdot[\cdot]\;$, twice"} \\ & \langle \forall y :: \lnot (y \in f[A \setminus B] \land y \in f[B]) \rangle \\ = & \qquad \text{"definition of $\;\cap\;$; basic property of $\;\emptyset\;$"} \\ & f[A \setminus B] \cap f[B] = \emptyset \\ \end{align}

This completes the proof.

If you want to see the above logical simplification in more detail, we have \begin{align} & P \;\equiv\; P \land \lnot Q \\ = & \qquad \text{"$\;p \equiv p \land q\;$ is one of the ways to write $\;p \Rightarrow q\;$"} \\ & P \;\Rightarrow\; \lnot Q \\ = & \qquad \text{"$\;\lnot p \lor q\;$ is another way to write $\;p \Rightarrow q\;$"} \\ & \lnot P \lor \lnot Q \\ = & \qquad \text{"DeMorgan"} \\ & \lnot (P \land Q) \\ \end{align}