$f(A\cap B)=f(A)\cap f(B)$ $\iff$ $f$ is injective.

Let $f:X\to Y$ where $X$ and $Y$ are nonempty. Prove that a sufficient and essential condition for any two subsets $A,B\subseteq X$ to fulfill $f(A\cap B)=f(A)\cap f(B)$ is that $f$ is injective. I sense there is some problem in my proof. I would be glad if you assisted me.

$Attempt:$ Let $f$ be injective and let $A,B\subseteq X$ be two subsets. If $A$ and $B$ are disjoint, then $A\cap B=\emptyset$ $\Rightarrow$ $f(A\cap B)=\emptyset$. Since $f$ is injective then there are no two elements with the same image and therefore $f(A)\cap f(B) =\emptyset =f(A\cap B)$. Now suppose $A\cap B\ne \emptyset.$ Let $ y\in f(A\cap B)$. There exists an $x\in A\cap B$ such that $f(x)=y$. Since $x \in A$ then $f(x)=y\in f(A)$ and since $x \in B$ then $f(x)=y\in f(B)$ $\Rightarrow$ $y\in f(A)\cap f(B)$. Therefore $f(A\cap B)\subseteq f(A)\cap f(B)$.

Now let $y\in f(A)\cap f(B)$. ( $f(A)\cap f(B)$ is not empty because if it were then $A$ and $B$ would have an empty intersection as well, which they don't.). Therefore $y\in f(A)$ and $y\in f(B)$ and therefore in $A$ there exists $x_1$ such that $f(x_1)=y$. The same with $B$, $f(x_2)=y$. By injectivity: $x_1=x_2 \Rightarrow x_1=x_2\in A\cap B\Rightarrow f(x_1)=y\in f(a\cap B)\Rightarrow f(A)\cap f(B)\subseteq f(A\cap B) \Rightarrow f(A\cap B)=f(A)\cap f(B).$

Necessary: Suppose it weren't necessary that $f$ is injective. Then there would exist a non-injective function $f$ such that for any two subsets $A,B\subseteq X$ we get $f(A\cap B)=f(A)\cap f(B)$. $f$ is non-injective and therefore there would be $x_1,x_2\in X$ such that $f(x_1)=f(x_2)$. Let us look at $\{x_1\},\{x_2\}\subseteq X$. $f(\{x_1\})\cap f(\{x_2\})=\{f(x_1)=f(x_2)\}\ne f(\{x_1\}\cap\{x_2\})=f(\emptyset)=\emptyset$. A contradiction.

Solution 1:

The proof that the condition (*) implies that $f$ is injective is fine. Here

(*) For all $A, B \subseteq X$ we have that $f[A] \cap f[B] = f[A \cap B]$

Suppose now that $f$ is injective. We need to show (*).

For any function, $A \cap B \subseteq A$, so $f[A \cap B] \subseteq f[A]$, and also, $A \cap B \subseteq B$ so $f[A \cap B] \subseteq f[B]$. Combining these gives $f[A \cap B] \subseteq f[A] \cap f[B]$. Alternatively, note that if $y \in f[A \cap B]$, then $y = f(x)$ for some $x \in A \cap B$ and this same $x$ witnesses that $y \in f[A]$ and also $y \in f[B]$. So $y$ is in their intersection. Nothing of $f$ is needed for that inclusion.

Now take $y \in f[A] \cap f[B]$. Then $y \in f[A]$ so there is some $a \in A$ with $f(a) = y$. Also, $y \in f[B]$, so there is some $b \in B$ such that $y = f(b)$. Now $f(a) = y = f(b)$, so $f$ being injective now implies $a = b$. So $a \in A \cap B$ and so $y \in f[A \cap B]$, which settles the other inequality.

No need to handle disjointness as a special case.

Solution 2:

Your proof looks okay, but most of the first paragraph is entirely unnecessary. The first paragraph sets out to prove the statement: $$f(A\cap B)\subseteq f(A)\cap f(B).$$ Why bother looking at the case when $A$ and $B$ are disjoint? In that case, the left hand side is the empty set and is trivially a subset of anything. It makes more sense just to write:

For any $y\in f(A\cap B)$, there is some $x\in A\cap B$ such that $f(x)=y$. Since $x$ is in both $A$ and $B$ hence $y\in f(A)\cap f(B)$.

The second bit of your proof is phrased as a proof by contradiction, when it's really a direct proof, which you derived the desired result and used it for contradiction - it's sort of like saying "We can prove $P$. Assume not $P$. Then, we have $P$ and not $P$ - a contradiction. Thus we reject that not $P$ is true, implying $P$" instead of just proving $P$. You could rephrase your basic idea as:

If $f(\{x_1\}\cap \{x_2\})=f(\{x_1\})\cap f(\{x_2\})$ for all $x_1,x_2\in X$, then if $f(x_1)=f(x_2)$ it follows that $f(\{x_1\})\cap f(\{x_2\}=f(\{x_1\}\cap\{x_2\})$ is non-empty, thus $\{x_1\}\cap\{x_2\}$ is non-empty and $x_1=x_2$.

Solution 3:

Your proof is fine.

You don't need to separate the case $A\cap B=\emptyset$ in the first part - just prove that $f(A\cap B)\subseteq f(A)\cap f(B)$ and $f(A)\cap f(B)\subseteq f(A\cap B)$ in general.

The first part is obvious - it is true for any $f$, not just injective $f$.

So you merely need to prove that $f(A)\cap f(B)\subseteq f(A\cap B)$.

If $x\in f(A)\cap f(B)$, then $x=f(a)$ and $x=f(b)$ for some $a\in A$ and $b\in B$. But then, by the assumption of injectivity, $a=b$, so $a\in A\cap B$ and $x\in f(A\cap B)$.