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$\circ$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$\circ$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$\in$Rng(f). Thus y$\in$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$\in$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$\circ$f. Thus h=g$\circ$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=$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!