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\circf 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\circf 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\inRng(f). Thus y\inDom(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\inB 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\circf. Thus h=g\circf 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=g\circ f is a bijection from A to C.

(Part 1 to show that h is a surjection.)
Choose any x\in A and let y=f(x). Since f is a bijection from A to B, we must have for every y\in B there exists an x\in A such that f(x)=y. Now choose any y\in B and let z=g(y). Then since g is a bijection from B to C, we have for each z\in C, there exists a y\in B such that g(y)=z. But g(y)=g(f(x))=(g\circ f)(x)=z. Thus h(x)=(g\circ f)(x)=z. Hence for each z\in C, there exists an x\in A such that h(x)=(g\circ f)(x)=z. This shows that h=(g\circ f) 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 x_{1},x_{2}\in A, if f(x_{1})=f(x_{2}), then x_{1}=x_{2}. Now choose any y_{1},y_{2}\in B such that y_{1}=f(x_{1}) and y_{2}=f(x_{2}). Since g is a bijection from B to C, we must have that for each y_{1},y_{2}\in B, if g(y_{1})=g(y_{2}), then y_{1}=y_{2}. Now y_{1}=f(x_{1}) and y_{2}=f(x_{2}) so g(y_{1})=g(f(x_{1}))=(g\circ f)(x_{1})=g(y_{2})=g(f(x_{2})=(g\circ f)(x_{2}). Since it follows that for each x_{1},x_{2}\in A, if (g\circ f)(x_{1})=(g\circ f)(x_{2}) then x_{1}=x_{2}, we have that h=g\circ f 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 x\in A and let y=f(x). Since f is a bijection from A to B, we must have for every y\in B there exists an x\in A 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 y\in B and let z=g(y). Then since g is a bijection from B to C, we have for each z\in C, there exists a y\in B 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))=(g\circ f)(x)=z. Thus h(x)=(g\circ f)(x)=z. Hence for each z\in C, there exists an x\in A such that h(x)=(g\circ f)(x)=z. This shows that h=(g\circ f) 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 x_{1},x_{2}\in A, if f(x_{1})=f(x_{2}), then x_{1}=x_{2}. Now choose any y_{1},y_{2}\in B such that y_{1}=f(x_{1}) and y_{2}=f(x_{2}). Since g is a bijection from B to C, we must have that for each y_{1},y_{2}\in B, if g(y_{1})=g(y_{2}), then y_{1}=y_{2}. Now y_{1}=f(x_{1}) and y_{2}=f(x_{2}) so g(y_{1})=g(f(x_{1}))=(g\circ f)(x_{1})=g(y_{2})=g(f(x_{2})=(g\circ f)(x_{2}). Since it follows that for each x_{1},x_{2}\in A, if (g\circ f)(x_{1})=(g\circ f)(x_{2}) then x_{1}=x_{2}, we have that h=g\circ f 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=g\circ f is a bijection from A to C.

(Part 1 to show that h is surjective.)
Choose any object z\in C. Since g is surjective from B to C, we have that for each z\in C, there exists a y\in B such that g(y)=z. Similarly, since f is surjective from A to B, we have that for each y\in B, there exists an x\in A 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))=(g\circ f)(x) so (g\circ f)(x)=z. It follows that for each z\in C, there exists an x\in A such that (g\circ f)(x)=z. In other words h(x)=z. Hence h=g\circ f is a surjection from A to C.

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

Thus h=g\circ f is both a surjection and an injection from A to C. Therefore h=g\circ f is a bijection from A to C.

 

[vela]

Looks good.

 

[DeadOriginal]

Thanks a lot!