2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

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

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

$\endgroup$
1
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ @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. $\endgroup$ – dtldarek Feb 13 '14 at 22:14
1
$\begingroup$

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}

$\endgroup$

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.