Proof Verification: If $g\circ f$ is surjective, Prove that $g$ is surjective.

Question

It's given that $f:A \to B$ and $g:B \to C$.

My Proof:

If $g\circ f$ is surjective then all elements $z∈C$ can be written as $g(f(x))$ where $x∈A$.

We know that for all $x∈A$, $f(x)∈B$ and that for all elements $y∈B$, $g(y)∈C$. Let S be the set containing all elements of $B$ which can be written as $f(x)$, where $x∈A$. Now the set of all $g(s)$,where $s∈S$ would be equal to the set C since the set of all $g(s)$ is the set of all $g(f(x))$. This implies that g is surjective.

Please verify if this is logically correct and rigorous enough.

Answer 1

I wouldn't write it like that. Usually surjectivity of a function $f: X \to Y$ is proven in the following way:

Take $y \in Y$, and find an element $x \in X$ such that $f(x) = y$

---

Let's do this now:

Take $c \in C$. Since $g \circ f$ is surjective, there exists $a \in A$ such that $g(f(a)) = (g \circ f)(a) = c$ and $f(a)$ is the element we are looking for.

Answer 2

Another proof: Suppose that $g$ is non-surjective, namely there exists some $c\in C$ such that for all $b\in B$, $g(b)\neq c$. Thus, we have $$g\circ f=g(f(a))\neq c,$$ since $f(a)\in B$. Can you conclude from here? (Spoiler below)

The above equation shows that $g\circ f$ is non-surjective. By contraposition, we get the desired result.

Answer 3

If $g \circ f$ is surjective then all elements $z \in C$ can be written $g(f(x))$ where $x \in A$.

True enough. It might be slightly clearer to say "... can be written $z=g(f(x))$ where $x \in $A".

One slight problem with this beginning is that the way the sentence is, the starting point of "$g \circ f$ is surjective" modifies just the one sentence. But you want that to be the assumption for the entire proof. So I would write this instead something like:

"Suppose $g \circ f$ is surjective. This means any element $z \in C$ can be written $z=g(f(x))$ where $x \in A$."

We know that for all $x \in A$, $f(x)\in B$ and that for all elements $y \in B$, $g(y) \in C.$

This sentence is just repeating the given that $f : A \to B$ and $g : B \to C$. I don't think it adds anything to the proof, especially since you don't obviously and directly use the statements in that form.

Let $S$ be the set containing all elements of $B$ which can be written as $f(x)$, where $x \in A$.

Have you come across the term "image" of a function? This would be an excellent place to use it, so that any other reader familiar with the term can immediately associate what they know about it:

"Let $S$ be the image of $f$; that is, the set containing all elements of $B$ which can be written as $f(x)$, where $x \in A$."

(Or if I could assume everyone in the intended audience of my proof understands "image", I might just write "Let $S \subseteq B$ be the image of $f$.")

Now the set of all $g(s)$, where $s \in S$ would be equal to the set $C$ since the set of all $g(s)$ is the set of all $g(f(x))$.

Here I'm not too comfortable following this. Doing arguments on transformations on "the set of all..." is not the usual rigorous approach, and I wouldn't be surprised if in some situations it could lead you to a false conclusion.

The usual and safer way is to demonstrate things about sets by demonstrating things about elements of those sets. This involves phrases like "for all" (or "for each" or "for every"), abbreviated $\forall$, and "there exists", abbreviated $\exists$.

So one way to write the definition of surjective is:

A function $\varphi : X \to Y$ is called surjective if $\forall y \in Y\: \exists x \in X : y=\varphi(x)$.

Backing up, I would write this proof like the following:

Given $f : A \to B$ and $g : B \to C$, prove that if $g \circ f$ is surjective, then $g$ is surjective.

Proof:

Suppose $g \circ f$ is surjective. That is, $\forall z \in C\: \exists x \in A : z = (g \circ f)(x)$.

Let $z$ be any element of $C$. We know there is some $x \in A$ with $z = (g \circ f)(x) = g(f(x))$.

So let $y = f(x)$. Then $z = g(y)$.

This shows $\forall z \in C\: \exists y \in B : z = g(y)$, so $g$ is surjective.