Prove that g composed of f is a bijection.

[DeadOriginal]

Homework Statement

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.

Homework Equations

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

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!

 

[vela]

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.

 

[DeadOriginal]

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.

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.

 

[vela]

Lots of problems with what you wrote.

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.

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.

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.

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.

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.

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.

(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.

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)##.

 

[DeadOriginal]

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.

 

[vela]

Looks good.

 

[DeadOriginal]

Thanks a lot!