1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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
    Staff Emeritus
    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]
    [​IMG]
    Still, can't understand.
     
  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
    Staff Emeritus
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Proving injection,surjection,bijection
  1. Proof of Bijection (Replies: 3)

Loading...