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: Injective Compositition

  1. Apr 10, 2012 #1
    Given two functions:
    f:A --> B
    g:B --> C
    How to show that if the (g ° f) is injection, then f is injection?

    I tried this:

    We need to show that g(f(a)) = g(f(b)) ==> a = b holds true for all a, b in A. But there's nothing said about function g.
  2. jcsd
  3. Apr 10, 2012 #2
    I've tried using function mapping diagrams and actually it showed this proposition is wrong.
    (g ° f) injective ==> g and f are injective.
  4. Apr 10, 2012 #3
    No, you don't need to show that, that's given.

    You need to show that f is an injection. That is: f(a)=f(b) ==> a=b. That is what you need to show.
  5. Apr 10, 2012 #4
    You are absolutely right, my bad expressing the problem...

    And yeah my post should have been moved under elementary school math ;)

    But it's not a homework either, it's a question my professor did not have time to clarify well!
  6. Apr 10, 2012 #5
    Doesn't really matter. It's the style of homework, so it belongs here. It's irrelevant whether it is actually homework.

    So, got any ideas??

    You have f(a)=f(b) and you need to prove a=b.
    Convert it to g(f(a))=g(f(b)) in some way.
  7. Apr 10, 2012 #6
    But I think in order to show that f(a) = f(b) ==> a = b, g has to be given as injection as well, though I could prove that both functions g and f are injections using function mapping diagram.
  8. Apr 10, 2012 #7
    No, you don't need that g is an injection.
    And if gf is an injection, then it does NOT imply that g is an injection.
  9. Apr 10, 2012 #8
    Ok I could prove it by contradiction. Assuming f(x) is not injection, then

    Then there's the case where f(a) = f(b) and a != b for some a, b

    Then g(f(a)) = g(f(b)) where a != b, which contradicts the given argument.
  10. Apr 10, 2012 #9
    That is ok. But there is no need for a contradiction argument.

    If f(a)=f(b). Taking g of both sides, we get g(f(a))=g(f(b)). By hypothesis, this implies a=b.
  11. Apr 10, 2012 #10
    Got it! Any good reference that helps with doing proper proofs?

  12. Apr 10, 2012 #11
    The book "How to think like a mathematician" by Kevin Houston is a good book.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook