1. PF Contest - Win "Conquering the Physics GRE" book! Click Here to Enter
    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!

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


    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


    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.


    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


    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


    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


    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


    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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook