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.)
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.
I approach such questions from both sides: try to find a proof and try to find a counterexample. If I get stuck in trying to prove it, perhaps there will be some missing property I can identify that prevents me from finding a proof. Or perhaps, when looking at examples I find that the statement is true for every example I try. In that case, perhaps I can use the examples to get a better idea of what is going on.
In this specific example, I start by trying to prove it. Since the statement is an equality of sets, I break that down into two containments:
$f(S \cap T) \subseteq f(S) \cap f(T)$?
I start by writing down the definition: $f(S \cap T) = \{f(x) : x \in S \cap T\}$. Then I write this down in words: an element of $f(S \cap T)$ looks like $f(x)$ where $x$ is in $S$ and $x$ is in $T$. Now I take this element, $f(x)$ and ask myself "is $f(x) \in f(S) \cap f(T)$?" which is equivalent to "is $f(x)$ in $f(S)$ and also in $f(T)$?"
Is $f(x) \in f(S)$? An element of $f(S)$ looks like $f(y)$ where $y \in S$. But $x \in S$ because $x \in S$ and $T$, thus $f(x) \in f(S)$. Likewise, $f(x) \in f(T)$ because $x \in T$.
So I have shown that every element of $f(S \cap T)$ is an element of $f(S)$ and of $f(T)$, which shows that $f(S \cap T) \subseteq f(S) \cap f(T)$.
$f(S) \cap f(T) \subseteq f(S \cap T)$?
An element of $f(S)$ looks like $f(x)$ where $x \in S$. An element of $f(T)$ looks like $f(y)$ where $y \in T$. So the element is both $f(x)$ and $f(y)$ so $f(x) = f(y)$ and I'm asking "is $f(x) = f(y)$ an element of $f(S \cap T)$?"
Before, we had $f(x) \in f(S \cap T)$ where $x \in S \cap T$ and we were able to use this $x$ to show that $f(x) \in f(S)$ and $f(x) \in f(T)$. Here we have two elements: $x$ and $y$. $x$ is an element of $S$, but not necessarily of $T$, and $y$ is an element of $T$, but not necessarily $S$. So the same method doesn't work. What we need is a third element $z \in S \cap T$ with $f(z) = f(x) = f(y)$.
A counterexample
Since it is not clear how to find such a $z$, let us instead try to find an example where there is no $z$. I note the equation $f(x) = f(y)$. And I say to myself: okay, $x$ and $y$ may lie in different sets but $f(x) = f(y)$. Well if $x$ and $y$ are in different sets then let's assume $x \ne y$ and $f(x) = f(y)$. This means that $f$ is not injective.
What's a simple example of a non-injective function? Let us try $f : \{0, 1\} \to \{0\}$ where $f(0) = f(1) = 0$. Can I find $S$ and $T$ where $f(S) \cap f(T) \not\subseteq f(S \cap T)$? Let us try $S = \{0\}$ and $T = \{1\}$. Then $f(S) = f(T) = \{0\}$ and $f(S \cap T) = f(\varnothing) = \varnothing$. So I have succeeded in finding a counterexample.
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.)
