Proving $f(C) \setminus f(D) \subseteq f(C \setminus D)$ and disproving equality

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?

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.

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.