1
$\begingroup$

How do I prove that: $f(S ∩ T) \neq f(S) ∩ f(T)$ unless $f$ is one-to-one?

I tried finding contradicting example like considering the function $f(x)=x^2$ with $S = \{-2,-1,0,1,2\}$ and $T=\{0,1,2,3,4\}$ or using the function $f(x) = |x|$, but, it seems to be true. But, my book says that In general the aforementioned statement is true, and I need to prove it. However, I can't start to prove this.

$\endgroup$
2
$\begingroup$

Just to be clear, the statement that you're asking about is really this: given a function $f:X\to Y$, the following two statements are equivalent:

  1. $f$ is one-to-one
  2. For any two sets $S, T\subseteq X$, we have $f(S\cap T) = f(S)\cap f(T)$

Or, to be more specific, you are looking at their inverses:

  1. $f$ is not one-to-one
  2. There exists $S, T\subseteq X$ such that $f(S\cap T)\neq f(S)\cap f(T)$

Below is a proof of the equivalence of the latter pair:

Note that no matter the function, $f(S\cap T) \subseteq f(S)\cap f(T)$. If there are $S$ and $T$ such that $f(S ∩ T) \neq f(S) ∩ f(T)$, then we know that there is some $y\in f(S)\cap f(T)$ which is not contained in $f(S\cap T)$. In that case, $y\in f(S)\cap f(T)$ means that we have both $y\in f(S)$ and $y\in f(T)$, which in turn means that there is an $x_1\in S$ such that $f(x_1) = y$, and there is an $x_2\in T$ such that $f(x_2) = y$. However, netiher $x_1$ nor $x_2$ are contained in $S\cap T$, because $y\notin f(S, T)$. That means that $x_1$ and $x_2$ must be different, which makes them a witness against $f$ being one-to-one.

For the other direction, if $f$ is not one-to-one, then there are some $x_1 \neq x_2$ with $f(x_1) = f(x_2)$. Let $S = \{x_1\}$ and $T = \{x_2\}$, and you're done.

$\endgroup$
  • $\begingroup$ If x1 and x2 are different and they point to a single y, then , wouldn't that suggest an onto mapping?Which is not one to one $\endgroup$ – mathmaniage Sep 25 '17 at 15:20
  • 1
    $\begingroup$ There is nothing in our assumptions that allow us to even consider onto. Onto means that every possible $y$ is pointed to, and we don't know anything about that codomain. Also, onto and one-to-one are not mutually exclusive. $\endgroup$ – Arthur Sep 25 '17 at 15:34
1
$\begingroup$

Take any $y\in f(S \cap P)$, then exist $x \in S \cap P$ such that $y= f(x)$. So, since $x\in S$ we have $y\in f(S)$ and since $x \in P$ we have $y\in f(P)$ and thus $y\in f(S)\cap f(P)$. So $\boxed{f(S\cap P)\subseteq f(S)\cap f(P)}$. So here we don't need injective property.

Now suppose $f$ is injective.

Take any $y\in f(S)\cap f(P)$, then there are $s\in S$ and $p\in P$ such that $f(s)=y = f(p)$. Since $f$ is injective we have $s=p =:x$. Thus $x\in S\cap P$ so $y\in f(S\cap P)$ and thus $\boxed{f(S)\cap f(P)\subseteq f(S\cap P)}$.

So, if $f$ is injective we have $f(S)\cap f(P)= f(S\cap P)$. For reverse of this read Arthur answer.

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