Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Injectivity with functions

  1. Apr 25, 2008 #1
    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, [itex]f(A \cap B) = f(A) \cap f(B)[/itex], then [itex]f[/itex] is injective.

    Proposed proof:
    Let's look at the contrapositive, that is if [itex]f[/itex] is not injective, then [itex]f(A \cap B) \neq f(A) \cap f(B)[/itex]. Since we already know that [itex]f(A \cap B) \subseteq f(A) \cap f(B)[/itex] by some earlier exercise. Let us assume for the sake of contradiction that [itex]f(A) \cap f(B) \subseteq f(A \cap B)[/itex]. Now consider, A = {1, 2, 3}, B = {1, 2} and f = {(1,1), (2,2), (3,3)}, so that [itex]f(A) \cap f(B) = \{1,2,3\} \not\subseteq \{1,2\} = f(A \cap B)[/itex]. Hence [itex]f(A \cap B)[/itex] cannot possibly be equal to [itex]f(A) \cap f(B)[/itex]
  2. jcsd
  3. Apr 25, 2008 #2
    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.
  4. Apr 25, 2008 #3
    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?
    Last edited: Apr 25, 2008
  5. Apr 25, 2008 #4
    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.
    Last edited: Apr 25, 2008
  6. Apr 25, 2008 #5
    Yes, we did assign values to A and B, but this was only after assuming that [itex]f(A) \cap f(B) \subseteq f(A \cap B)[/itex] 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 [itex]f(A) \cap f(B) \subseteq f(A \cap B)[/itex] 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 [itex]p \Rightarrow q[/itex] stuff to show what you mean.
  7. Apr 25, 2008 #6
    f(A) = {1 , 2, 3}, f(B) = {1, 2}, so there intersection is {1, 2} (not {1, 2, 3} as you have)
  8. Apr 25, 2008 #7
    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.
  9. Apr 25, 2008 #8
    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
    Last edited: Apr 25, 2008
  10. Apr 25, 2008 #9
    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.
  11. Apr 25, 2008 #10
    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:)
    Last edited: Apr 25, 2008
  12. Apr 25, 2008 #11

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

    if [itex]f[/itex] is not injective, then [itex]f(A \cap B) \neq f(A) \cap f(B)[/itex].

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

    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"?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook