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: Surjective Proof

  1. Sep 6, 2008 #1

    nicksauce

    User Avatar
    Science Advisor
    Homework Helper

    1. The problem statement, all variables and given/known data
    Let [itex]f:X\rightarrow~Y[/itex] and [itex]g:Y\rightarrow~Z[/itex] be surjections. Show that [itex]g\circ~f[/itex] is surjective.


    2. Relevant equations



    3. The attempt at a solution
    Proof:
    Suppose f and g are surjections.
    Then (1)[itex]\forall~y\in~Y \exists~x\in~X\textnormal{ st. }f(x)=y[/itex]
    And (2) [itex]\forall~z\in~Z \exists~y\in~Y\textnormal{ st. }g(y)=z[/itex]

    (1) guarantees that we can write any y as f(x) for some x, so placing this into (2) gives:
    (3)[itex]\forall~z\in~Z \exists~x\in~X\textnormal{ st. }g(f(x))=g\circ~f=z[/itex]

    And (3) shows that [itex]g\circ~f[/itex] is surjective.

    Is my logic correct?
     
  2. jcsd
  3. Sep 6, 2008 #2

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Hi nicksauce! :smile:

    (have an exists: ∃ and an in/episilon: ε :smile:)

    Your logic is fine …

    but it would be quicker and neater to start with (2) …

    given z ε Z, ∃ y ε Y st g(y) = z, so ∃ x ε X st … :wink:
     
  4. Sep 6, 2008 #3

    HallsofIvy

    User Avatar
    Science Advisor

    The proof is correct but, rather than saying "for all", better wording would be "if z is in Z, then, because g is surjective, there exist y in Y such that g(y)= z. Now, since f is surjective, there exist x in X such that f(x)= y (that specific y you got before). Then [itex]g\circ f(x)= g(f(x))= g(y)= z[/itex]. That is, you have proved "if z is in Z, then there exist x in X such that [itex]g\circ f(x)= z[/itex].
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook