Discrete Mathematics (Prove or Find a Counterexample of a Proposition) Let f : X → Y be a function. For each of the following propositions, prove or find a counterexample. (In constructing a counterexample, please specify what your domain and codomain are as well as the function itself.)


If S,T ⊆ X then f(S ∩ T) = f(S) ∩ f(T). 



Can somebody please show me how to solve this type of problem? I have other similar problems and need to learn the process for solving them. Thank you!
Usually what I do, if I'm not sure whether a statement is true or not is I start trying to prove it and if I hit a spot where I feel like I can't finish my proof because some condition doesn't seem to hold then I try and come up with an example where that happens.  My hope is that the example will either be a counterexample or it will indicate to me how to get around my difficulty.

For your problem you want to prove two sets are equal so you prove that each is contained in the other.  We'll just start proving and see if we get stuck...

Step 1) Assume $x \in f(S \cap T)$ and prove that $x \in f(S) \cap f(T)$.

If $x \in f(S \cap T)$ then there is a $y \in S \cap T$ such that $f(y) = x$.  Now $y \in S \cap T$ means $y \in S$ and $y \in T$.  That $y \in S$ and $f(y) = x$ means $x \in f(S)$.  Similarly $y \in T$ gives $x \in f(T)$.  Now we have $x \in f(S)$ and $x \in f(T)$ so $x \in f(S) \cap f(T)$.  Done.

Step 2) Assume $x \in f(S) \cap f(T)$ and prove that $x \in f(S \cap T)$.

Assume $x \in f(S) \cap f(T)$.  Then $x \in f(S)$ and $x \in f(T)$.  That $x \in f(S)$ means there is a $y \in S$ such that $f(y) = x$.  That $x \in f(T)$ means there is a $z \in T$ such that $f(z) = x$... hmmm.  I need the element that hits $x$ to be in both $S$ and $T$ at the same time, but right now I have two different elements.  If they were the same, $y = z$, then I'm done, but why does this need to be the case?  If the function were injective we would get that, but there are functions that are not injective.  In fact, now that I think about it, why would $S$ and $T$ need to intersect at all?  Maybe this means it's not true.

Counterexample:

Ok, we got stuck.  If the function isn't injective then I can't seem to get any further.  So for my counterexample I want a $z$ and a $y$ that both map to $x$, but $z \neq y$.  So what about the function $f\colon\{1, 2\} \to \{1\}$ defined by $f(1) = f(2) = 1$.  Then I choose $S = \{1\}$ and $T = \{2\}$.  Now with this explicit choice for $f, S, T$ figure out what $f(S \cap T)$ and $f(S) \cap f(T)$ are.  Are they the same?  If not you have a counterexample.  If yes, then maybe the example you chose wasn't the right one to be a counterexample, or maybe the theorem is true and there is no counter example.  There's no sure fire way to know which case your in, this is where experience and intuition are helpful.
When I have a problem that asks me to prove something, I first try to convince myself if it is true. If I don't believe it, then I start out by trying to find a counterexample. When I look at your problem statement, I notice that we do have $f(S \cap T) \subseteq f(S) \cap f(T)$. So the only question is whether or not $f(S) \cap f(T) \subseteq f(S \cap T)$. At this point, I would notice that we did not assume that the function $f$ is one-to-one. Hence, I would build a counterexample: Pick an $s \in S$ for which $s \not\in T$ and a $t \in T$ for which $t \not\in S$. What happens if $f(s) = f(t)$? We would get a counterexample.

However, if I have trouble finding a counterexample, I may then try to prove the statement instead. (This is extremely similar to what Jim wrote at the beginning of his answer.)