# Proving a function is surjective

Is this a valid proof for the following?

Let $f$ and $g$ be functions such that $f: A \to B$ and $g: B \to C$. Prove or disprove that if $g(f(x))$ is surjective, then $g$ is surjective.

To show that $g$ is onto, it must be shown that for every element $c \in C$, $g(b) = c$ for some $b \in B$. Since we know that $g(f(x))$ is onto, then for every element $c \in C$, $g(f(a)) = c$ for some $a \in A$, which means that for every element $b \in B$, $f(a) = b$ for some $a \in A$.

That is, $g(f(a)) = g(b) = c$.

Therefore, we have shown that $g$ is onto $C$.

-
yes, that's a valid proof. –  user20266 Dec 11 '11 at 18:33
No, that's not a valid proof. Specifically, $f$ does not have to be surjective which you assert in your "for every element $b\in B,$ $f(a) = b$ for some $a\in A$. –  Jason DeVito Dec 11 '11 at 18:35
ouch, did not look accurately enough. Only noted Krysten found the counter counter image which is needed... –  user20266 Dec 11 '11 at 18:43

The idea is solid, but you have a flawed reasoning at the end there.

If $g$ is surjective it does not necessarily means that $f$ is surjective. Consider the case:

• $A=\{0\}$, $B=\{1,2\}$ and $C=\{3\}$.
• $f(0)=1$ and $g(1)=g(2)=3$.

The composition is surjective and indeed so is $g$, but not every $b\in B$ is $f(a)$ for some $a\in A$.

To correct your proof, note that it is not needed that $f$ is surjective, but rather that for every $c\in C$, there is some $a\in A$ such that $f(a)$ is sent to $c$ by $g$ (that is $g(f(a))=c$). This is enough to show that $g$ is surjective even if restricted to $\operatorname{Rng}(f)$.

-
thanks. this explanation really helped. –  Krysten Dec 11 '11 at 19:49
@Krysten: You're welcomed. –  Asaf Karagila Dec 11 '11 at 20:30

It is true that $g$ is surjective, but there are flaws in your argument. You are claiming that $f$ is surjective when you say "for every element $b \in B$, $f(a)=b$ for some $a \in A$." This is not true in general. What is true is that for any $c \in C$ there exists some $a$ such that $g(f(a)) = c$. Then $f(a) \in B$, and if we let $x = f(a)$, then $g(x) = g(f(a)) = c$. So $g$ is surjective.

-
thanks. this makes a lot of sense –  Krysten Dec 11 '11 at 19:50