6
$\begingroup$

Let $f: A\longrightarrow B$ be a function.

1)Prove that for any two sets, $C,D\subseteq A$ , we have $f(C) \setminus f(D)\subseteq f(C\setminus D)$.

2)Give an example of a function $f$, and sets $C$,$D$, for which $f(C) \setminus f(D) \neq f(C\setminus D)$

First time exposed to sets.. how would I go about proving this? What assumptions should I make?

$\endgroup$
  • $\begingroup$ You assume that $C$ and $D$ are subsets of $A$, and then you have to show that an arbitrary element of $f(C) - f(D)$ is in the set $f(C - D)$ using definitions you should know. If you are having problems trying to pick out "given" statements, or how to actually construct a proof, I'd look into the book How to Prove It by Velleman. $\endgroup$ – Tyler Oct 2 '13 at 1:26
  • $\begingroup$ Hint: for part (2), the function $f$ cannot be injective (one-to-one). Also, for both parts, the sets $A$ and $B$ are more or less irrelevant. $\endgroup$ – Trevor Wilson Oct 2 '13 at 3:54
  • $\begingroup$ Hello, welcome to Math.SE. Please, try to make the title of your questions more informative. E.g., Why does $a\le b$ imply $a+c\le b+c$? is much more useful for other users than A question about inequality. For more information on choosing a good title, see this post. $\endgroup$ – Lord_Farin Oct 2 '13 at 9:17
13
$\begingroup$

Since you’re new to this, instead of giving a hint, I’m going to show in detail how you might approach and solve both problems.

The most straightforward way to show that $X\subseteq Y$ is to let $x$ be an arbitrary element of $X$ and show somehow that this forces $x$ to belong to $Y$ as well. Here you have $f:A\to B$ and $C,D\subseteq A$, and you want to show that $f[C]\setminus f[D]\subseteq f[C\setminus D]$, so let $x\in f[C]\setminus f[D]$ be arbitrary. Then by the definition of set difference we know that $x\in f[C]$ and $x\notin f[D]$. Since $x\in f[C]$, there is some $c\in C$ such that $x=f(c)$. Can $c$ belong to $D$? No, because if $c\in D$, then $x=f(c)\in f[D]$, which we know is not the case. Therefore $c\in C\setminus D$, and $x=f(c)\in f[C\setminus D]$. In this argument we used no information about $x$ beyond the assumption that it belonged to $f[C]\setminus f[D]$, so we’ve just shown that every element of $f[C]\setminus f[D]$ is an element of $f[C\setminus D]$ and hence, by the definition of subset, that $f[C]\setminus f[D]\subseteq f[C\setminus D]$.

My argument is a bit wordy, because I’ve filled in some details that should very quickly become almost second nature; it could be condensed a fair bit and still be acceptable to a grader. However, when you’re just getting started it’s on balance better to say too much than to say too little: if you’re right, you’ll reassure the grader that you really do understand what you’re saying, and if you’re wrong, you’ll make it easier to see what misconception you have.

In order to construct an example in which $f[C]\setminus f[D]\ne f[C\setminus D]$, we’ll have to arrange matters so that $f[C]\setminus f[D]\subsetneqq f[C\setminus D]$. That means that we want to have something in $f[C\setminus D]$ that isn’t in $f[C]\setminus f[D]$. If $x\in f[C\setminus D]$, then there is a $c\in C\setminus D$ such that $x=f(c)$; clearly $c\in C$, so $x\in f[C]$. The only way to keep this $x$ out of $f[C]\setminus f[D]$ is to make sure that $x\in f[D]$. Thus, we need to make sure that there is some $d\in D$ such that $x=f(d)$. And that’s really all that we need to build our example. Let $A=\{c,d\}$, $B=\{x\}$, $C=\{c\}$, and $D=\{d\}$, and let $f$ be the only function from $A$ to $B$: $f(c)=f(d)=x$. Then

$$f[C]\setminus f[D]=f[\{c\}]\setminus f[\{d\}]=\{x\}\setminus\{x\}=\varnothing\;,$$

and

$$f[C\setminus D]=f[\{c\}\setminus\{d\}]=f[\{c\}]=\{x\}\;,$$

and certainly $\{x\}\ne\varnothing$.

When trying to construct an example with certain properties, ask yourself what has to happen in order for it to have those properties. Here there had to be distinct elements $c\in C\setminus D$ and $d\in D$ that $f$ sent to the same element of $B$. That turned out to be all we needed; in another problem you might have to work a bit harder. Another useful technique is to think about how you might try to prove that no such example exists; in the present setting that would mean proving that it’s always the case that $f[C]\setminus f[D]=f[C\setminus D]$. See where your attempt at a proof gets stuck, and try to see why it gets stuck; that often gives you a good idea of what a counterexample has to look like.

$\endgroup$
  • $\begingroup$ @Lord_Farin: Thanks! $\endgroup$ – Brian M. Scott Oct 2 '13 at 9:22
