Results 1 to 5 of 5

Math Help - [SOLVED] proving g of f of x is injective/surjective

  1. #1
    Junior Member
    Joined
    Feb 2009
    Posts
    48

    [SOLVED] proving g of f of x is injective/surjective

    Let A, B and C be sets and if f: A-> B and g: B-> C be functions.

    a) Prove that if g ○ f is injective then f must be injective.

    b) Prove that if g ○ f is surjective then g must be surjective.


    For a) this is what I got..

    Suppose that (g ○ f)(x) = (g ○ f)(y) for some x,yεA. By definition of composition, g(f(x)) = g(f(y)). Since g is assumed injective, f(x)=f(y) is also assumed injective, x=y. Therefore (g ○ f)(x)=(g ○ f)(y) implies x=y so (g ○ f) is injective and thus so is f.

    Is that correct?
    I need a bit of a hint at least to start b)
    Last edited by Plato; August 11th 2009 at 02:32 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Feb 2009
    Posts
    48
    okay I know I got a) wrong. I got up to

    (g ○ f)(x) = g(f(x)) (by definition)
    = g(f(y)) (since f(x)=f(y) by assumption)
    =(g ○ f)(y)

    (g ○ f)(x)=(g ○ f)(y)

    and am a little stuck..any help?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2009
    Posts
    48
    Anyone?

    I think I completed the first part but I need to prove that if (g ○ f) is surjective then g must be surjective.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Failure's Avatar
    Joined
    Jul 2009
    From
    Zürich
    Posts
    555
    Quote Originally Posted by Kitizhi View Post
    Anyone?

    I think I completed the first part but I need to prove that if (g ○ f) is surjective then g must be surjective.
    In both cases, a) and b), you have to prove a statement of the form A\Rightarrow B. Instead of proving this directly, you can, instead, prove its contrapositive, which is \neg B\Rightarrow \neg A.

    So, in the case of a) you assume that f is not injective (i.e. that there exist two different elements x_1,x_2 in the domain of f such that f(x_1){\color{red}=}f(x_2)) and show that it follows that g\circ f is not injective either. Which should be obvious, because

    (g\circ f)(x_1)=g(f(x_1)){\color{red}=}g(f(x_2))=(g\circ f)(x_2)

    Similarly, in the case of b) you assume that g is not surjective (i.e. that there exists an element y of the codomain of g which is not part of the range of g) and then show that this (same) element y cannot be part of the range of g\circ f either, which is to say that g\circ f is not surjective. This, too, should be obvious, because the range of g\circ f is a subset of the range of g.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,661
    Thanks
    1616
    Awards
    1
    Quote Originally Posted by Kitizhi View Post
    Let A, B and C be sets and if f: A-> B and g: B-> C be functions.
    a) Prove that if g ○ f is injective then f must be injective.
    b) Prove that if g ○ f is surjective then g must be surjective.
    Here are two direct proofs.
    a) Suppose that f\left( {a_1 } \right) = f\left( {a_2 } \right) then definition g \circ f\left( {a_1 } \right) = g \circ f\left( {a_2 } \right).
    We know that g \circ f is injective, so a_1=a_2. That shows that f is injective.

    b) Suppose that y\in C. g \circ f is surjective, so \left( {\exists a \in A} \right)\left[ {g \circ f\left( a \right) = y} \right]. But f(a)\in B so g is surjective.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. When will be this surjective or injective?
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: November 27th 2011, 10:20 AM
  2. [SOLVED] Injective and Surjective
    Posted in the Calculus Forum
    Replies: 11
    Last Post: September 29th 2010, 02:16 PM
  3. injective and surjective
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: February 12th 2010, 10:18 AM
  4. Injective/Surjective.
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: October 31st 2009, 07:14 AM
  5. Injective/Surjective
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 10th 2008, 08:19 AM

Search Tags


/mathhelpforum @mathhelpforum