Results 1 to 5 of 5

Thread: Surjection

  1. #1
    Member
    Joined
    Aug 2007
    Posts
    239

    Surjection

    Let $\displaystyle f: X \to Y $ be a function. Prove that there exists a function $\displaystyle g: Y \to X $ such that $\displaystyle f \circ g = I_Y $ if and only if $\displaystyle f $ is a surjection.

    So we first construct $\displaystyle g $(using axiom of choice) by picking a point in the preimage of $\displaystyle y $ for all $\displaystyle y $( $\displaystyle \overleftarrow{f}(Y) $). If $\displaystyle f(g(y)) = f(x) = y, \ \forall x \in X $ then $\displaystyle f $ is a surjection. If $\displaystyle f $ is a surjection, then $\displaystyle \forall y \in Y, \exists x \in X, y = f(x) $. Then $\displaystyle f(g(y)) = f(x) = y $ as required.

    Is this correct?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,796
    Thanks
    2827
    Awards
    1
    Quote Originally Posted by shilz222 View Post
    Let $\displaystyle f: X \to Y $ be a function. Prove that there exists a function $\displaystyle g: Y \to X $ such that $\displaystyle f \circ g = I_Y $ if and only if $\displaystyle f $ is a surjection.
    So we first construct $\displaystyle g $(using axiom of choice) by picking a point in the preimage of $\displaystyle y $ for all $\displaystyle y $( $\displaystyle \overleftarrow{f}(Y) $). If $\displaystyle f(g(y)) = f(x) = y, \ \forall x \in X $ then $\displaystyle f $ is a surjection. If $\displaystyle f $ is a surjection, then $\displaystyle \forall y \in Y, \exists x \in X, y = f(x) $. Then $\displaystyle f(g(y)) = f(x) = y $ as required.
    Is this correct?
    No it is most definitely not correct. You have confused the two-way proof.

    First assume that $\displaystyle g: Y \to X $ such that $\displaystyle f \circ g = I_Y $.
    In which case there is no need to construct g because you already have it assumed.
    Now just go about proving f is surjective.

    That part done, then assume that f is surjective and go about constructing g such that $\displaystyle f \circ g = I_Y $.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Aug 2007
    Posts
    239
    didnt I do that? Plus it says prove that there exists a function $\displaystyle g: Y \to X $. THat is separate from the other part of the proof.

    So the two parts are: Prove existence of function $\displaystyle g: Y \to X $, and the two-way proof.

    So I proved: (1)$\displaystyle f \circ g = I_y \Leftrightarrow f $ is surjective and (2) that such a function $\displaystyle g: Y \to X $ exists.

    So how come the question didn't given both functions $\displaystyle f: X \to Y $ and $\displaystyle g: Y \to X $?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,796
    Thanks
    2827
    Awards
    1
    Do you have difficulty understanding the problem? Here is what this problem says.
    GIVEN $\displaystyle f: X \to Y $ be a function.
    Now we are working in a universe of discourse where $\displaystyle f: X \to Y $ is a fixed function.

    Now for the problem:
    PROBLEM Prove that there exists a function $\displaystyle g: Y \to X $ such that $\displaystyle f \circ g = I_Y $ if and only if $\displaystyle f $ is a surjection.

    1) Show that $\displaystyle g: Y \to X $ such that $\displaystyle f \circ g = I_Y $ implies that $\displaystyle f $ is a surjection.
    Here the function g implicitly given from which you are proving something about the function f.

    2) Show that $\displaystyle f $ is a surjection implies that there exists a function $\displaystyle g: Y \to X $ such that $\displaystyle f \circ g = I_Y $.
    In this part, from an assumed property of f you are constructing a function g having a required property.

    Now if you think you have done that, then you mistaken.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,796
    Thanks
    2827
    Awards
    1
    Quote Originally Posted by shilz222 View Post
    Actually the $\displaystyle \Leftarrow $ direction is as follows: Given $\displaystyle f $ is a surjection prove that there exists a function $\displaystyle g $ such that $\displaystyle f \circ g = I_Y $. It is here where we construct the function $\displaystyle g $.
    Well, you have finally seen the light.
    But of course, I said that in my very first reply.

    The point of $\displaystyle f$ being a surjection means that the collection $\displaystyle \left\{ {\overleftarrow f (y)} \right\}_{y \in Y} $ forms a partition of $\displaystyle X$.
    Now one does have to use the axiom of choice on that collection in order to construct $\displaystyle g$.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Injection and Surjection
    Posted in the Advanced Algebra Forum
    Replies: 15
    Last Post: Jan 7th 2010, 06:44 AM
  2. Surjection
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: Nov 6th 2009, 08:29 AM
  3. surjection proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Sep 9th 2009, 07:58 AM
  4. surjection
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: Jul 23rd 2009, 05:52 AM
  5. Surjection
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Aug 21st 2008, 03:16 AM

Search Tags


/mathhelpforum @mathhelpforum