5
$\begingroup$

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$.

  • 0
    ouch, did not look accurately enough. Only noted Krysten found the counter counter image which is needed...2011-12-11

2 Answers 2

3

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)$.

  • 0
    @Krysten: You're welcomed.2011-12-11
2

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.

  • 0
    thanks. this makes a lot of sense2011-12-11