Results 1 to 10 of 10

Math Help - Is this an equivalent definition for injection?

  1. #1
    Junior Member
    Joined
    Jul 2010
    From
    NJ
    Posts
    68

    Is this an equivalent definition for injection?

    I recently had problem set which asked to prove that if for any A, B \subset X, we have
    f(A \cap B) = f(A) \cap f(B) then f is an injection. (EDITED**)

    My proof started with the intention to show that if (pointwise) f(A) = f(B), then A = B. And I did that, but when I got it returned, apparently I didn't use the definition of an injection since injectivity implies that for all x1, x2 \in X, f(x1) = f(x2) implies x1 = x2.

    However, I feel that my proof was valid since A and B can have very well been singleton sets with x1 and x2, respectively. Is my approach incorrect?
    Last edited by elemental; October 1st 2012 at 12:18 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,546
    Thanks
    781

    Re: Is this an equivalent definition for injection?

    Quote Originally Posted by elemental View Post
    I recently had problem set which asked to prove that if for any A, B \subset X, then we have
    f(A \cap B) = f(A) \cap f(B).
    This is not a grammatically correct sentence. What is it that you were asked to prove?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jul 2010
    From
    NJ
    Posts
    68

    Re: Is this an equivalent definition for injection?

    I had to prove the following statement:

    Let f : X -> Y be a function with domain X and codomain Y
    Prove that if for any A, B \subset X we have f(A \cap B) = f(A) \cap f(B) then f is an injection.

    Sorry, I did not clarify the injection clause before.
    Last edited by elemental; October 1st 2012 at 12:14 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,803
    Thanks
    1692
    Awards
    1

    Re: Is this an equivalent definition for injection?

    Quote Originally Posted by elemental View Post
    I recently had problem set which asked to prove that if for any A, B \subset X, then we have
    f(A \cap B) = f(A) \cap f(B).
    You cannot prove that.
    You can prove that f(A \cap B) \subseteq f(A) \cap f(B)
    If t\in f(A\cap B) then \exists k\in A\cap B~\&~f(k)=t.
    That means [k\in A~\&~f(k)=t]~\&~[k\in B~\&~f(k)=t]
    So t\in f(A)\cap f(B).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jul 2010
    From
    NJ
    Posts
    68

    Re: Is this an equivalent definition for injection?

    Thanks Plato, but I had incorrectly typed the question before. If you'd like to, please check my correction in my last post!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,803
    Thanks
    1692
    Awards
    1

    Re: Is this an equivalent definition for injection?

    Quote Originally Posted by elemental View Post
    Thanks Plato, but I had incorrectly typed the question before. If you'd like to, please check my correction in my last post!
    Now if s\in f(A)\cap f(b) then s\in f(A)~\&~s\in f(B).
    Take then one at a time:
    (\exists j\in A)[f(j)=s]~\&~(\exists h\in B)[f(j)=s].
    but f\text{ is injective so }f(j)=f(h) \Rightarrow  h=j

    Thus s\in f(A\cap B)
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,546
    Thanks
    781

    Re: Is this an equivalent definition for injection?

    Quote Originally Posted by Plato View Post
    Now if s\in f(A)\cap f(b) then s\in f(A)~\&~s\in f(B).
    Take then one at a time:
    (\exists j\in A)[f(j)=s]~\&~(\exists h\in B)[f(j)=s].
    but f\text{ is injective so }f(j)=f(h) \Rightarrow  h=j

    Thus s\in f(A\cap B)
    The OP has to prove the converse statement: if f(A \cap B) \supseteq f(A) \cap f(B) for all A and B, then f is injective.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,803
    Thanks
    1692
    Awards
    1

    Re: Is this an equivalent definition for injection?

    Quote Originally Posted by emakarov View Post
    The OP has to prove the converse statement: if f(A \cap B) \supseteq f(A) \cap f(B) for all A and B, then f is injective.
    In that case suppose x\ne y~\&~f(x)=f(y) then let A=\{x\}~\&~B=\{y\} what happens?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,546
    Thanks
    781

    Re: Is this an equivalent definition for injection?

    Quote Originally Posted by elemental View Post
    I recently had problem set which asked to prove that if for any A, B \subset X, we have
    f(A \cap B) = f(A) \cap f(B) then f is an injection. (EDITED**)

    My proof started with the intention to show that if (pointwise) f(A) = f(B), then A = B. And I did that, but when I got it returned, apparently I didn't use the definition of an injection since injectivity implies that for all x1, x2 \in X, f(x1) = f(x2) implies x1 = x2.

    However, I feel that my proof was valid since A and B can have very well been singleton sets with x1 and x2, respectively. Is my approach incorrect?
    I agree that if

    f(A) = f(B) implies A = B for all A, B (*),

    then

    f(x1) = f(x2) implies x1 = x2 for all x1, x2 (**).

    As you said, (*) implies (**) by taking A = {x1} and B = {x2}. Therefore, if you proved (*), you basically solved the problem. However, while the step from (*) to (**) can be considered negligible and omitted when talking about some complicated theorem whose proof takes many pages, it is not negligible in the problem designed to test your understanding of injective functions. Since the problem is relatively simple, the proof also has to be spelled out in great detail. So I can understand the issue your instructor had with your proof, which does not even use the definition of injection.

    As Plato says, it is easier to prove (**) by considering singleton A and B from the start.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Junior Member
    Joined
    Jul 2010
    From
    NJ
    Posts
    68

    Re: Is this an equivalent definition for injection?

    Ah, I see what you mean and will keep it in mind for the future. Thanks a lot!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Injection/Surjection
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 17th 2010, 10:13 PM
  2. Injection and Surjection
    Posted in the Advanced Algebra Forum
    Replies: 15
    Last Post: January 7th 2010, 06:44 AM
  3. Injection or not?
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: December 29th 2009, 02:12 PM
  4. injection
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 27th 2009, 04:55 AM
  5. injection & surjection proofs
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 15th 2009, 05:01 AM

Search Tags


/mathhelpforum @mathhelpforum