Composite of Surjections is Surjection

From ProofWiki
Jump to navigation Jump to search

Theorem

A composite of surjections is a surjection.


That is:

If $g$ and $f$ are surjections, then so is $g \circ f$.


Proof

Let $f: S_1 \to S_2$ and $g: S_2 \to S_3$ be surjections.

Then:

\(\displaystyle \forall z \in S_3: \exists y \in S_2: \map g y\) \(=\) \(\displaystyle z\) Definition of Surjection
\(\displaystyle \leadsto \ \ \) \(\displaystyle \exists x \in S_1: \map f x\) \(=\) \(\displaystyle y\) Definition of Surjection

By definition of a composite mapping:

$\map {g \circ f} x = \map g {\map f x} = \map g y = z$

Hence $g \circ f$ is surjective.

$\blacksquare$


Sources