Proof verification: If $g\circ f$ is surjective, show that $g$ is surjective.

Let $$X,Y,Z$$ be sets and $$f: X\to Y$$, $$g: Y\to Z$$ functions. If $$g\circ f$$ is surjective, prove that $$g$$ is surjective.

Here's my sketch: Since $$g\circ f : X\to Z$$ is surjective, there are for every $$z\in Z$$ at least one $$x\in X$$ with $$f(z)=x$$. This means that $$\#X \geq \# Z$$ . Furthermore, we know that every $$x\in X$$ will mapped to $$f(x)=y$$. $$g$$ can only map $$g(y)=z$$ with $$y$$ being the elements of the image of $$f$$. Ultimately, the amount of $$y=f(x)$$-values is dependent on the amount of values in $$Z$$. There can never be more Elements $$f(x)=y\in Y$$ then there are elements in $$Z$$. Hence $$g$$ is surjective.

I hope you get what I just wrote since it is really hard to explain in English.

• Take an element $z$ of $Z$. Since $g\circ f$ is surjective, there is an element $x$ of $X$ such that $g(f(x))=z$. Now consider the element $f(x)$ of $Y$. What can you conclude about $f$? – Valerio Jul 30 at 1:02

You don't really need to argue with elements:

Since $$f(X) \subseteq Y$$, we have $$Z = g(f(X)) \subseteq g(Y) \subseteq Z$$, which implies $$g(Y)=Z$$, and $$g$$ is surjective.

Let $$f:X \to Y$$ and $$g:Y\to Z$$. We need to prove that if $$g\circ f:X\to Z$$ is surjective, then so is $$g$$.

Idea of Proof: We need to find a $$y\in Y$$ such that $$g(y)=z$$ for every $$z\in Z$$ in accordance to the definition of a surjection.

Proof: Suppose $$g\circ f:X\to Z$$ is surjective. Take any $$z\in Z$$. Since $$g\circ f$$ is surjective, there exists some $$x\in X$$ such that $$(g\circ f)(x)=z$$.

Therefore, $$g(f(x))=z$$. Set $$y=f(x)\in Y$$. Then, $$g(y)=g(f(x))=z$$. Hence, $$g$$ must be surjective.

Let $$c \in Z \implies a \in X$$ such that $$(g\circ f)(a) = c$$. This is true since $$(g\circ f)$$ is onto. But $$(g\circ f)(a) = g(f(a))$$. So if you put $$b = f(a) \in Y$$, then $$g(b) = c$$, proving $$g$$ onto. I think this notation is easier to remember than yours...

We need to prove that $$\forall z \in Z \exists y \in Y(z=f(y))$$ Let z in Z.
$$f \circ g$$ iz onto, so let x in X so that $$z=(f \circ g)(x)$$
$$g(x) \in Y$$
Well, we found element y in Y - $$g(x)$$ - so that $$z=f(y)$$. And so we proved that $$f$$ is onto.