3
$\begingroup$

Here is a proof for the $\;\subseteq\;$ part, which goes back to the definitions and then uses predicate logic.

We start at the left hand side, and try to see which elements $\;y\;$ are in that set: for all $\;y\;$,

\begin{align} & y \in f[C] \setminus f [D] \\ \equiv & \;\;\;\;\;\text{"definition of $\;\setminus\;$"} \\ & y \in f[C] \;\land\; y \not\in f [D] \\ \equiv & \;\;\;\;\;\text{"definition of $\;\cdot[\cdot]\;$, twice"} \\ & \langle \exists x : f(x) = y : x \in C \rangle \;\land\; \lnot \langle \exists x : f(x) = y : x \in D \rangle \\ \equiv & \;\;\;\;\;\text{"DeMorgan"} \\ (*) \;\;\; \phantom\equiv & \langle \exists x : f(x) = y : x \in C \rangle \;\land\; \langle \forall x : f(x) = y : x \not\in D \rangle \\ \equiv & \;\;\;\;\;\text{"logic: use $\;\langle \forall x : f(x) = y : x \not\in D \rangle\;$ on other side of $\;\land\;$:} \\ & \;\;\;\;\;\phantom{\text{"}}\text{when simplifying $\;P\;$ in $\;P \land Q\;$ we may assume $\;Q\;$} \\ & \;\;\;\;\;\phantom{\text{"}}\text{-- to bring $\;C\;$ and $\;D\;$ together as in our goal"} \\ & \langle \exists x : f(x) = y : x \in C \land x \not\in D \rangle \;\land\; \langle \forall x : f(x) = y : x \not\in D \rangle \\ \Rightarrow & \;\;\;\;\;\text{"logic: weaken using $\;P \land Q \;\Rightarrow\; P\;$} \\ & \;\;\;\;\;\phantom{\text{"}}\text{-- the right hand part isn't needed anymore"} \\ (**) \;\;\; \phantom\equiv & \langle \exists x : f(x) = y : x \in C \land x \not\in D \rangle \\ \equiv & \;\;\;\;\;\text{"definition of $\;\setminus\;$"} \\ & \langle \exists x : f(x) = y : x \in C \setminus D \rangle \\ \equiv & \;\;\;\;\;\text{"definition of $\;\cdot[\cdot]\;$"} \\ & y \in f[C \setminus D] \end{align} By the definition of $\;\subseteq\;$ this proves $\;f[C] \setminus f [D] \;\subseteq\; f[C \setminus D]\;$.

Finally, to find a counterexample for the $\;=\;$ part, find $\;f,C,D\;$ for which the $\;\Rightarrow\;$ step above cannot be reversed.


If you get stuck at $(*)$ and the two following steps are too magical, then you can also work from the other side until you reach $(**)$, and then (by the definition of $\;\subseteq\;$) you're left with proving $$ \langle \exists x : f(x) = y : x \in C \rangle \;\land\; \langle \forall x : f(x) = y : x \not\in D \rangle \;\Rightarrow\; \langle \exists x : f(x) = y : x \in C \land x \not\in D \rangle $$ Now it is hopefully easier to see why we need to bring $\;x \in C\;$ and $\;x \not\in D\;$ together.

$\endgroup$
  • $\begingroup$ Would you please explain "use RH part in LH part" and "weaken -- the RH part isn't needed anymore", in your answer and not as a comment? $\endgroup$ – Greek - Area 51 Proposal Apr 11 '14 at 14:17
  • $\begingroup$ @LePressentiment I tried; does that help? $\endgroup$ – Marnix Klooster Apr 12 '14 at 8:09
  • $\begingroup$ +1. Thank you very much. It helpfully illumined me! Moreover, is it possible to rewrite your sterling proof without $y$? I was hoping to start with $f(x) \in f[C] \backslash f[D] \implies f(x) \in f[C\backslash D]$? $\endgroup$ – Greek - Area 51 Proposal Apr 13 '14 at 8:32
  • $\begingroup$ I'll also delight in +1 your other supernal answers. $\endgroup$ – Greek - Area 51 Proposal Apr 13 '14 at 8:33
0
$\begingroup$

enter image description here

Here, $f: A \rightarrow B$ is in green and $\{S_i\} = S_i$ for $S = A, B$ and $i = 1, 2.$
Ignore $\{b_2\} = B_2$ in this picture. This picture proves that $ f(A_1) - f(A_2) \neq f(A_1 - A_2)$. Incidentally, the same picture works for Is this proof correct for : Does $F(A)\cap F(B)\subseteq F(A\cap B) $ for all functions $F$?

$\endgroup$
0
$\begingroup$

This links to a resource of selected attempts to solutions for exercises of Terence Tao's Analysis I (2006) 1E. A proof for $f(C)\backslash f(D) \subseteq f(C \backslash D)$ and $f \hspace{0.2cm} \text{injective} \rightarrow f(C)\backslash f(D) = f(C \backslash D)$ can be found there.

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