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?
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)
In both cases, a) and b), you have to prove a statement of the form . Instead of proving this directly, you can, instead, prove its contrapositive, which is .
So, in the case of a) you assume that f is not injective (i.e. that there exist two different elements in the domain of f such that ) and show that it follows that is not injective either. Which should be obvious, because
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 either, which is to say that is not surjective. This, too, should be obvious, because the range of is a subset of the range of .