5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I don't think you need to deal with the case $A\cap B=\emptyset$ separately in the first part. $\endgroup$ – Thomas Andrews Feb 7 '15 at 21:41
  • 2
    $\begingroup$ One thing of which you should be aware: $f(A\cap B)\subseteq f(A)\cap f(B)$ for any $f$. $\endgroup$ – Tim Raczkowski Feb 7 '15 at 21:45
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

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