[SOLVED] proving g of f of x is injective/surjective

• Aug 10th 2009, 05:32 PM
Kitizhi
[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)
• Aug 10th 2009, 06:21 PM
Kitizhi
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?
• Aug 10th 2009, 08:58 PM
Kitizhi
Anyone?

I think I completed the first part but I need to prove that if (g ○ f) is surjective then g must be surjective.
• Aug 10th 2009, 10:00 PM
Failure
Quote:

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

$(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 $g\circ f$ either, which is to say that $g\circ f$ is not surjective. This, too, should be obvious, because the range of $g\circ f$ is a subset of the range of $g$.
• Aug 11th 2009, 03:31 AM
Plato
Quote:

Originally Posted by Kitizhi
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 $f\left( {a_1 } \right) = f\left( {a_2 } \right)$ then definition $g \circ f\left( {a_1 } \right) = g \circ f\left( {a_2 } \right)$.
We know that $g \circ f$ is injective, so $a_1=a_2$. That shows that $f$ is injective.

b) Suppose that $y\in C$. $g \circ f$ is surjective, so $\left( {\exists a \in A} \right)\left[ {g \circ f\left( a \right) = y} \right]$. But $f(a)\in B$ so $g$ is surjective.