12
$\begingroup$

Is this proof correct? To prove $F(A)\cap F(B)\subseteq F(A\cap B) $ for all functions $F$.

Let any number $y\in F(A)\cap F(B)$. We want to show $y\in F(A\cap B).$

Therefore, $y\in F(A)$ and $y\in F(B)$, by definition of intersection.

By definition of inverse, $y=F(x)$ for some $x\in A$ and $x\in B$

And so, $y=F(x)$ for some $x\in A\cap B$

And therefore, $y\in F(A\cap B)$

I have a gut feeling deep down that something is wrong. Can anyone help me pinpoint the mistake? I am not sure why am I having so much problems with functions. Am I not thinking in the right direction?

Sources : 2nd Ed, P219 9.60 = 3rd Ed, P235 9.12, 9.29 - Mathematical Proofs, by Gary Chartrand, P214 Theorem 12.4 - Book of Proof, by Richard Hammack,
P257-258 - How to Prove It, by D Velleman.

$\endgroup$
  • 1
    $\begingroup$ Remark: $F(A) \cap F(B) \subseteq F(A \cap B)$ holds for all $A,B$ iff $F$ is one-to-one (injective). $\endgroup$ – Martin Brandenburg Jan 13 '14 at 15:14
9
$\begingroup$

The third line is mistaken. You only know that there exists an $x$ in $A$ such that $F(x)=y$, and you know there is a $z\in B$ such that $F(z)=y$.

It is extremely easy to find a counterexample: just draw two sets $A$, $B$ that are disjoint, and map an $a\in A$ and a $b\in B$ to a single point. Then you have that $y\in F(A)\cap F(B)$, but $F(A\cap B)=\emptyset$.

$\endgroup$
  • $\begingroup$ @AustinMohr True, but I think in this case, since it really is extremely easy, the OP will need to have skin thick enough to not go crying into their beer about it. At any rate I applaud the OP's gut instinct! $\endgroup$ – rschwieb Oct 30 '12 at 17:06
  • $\begingroup$ If I sounded harsh, the compensation is that I +1 the question! Hope it helps... $\endgroup$ – rschwieb Oct 30 '12 at 17:07
  • $\begingroup$ Why the downvote? $\endgroup$ – rschwieb Jan 18 '18 at 17:41
12
$\begingroup$

Your gut is right. Something is indeed very wrong: the statement that you’re trying to prove is false. Here’s a familiar counterexample: let $F:\Bbb R\to\Bbb R:x\mapsto x^2$, let $A$ be the set of negative real numbers, and let $B$ be the set of positive real numbers. Then $F[A]=F[B]=B$, so $F[A]\cap F[B]=B$, but $A\cap B=\varnothing$, so $F[A\cap B]=\varnothing$. Clearly $B\nsubseteq\varnothing$!

The problem with your reasoning, as you can see from the counterexample, is that although $x\in F[A]$ guarantees that $x=F(a)$ for some $a\in A$, and $x\in F[B]$ guarantees that $x=F(b)$ for some $b\in B$, you have no guarantee that $a=b$. There may be nothing at all in $A\cap B$.

$\endgroup$
0
$\begingroup$

This is wrong. Consider $A=\{1,2\}$ and $B=\{3,4\}$ and we can define $F(1)=F(3)=1,a$ not equal $c$ and this $A\cap B= \emptyset$ while $F(A)\cap F(B)$ doesn't equal to $\emptyset$. This is a counter example to your statement

$\endgroup$
0
$\begingroup$

enter image description here

Here, $f: A \rightarrow B$ is in green and $\{S_i\} = S_i$ for $S = A, B$ and $i = 1, 2.$
This picture proves that $ f(A_1) \cap f(A_2) \not\subseteq f(A_1 \cap A_2)$. Incidentally, the same picture works for Proving $f(C) \setminus f(D) \subseteq f(C \setminus D)$ and disproving equality.

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