Is my proof for "If $f$ and $g$ are surjective, then $g\circ f$ surjective" valid?

Question

Any advice is greatly appreciated. I wrote this proof but still struggle to understnad it. I am especially worried about the 2nd to last line.

PROOF:

Because $f$ is surjective, for all $b$ in $B$ there exist an $a$ in $A$ such that $f(a)=b$.

Now, $$(g\circ f)(a)=g(f(a))=g(b).$$

Because $g$ is surjective, for all $c$ in $C$ there exist a $b$ in $B$ such that $f(b)=c$.

Therefore, for all $c$ in $C$ there exist an $a$ in $A$ such that $g(f(a))=(g\circ f)(a)=c$.

And so $g\circ f$ is surjective if both $g$ and $f$ are surjectie.

QED

Answer 1

The idea is right. It's not exactly wrong. But things are in the wrong order. As it is, you have basically said:

• $f$ is surjective. (state definition)
• $g$ is surjective. (state definition)
• Therefore, $g \circ f$ is surjective. (state definition)

Here it's obvious enough that that looks sort of like a proof, but the structure is wrong.

You don't want to use the definitions unless you know exactly how they help you. Just re-stating the definitions again isn't useful. Start just with the given hypotheses:

Suppose $f: A \rightarrow B$ and $g: B \rightarrow C$ are surjective.

Now think about what you want to prove: "For all $c \in C$, there is $a \in A$ with $(g \circ f)(a) = c$." You aren't there yet, but that's the goal. Since you want to prove a universally quantified statement ("For all $c \in C$..."), you automatically write:

Let $c \in C$.

Now you have a thing called $c$ in play and you can refer to it subsequently. You want to prove something about it: "...there is $a \in A$ with $(g \circ f)(a) = c$." You need to get your hands on such $a \in A$ somehow. Now think about the definition you have: "For all $c$ in $C$ there exist a $b$ in $B$ such that $g(b)=c$." But you don't need to state this. We already know it. Just apply it to your $c$ which is already in play:

Because $g$ is surjective, there is some $b \in B$ with $g(b) = c$.

Now you have a thing called $b$ you can reason about. Next step is obvious:

Then because $f$ is surjective, there is some $a \in A$ with $f(a) = b$.

Now you have your $a$. To finish, prove the thing you need to prove about $a$:

Thus $(g\circ f)(a) = g(f(a)) = g(b) = c$.

Finally, if you like, give one last sentence saying that you're done:

So $g\circ f$ is surjective.

All together:

Suppose $f: A \rightarrow B$ and $g: B \rightarrow C$ are surjective. Let $c \in C$. Because $g$ is surjective, there is some $b \in B$ with $g(b) = c$. Then because $f$ is surjective, there is some $a \in A$ with $f(a) = b$. Thus $(g\circ f)(a) = g(f(a)) = g(b) = c$. So $g\circ f$ is surjective.

Answer 2

It's a little mixed up, and there some steps that I'm not convinced need to be there, but you have the right steps there. I would just rearrange it like so:

Suppose $c \in C$. Because $g$ is surjective, there exists some $b \in B$ such that $g(b) = c$. Since $f$ is surjective, there exists some $a \in A$ such that $f(a) = b$. Then, $$(g \circ f)(a) = g(f(a)) = g(b) = c,$$ proving $g \circ f$ is surjective.

Note how much more streamlined it is. It helps to write out exactly what it is you're supposed to be proving (i.e. for all $c \in C$, there exists an $a \in A$ such that $(g \circ f)(a) = c$), and work from there.