Results 1 to 5 of 5

Thread: [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; Aug 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 $\displaystyle A\Rightarrow B$. Instead of proving this directly, you can, instead, prove its contrapositive, which is $\displaystyle \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 $\displaystyle x_1,x_2$ in the domain of f such that $\displaystyle f(x_1){\color{red}=}f(x_2)$) and show that it follows that $\displaystyle g\circ f$ is not injective either. Which should be obvious, because

    $\displaystyle (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 $\displaystyle g\circ f$ either, which is to say that $\displaystyle g\circ f$ is not surjective. This, too, should be obvious, because the range of $\displaystyle g\circ f$ is a subset of the range of $\displaystyle g$.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,782
    Thanks
    2824
    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 $\displaystyle f\left( {a_1 } \right) = f\left( {a_2 } \right)$ then definition $\displaystyle g \circ f\left( {a_1 } \right) = g \circ f\left( {a_2 } \right)$.
    We know that $\displaystyle g \circ f$ is injective, so $\displaystyle a_1=a_2$. That shows that $\displaystyle f$ is injective.

    b) Suppose that $\displaystyle y\in C$. $\displaystyle g \circ f$ is surjective, so $\displaystyle \left( {\exists a \in A} \right)\left[ {g \circ f\left( a \right) = y} \right]$. But $\displaystyle f(a)\in B$ so $\displaystyle 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: Nov 27th 2011, 10:20 AM
  2. [SOLVED] Injective and Surjective
    Posted in the Calculus Forum
    Replies: 11
    Last Post: Sep 29th 2010, 02:16 PM
  3. injective and surjective
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: Feb 12th 2010, 10:18 AM
  4. Injective/Surjective.
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Oct 31st 2009, 07:14 AM
  5. Injective/Surjective
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Sep 10th 2008, 08:19 AM

Search tags for this page

Click on a term to search for related topics.

Search Tags


/mathhelpforum @mathhelpforum