Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Remark: $F(A) \cap F(B) \subseteq F(A \cap B)$ holds for all $A,B$ iff $F$ is one-to-one (injective). –  Martin Brandenburg Jan 13 at 15:14
add comment

4 Answers 4

up vote 5 down vote accepted

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

share|improve this answer
    
@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! –  rschwieb Oct 30 '12 at 17:06
    
If I sounded harsh, the compensation is that I +1 the question! Hope it helps... –  rschwieb Oct 30 '12 at 17:07
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.