1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove that g composed of f is a bijection.

  1. May 26, 2012 #1
    1. The problem statement, all variables and given/known data
    If f:A->B is a bijection and g:B->C is a bijection, show that g[itex]\circ[/itex]f is a bijection from A->C.


    2. Relevant equations
    A function is a bijection from A to B when it is both a surjection and an injection from A to B.


    3. The attempt at a solution
    Suppose f is a bijection from A to B and g is a bijection from B to C. We want to show that h=g[itex]\circ[/itex]f is a bijection from A to C. Since f is a bijection from A to B we have that the Rng(f)=B. Now since g is a function from B to C we have that Rng(f)=Dom(g). Let f(x)=y. Then y[itex]\in[/itex]Rng(f). Thus y[itex]\in[/itex]Dom(g). Now since we have that g is a bijection from B to C, g(y) is a bijection from B to C because y[itex]\in[/itex]B but y=f(x) so g(f(x)) is a bijection. Now f(x) was a bijection from A to B so g(f(x)) is a bijection from A to B to C. In particular, g(f(x)) is a bijection from A to C. By definition we have that g(f(x))=g[itex]\circ[/itex]f. Thus h=g[itex]\circ[/itex]f is a bijection from A to C.

    I would appreciate it if someone could read over my proof and give me some feedback on it. Thanks a lot!
     
  2. jcsd
  3. May 27, 2012 #2

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    It's kind of hard to follow. Also, it doesn't make sense to say g(y) is a bijection the way you did. The mapping g is a bijection, but g(y) is an element of C.

    Go back to your basic definitions. Since you want to prove h:A→C is a bijection, you need to show two things:
    1. h is injective: if h(x)=h(y), then x=y.
    2. h is surjective: if ##y \in C##, then there exists ##x \in A## such that h(x)=y.
     
  4. May 27, 2012 #3
    Thanks for the reply!

    Here is an attempt at a better solution. I realized my proof writing skills are already insufficient and by jumbling everything up only makes it harder on you so let me fix that.

    Suppose f is a bijection from A to B and g is a bijection from B to C. We wish to show that h=[itex]g\circ f[/itex] is a bijection from A to C.

    (Part 1 to show that h is a surjection.)
    Choose any [itex]x\in A[/itex] and let y=f(x). Since f is a bijection from A to B, we must have for every [itex]y\in B[/itex] there exists an [itex]x\in A[/itex] such that f(x)=y. Now choose any [itex]y\in B[/itex] and let z=g(y). Then since g is a bijection from B to C, we have for each [itex]z\in C[/itex], there exists a [itex]y\in B[/itex] such that g(y)=z. But g(y)=g(f(x))=[itex](g\circ f)(x)[/itex]=z. Thus h(x)=[itex](g\circ f)(x)[/itex]=z. Hence for each [itex]z\in C[/itex], there exists an [itex]x\in A[/itex] such that h(x)=[itex](g\circ f)(x)[/itex]=z. This shows that h=[itex](g\circ f)[/itex] is a surjection.

    (Part 2 to show that h is an injection.)
    Since f is a bijection from A to B, we must have for each [itex]x_{1},x_{2}\in A[/itex], if [itex]f(x_{1})=f(x_{2})[/itex], then [itex]x_{1}=x_{2}[/itex]. Now choose any [itex]y_{1},y_{2}\in B[/itex] such that [itex]y_{1}=f(x_{1})[/itex] and [itex]y_{2}=f(x_{2})[/itex]. Since g is a bijection from B to C, we must have that for each [itex]y_{1},y_{2}\in B[/itex], if [itex]g(y_{1})=g(y_{2})[/itex], then [itex]y_{1}=y_{2}[/itex]. Now [itex]y_{1}=f(x_{1})[/itex] and [itex]y_{2}=f(x_{2})[/itex] so [itex]g(y_{1})=g(f(x_{1}))=(g\circ f)(x_{1})=g(y_{2})=g(f(x_{2})=(g\circ f)(x_{2}).[/itex] Since it follows that for each [itex]x_{1},x_{2}\in A[/itex], if [itex](g\circ f)(x_{1})=(g\circ f)(x_{2})[/itex] then [itex]x_{1}=x_{2}[/itex], we have that [itex]h=g\circ f[/itex] is an injection from A to C.

    Since h is both a surjection from A to C and an injection from A to C, we must have the h is a bijection from A to C.
     
  5. May 28, 2012 #4

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    Lots of problems with what you wrote.
    You don't need the fact that f is a bijection to know that f(x)=y. You chose x and then said y=f(x) is the element to which x maps.

    Above, you already said y was the element f maps x to, so you can't say you're choosing any y in B. And again, you're saying z=g(y), so there's no need to use the fact that g is surjective to say there exists an element y that g maps to z.

    If we ignore the problems above, all you've really "proved" is that if you have x in A and it maps to z=h(x), then there's an element in A, namely x, that maps to z.

    Start with ##z \in C##. This is what you're allowed to assume. You want to show that this inevitably leads to the fact that there's some element x in A that h will map to z. First, use the fact that g is surjective. What does that imply (as it's related to z)? Then use a similar argument based on the fact that f is surjective.

    Similar problems. You might find it easier to use the contrapositive of what I said above. Show that ##x_1 \ne x_2## implies ##h(x_1) \ne h(x_2)##.
     
  6. May 28, 2012 #5
    Okay. I have read over what you said and here is my next attempt. I didn't use the contra positive to show that h is injective.

    Suppose f is a bijection from A to B and g is a bijection from B to C. We want to show that h=[itex]g\circ f[/itex] is a bijection from A to C.

    (Part 1 to show that h is surjective.)
    Choose any object [itex]z\in C[/itex]. Since g is surjective from B to C, we have that for each [itex]z\in C[/itex], there exists a [itex]y\in B[/itex] such that g(y)=z. Similarly, since f is surjective from A to B, we have that for each [itex]y\in B[/itex], there exists an [itex]x\in A[/itex] such that f(x)=y. Thus we have g(y)=z and f(x)=y so g(f(x))=z. By definition we know that g(f(x))=[itex](g\circ f)(x)[/itex] so [itex](g\circ f)(x)=z[/itex]. It follows that for each [itex]z\in C[/itex], there exists an [itex]x\in A[/itex] such that [itex](g\circ f)(x)=z[/itex]. In other words h(x)=z. Hence h=[itex]g\circ f[/itex] is a surjection from A to C.

    (Part 2 to show that h is injective.)
    Suppose we have [itex]h(x_{1})=h(x_{2})[/itex]. Then since [itex]h(x)=(g\circ f)(x)=g(f(x))[/itex] we have [itex]g(f(x_{1}))=g(f(x_{2}))[/itex]. Now g is an injection from B to C so for each [itex]f(x_{1}),f(x_{2})\in B[/itex] since we have [itex]g(f(x_{1}))=g(f(x_{2}))[/itex], we must have that [itex]f(x_{1})=f(x_{2})[/itex]. Similarly since f is an injection from A to B, for each [itex]x_{1},x_{2}\in A[/itex], since [itex]f(x_{1})=f(x_{2})[/itex], we must have [itex]x_{1}=x_{2}[/itex]. Thus for each [itex]x_{1},x_{2}\in A[/itex], if we have [itex]h(x_{1})=h(x_{2})[/itex] then [itex]x_{1}=x_{2}[/itex]. Hence h=[itex]g\circ f[/itex] is an injection from A to C.

    Thus h=[itex]g\circ f[/itex] is both a surjection and an injection from A to C. Therefore h=[itex]g\circ f[/itex] is a bijection from A to C.
     
  7. May 28, 2012 #6

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    Looks good.
     
  8. May 28, 2012 #7
    Thanks a lot!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Prove that g composed of f is a bijection.
  1. Prove f(x)=g(x) (Replies: 2)

Loading...