Suppose f is a function from X to Y and A, B are subsets of X, and suppose that S, T are
subsets of Y.
prove that $f(A\cap B) \subseteq f(A) \cap f(B)$.
my working:
let $x\in A\cap B$, then $f(x) \in f(A \cap B)$.
$x\in A$ and $x\in B$ so $f(x) \in f(A)$ and $f(x) \in f(B)$.
so $f(x) \in f(A) \cap f(B)$
Hence the forward direction is proved. However, somehow, the backward direction can also be proved.
let $x\in A$ and $x\in B$, so $f(x)\in f(A)\cap f(B)$
$x\in A\cap B$ so $f(x) \in f(A \cap B)$
How come the answer isn't an equal sign, and where did I go wrong, ie which step was invalid?
Best Answer
You start the backwards direction like this:
This isn't a general description of every element in $f(A)\cap f(B)$. It may be two different values $x\in A,y\in B$ that produce the same output, $f(x)=f(y)\in f(A)\cap f(B)$.
Other people have given explicit counterexamples. In each case, note how it is two different elements from $A$ and $B$ that map to the same output that cause the issue.
By seeing exactly which step in your "proof" is wrong, we can construct a very simple counterexample: $A=\{0\},B=\{1\},f(0)=f(1)=2$. Observe that $f(A)\cap f(B)=\{2\}\cap\{2\}=\{2\}$, but $f(A\cap B)=f(\emptyset)=\emptyset$. This is a common technique in "proof or counterexample" situations - try to construct a proof, and if a step of logic is faulty, that tells you something about how to make a counterexample.