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: Composite of two injections is an injection

  1. Jul 19, 2010 #1
    1. The problem statement, all variables and given/known data

    That's what I'm supposed to prove.


    2. Relevant equations

    A function f is an injection if

    f(x1)=f(x2) ---> x1=x2

    3. The attempt at a solution

    I'm just having trouble constructing a formal proof. I mean, it's obvious that f(g(x1))=f(g(x2)) then either g(x1)=g(x2) or g(x1)≠g(x2), and since g(x1)≠g(x2) implies x1≠x2, ......

    I don't know. I'm getting all tongue-tied. Help me out here.
     
  2. jcsd
  3. Jul 19, 2010 #2

    hunt_mat

    User Avatar
    Homework Helper

    f and g are injective then is [tex]g\circ f[/tex]?, write down wheat it means for f to be injective (f(a)=f(b)=>a=b), what it means for g and what it means for [tex]g\circ f[/tex] and you should have your proof, it's a one liner.
     
  4. Jul 19, 2010 #3

    Mark44

    Staff: Mentor

    Since f is an injection, you won't have the latter case. Since f(g(x1))=f(g(x2)) then g(x1)=g(x2), because f is an injection.
     
  5. Jul 20, 2010 #4
    Nevermind. I was thinking to hard about this.

    Proof.

    Let h=f(g(x)), where f and g are injective functions.

    h(x1)=h(x2) [tex]\Rightarrow[/tex] f(g(x1))=f(g(x2)) [tex]\Rightarrow[/tex] g(x1)=g(x2) (since f is an injection) [tex]\Rightarrow[/tex] x1=x2 (since g is an injection)
     
  6. Jul 20, 2010 #5
    But the next question asks me to show that the composite of two surjections is a surjection. I'll give it a shot.

    Proof. Let f:A[tex]\rightarrow[/tex]B and g:C[tex]\rightarrow[/tex]D be surjections.

    ( [tex]\forall[/tex] b[tex]\in[/tex]B ) ( [tex]\exists[/tex] a[tex]\in[/tex]A ) ( f(a)=b )

    ( [tex]\forall[/tex] d[tex]\in[/tex]D ) ( [tex]\exists[/tex] c[tex]\in[/tex]C ) ( f(c)=d )

    Let h=f(g(x)).

    ....

    Not sure where to go from here. Can someone give me a jump start?
     
  7. Jul 20, 2010 #6

    hunt_mat

    User Avatar
    Homework Helper

    Same as before with the injection, f:A->B and g:C->A. f is surjective then for all g(c) in A there is an b in B such that f(g(c))=b. What does it mean for g to be surjective?

    You have to define your maps correctly.
     
  8. Jul 20, 2010 #7
    So why is the domain of f the same as the codomain of g?
     
  9. Jul 20, 2010 #8

    hunt_mat

    User Avatar
    Homework Helper

    because you're looking at f(g(x)), g has to map to something that f can map from. I prefer the term image to codomain, you may hear that from time to time.
     
    Last edited: Jul 20, 2010
  10. Jul 20, 2010 #9
    Why couldn't I just say ...

    Let f:A-->B and g:C-->D be surjections. For all b in B, there exists an a in A such that f(a)=b, and for all d in D, there exists a c in C such that f(c)=d. The composite function h(x)=f(g(x)) will map the set C to the set A. h will be a surjection if for all a in A, there exists a c in C such that f(c)=a.

    .... I don't know. Still don't get it. :confused:
     
  11. Jul 20, 2010 #10

    hunt_mat

    User Avatar
    Homework Helper

    No, sorry. You have to think about the two functions f & g. You can define g:A->B, so take an a in A, g will map this from A into B with a value g(a). Now as we're considering the composition f(g(a)). The value g(a) must lie in the domain of f for the composition to make sense, otherwise the composition f(g(a)) wouldn't make sense. Are you with me so far?

    f will have to be a map f:B->C, so that the composition [tex]f\circ g:A\rightarrow C[/tex] makes sense. I think your confused about the composition of functions.
     
  12. Jul 21, 2010 #11
    I'm with you.
     
  13. Jul 21, 2010 #12

    hunt_mat

    User Avatar
    Homework Helper

    So I think now you're able to complete the question using the same sort of logic as you did with the injective part.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook