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

Homework Help: Proving injection,surjection,bijection

  1. Feb 27, 2008 #1
    1. The problem statement, all variables and given/known data

    Prove that one copying [tex]f:A \rightarrow B[/tex] is injection, only if [tex]x_1,x_2 \in A[/tex] and [tex]x_1 \neq x_2 \Rightarrow f(x_1) \neq f(x_2)[/tex]

    2. Relevant equations



    3. The attempt at a solution

    I have not idea at all. Can somebody, please help?
     
  2. jcsd
  3. Feb 27, 2008 #2

    EnumaElish

    User Avatar
    Science Advisor
    Homework Helper

    What is the definition of an injection that you are working with/have been taught?
     
  4. Feb 27, 2008 #3

    Tom Mattson

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I bet the definition he was taught was the contrapositive of this one. Namely, that a map [itex]f:A\rightarrow B[/itex] is an injection if for all [itex]x_1,x_2\in A[/itex], [itex]f(x_1)=f(x_2)[/itex] implies [itex]x_1=x_2[/itex].

    Physicsissuef, is that the definition in your book?
     
  5. Feb 27, 2008 #4
    Yes sir, sorry for missing the formula.
     
  6. Feb 27, 2008 #5

    Tom Mattson

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    In that case, your proof need only be one line long. For any conditional statement [itex]p \Rightarrow q[/itex] (that is: if p, then q), a logically equivalent statement is [itex]\neg q \Rightarrow \neg p[/itex] (that is: if not p, then not q). This latter statement is called the contrapositive of the first, and it can be immediately inferred from it.
     
  7. Feb 27, 2008 #6
    And what about this one?
    Prove that one copying [tex]f:A \rightarrow B[/tex] is surjection, only if [tex]f(A)=B[/tex]
     
  8. Feb 27, 2008 #7

    Tom Mattson

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Are you going to make me guess the definition again?
     
  9. Feb 27, 2008 #8
    surjection is, if every element [tex]y \in B[/tex] is image of at least one element [tex]a \in A[/tex]
     
  10. Feb 27, 2008 #9

    HallsofIvy

    User Avatar
    Science Advisor

    Okay, you prove one set is equal to another by showing that each is a subset of the other. And you prove subset by saying "if x is in" the first set and then showing that x must be in the second.

    It should be trivial to show that f(A) is a subset of B. (What does [itex]f: A\rightarrow B[/itex] mean?)
    To prove that B is a subset of A, start with "if [tex]y \in B[/tex]" and show that y is in f(A). Of course, you will also need to use the definition of "f(A)".

    Do you see a basic theme in all of this? Learn the exact words of the definitions. You can use the exact statement of definitions in proofs.
     
  11. Feb 28, 2008 #10
    Ok, but I think I still can't understand the definition of injection. What does [tex]f(x_1)=f(x_2), x_1=x_2[/tex], mean?
    If I draw a domain and codomain, lets say [tex]f(x_1)=f(x_2)=1, x_1=x_2[/tex]
    http://pic.mkd.net/images/638823221.JPG [Broken]
    Still, can't understand.
     
    Last edited by a moderator: May 3, 2017
  12. Feb 28, 2008 #11
    Here's an example of something that's not an injection:

    Let f(x) = x2. If f(y) = f(z) = 4, does y = z ? Not necessarily, because you could have y = 2 and z = -2. This is not an injection.

    If, for example, f(x) = 2x, then f(y) = f(z) would imply that y = z. e.g. f(y) = f(z) = 4 => y = z = 2. This is an injection.

    Hope that helped you understand the concept a little better. :smile:
     
  13. Feb 28, 2008 #12
    Ok, thanks. But can you draw it with domains and co domains, like my picture, please?
     
  14. Feb 29, 2008 #13
    Can you give me the whole prove, please?
     
  15. Feb 29, 2008 #14

    HallsofIvy

    User Avatar
    Science Advisor

    No, we don't want to prevent you form learning- you learn by doing, not by watching someone else do it for you .

    I will do this: suppose f:R->R is defined by f(x)= 3x- 4. To prove that f is injective ("one-to-one") we need to prove "if f(x1)= f(x2) then x1= x2. Okay, for this particular f, f(x1)= 3x1- 4 and f(x2)= 3x2- 4 so f(x1)= f(x2) means 3x1- 4= 3x2- 4. Adding 4 to both sides of the equation gives 3x1= 3x2 and then dividing both sides by 3, x1= x2, exactly what we needed to prove. To prove f is surjective ("onto"), let y be any real number. We need to prove that there must exist x such that f(x)= y. f(x)= 3x- 4= y so, again adding 4 to both sides, 3x= y+ 4 and then dividing by 3, x= (y+4)/3. For any real number y, that is still a real number. Since every number in R is f(x) for some x, f is surjective.

    Now, can you tell me why g: R-> R, defined by g(x)= x2, can you tell me g is not injective and is not surjective?

    Can you tell me why h:R to the non-negative real numbers, defined by h(x)= x2, is not injective but is surjective?

    What about j(x)= x2, from non-negative real numbers to all real numbers?

    What about k(x)= x2, from non-negative real numbers to non-negative real numbers?
     
  16. Mar 1, 2008 #15


    Ok, can you explain me first, why the definition is [itex]f(x_1)=f(x_2)[/itex] , [itex]x_1=x_2[/itex]? What it means?
     
  17. Mar 1, 2008 #16

    cristo

    User Avatar
    Staff Emeritus
    Science Advisor

    It's just the definition. In words, it means that an injective function is one that maps a distinct element in the domain to a distinct element in the codomain.
     
  18. Mar 1, 2008 #17
    But why [itex]x_1=x_2[/itex]?
     
  19. Mar 1, 2008 #18

    cristo

    User Avatar
    Staff Emeritus
    Science Advisor

    That's the "distinct element in the domain" part.
     
  20. Mar 1, 2008 #19
    Lets say if [itex]f(x_1)=f(x_2)[/itex], [itex]f(x_1)=y[/itex] if y=3, then [itex]f(x_2)=3[/itex]
    if [itex]x_2=5[/itex], so [itex]f(5)=3[/itex], then [itex]x_1=6[/itex] and [itex]f(6)=3[/itex], it doesn't necessarily [itex]x_1=x_2[/itex]
     
  21. Mar 1, 2008 #20

    cristo

    User Avatar
    Staff Emeritus
    Science Advisor

    Sorry, but what function are you using? I don't see you define f anywhere.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook