1

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.

Arthur
  • 199,419
mathmaniage
  • 596

2 Answers2

2

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.

Arthur
  • 199,419
  • 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 – mathmaniage Sep 25 '17 at 15:20
  • 1
    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. – Arthur Sep 25 '17 at 15:34
1

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.

nonuser
  • 90,026