Injectivity and Set Intersection: Exploring the Validity of a Proposition

[daveyinaz]

Alright, I would like to pose a question on the validity of this argument, I seem to be caught on whether or not to believe it.

The proposition is, if, for any sets A and B, $f(A \cap B) = f(A) \cap f(B)$, then $f$ is injective.

Proposed proof:
Let's look at the contrapositive, that is if $f$ is not injective, then $f(A \cap B) \neq f(A) \cap f(B)$. Since we already know that $f(A \cap B) \subseteq f(A) \cap f(B)$ by some earlier exercise. Let us assume for the sake of contradiction that $f(A) \cap f(B) \subseteq f(A \cap B)$. Now consider, A = {1, 2, 3}, B = {1, 2} and f = {(1,1), (2,2), (3,3)}, so that $f(A) \cap f(B) = \{1,2,3\} \not\subseteq \{1,2\} = f(A \cap B)$. Hence $f(A \cap B)$ cannot possibly be equal to $f(A) \cap f(B)$

 

[ircdan]

no it doesn't work

why not prove it directly?

you have f injective, you need to show f(A) n f(B) = f(A n B). As you pointed out one direction is always true.

so take y in f(A) n f(B), so y is in f(A) and y is in f(B), so there is a in A and b in B s.t. f(a) = y and f(b) = y. Now use injectivity to finish.

 

[daveyinaz]

The question was not "How do I prove it?"

It was more explicitly...is there any reason to believe that this is a fallacious argument? If so, why is it?

 

[ircdan]

well the reason it's not a valid proof is that your sets A and B are arbitrary sets, this is assumed throughout the entire proof.

you say, assume for the sake of contradiction f(A) n f(B) <= f(A n B). Later, you go on to specify what A and B are, you cannot do this since they are arbitrary.

if that wasn't clear, remember since you are trying to prove that this holds for any sets, at the beginning of your proof you should say, let A and B be two arbitrary sets.

 

[daveyinaz]

Yes, we did assign values to A and B, but this was only after assuming that $f(A) \cap f(B) \subseteq f(A \cap B)$ was true. So it's says: assume it was true, then here is a counterexample.

So generally when someone makes a statement, if this, then that. We go on to show a counterexample of why it won't work, making the statement false. Well, since $f(A) \cap f(B) \subseteq f(A \cap B)$ is either true or false. We show it's false by counterexample, making the if f is not injective, then f(a) blah blah is not equal to that.

do you see what I'm saying?

Perhaps, if you use $p \Rightarrow q$ stuff to show what you mean.

 

[ircdan]

f(A) = {1 , 2, 3}, f(B) = {1, 2}, so there intersection is {1, 2} (not {1, 2, 3} as you have)

 

[daveyinaz]

I'm sorry I'm on crack, A = {1, 2, 3}, B = {1, 3, 4} and f = {(1,1), (2,3), (3,1), (4,4)}.

So the counterexample was messed up but that doesn't answer my question.

 

[ircdan]

I'm sorry I'm on crack, A = {1, 2, 3}, B = {1, 3, 4} and f = {(1,1), (2,3), (3,1), (4,4)}.

So the counterexample was messed up but that doesn't answer my question.

that function is not injective and your question is not clear

the function you just typed does show that the statement f(A n B) = f(A) n f(B) for all sets A, B, and any function f isn't necessarily true, and as you already know, it's true if f is injective

 

[daveyinaz]

Are you serious!??! Did you even read what I wrote?

If f is not injective! Obviously you need to move on to another thread where you can answer more appropriately.

 

[ircdan]

Are you serious!??! Did you even read what I wrote?

If f is not injective! Obviously you need to move on to another thread where you can answer more appropriately.

I get the feeling you are trying to start one of those long posts over something silly like (0/0 = 1?). Best of luck in your efforts.
And don't worry, I'm done here:)

 

[daveyinaz]

thanks.

For the sake of it. We can answer the above statement assuming A and B are any set,

if $f$ is not injective, then $f(A \cap B) \neq f(A) \cap f(B)$.

Proof: Suppose that $f$ is not injective, then that means that $\exists x_1, x_2$ such that $x_1 \neq x_2$ and $f(x_1) = f(x_2)$. Let $A = \{x_1\}$ and $B = \{x_2\}$ to show that $f(A) \cap f(B) \not\subseteq f(A \cap B)$.

The thing that gets me is that the last part is still a counterexample, using any element but still a counterexample nonetheless...just like the first thing I posted. So the only thing I might find wrong with this is that instead of using arbitrary elements like x_1 and x_2, we assigned them values. Of course, it's still in the same vein and which is the question I'm asking. How much different are these two "proofs"?