Composite of Surjections is a Surjection

From ProofWiki

Jump to: navigation, search

Theorem

That is:

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

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

	$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle \forall z \in S_3: \exists y \in S_2: f \left({y}\right)$	$=$	$\displaystyle z$	$\displaystyle $	$\displaystyle $	$\displaystyle $	Definition of a Surjection
	$\displaystyle $	$\displaystyle \implies$	$\displaystyle $	$\displaystyle \exists x \in S_1: g \left({x}\right)$	$=$	$\displaystyle y$	$\displaystyle $	$\displaystyle $	$\displaystyle $	Definition of a Surjection

By definition of a composite mapping, $f \circ g \left({x}\right) = f \left({g \left({x}\right)}\right) = f \left({y}\right) = z$.

Hence $f \circ g$ is surjective.

$\blacksquare$

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \forall z \in S_3: \exists y \in S_2: f \left({y}\right)\)	\(=\)	\(\displaystyle z\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of a Surjection
	\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle \exists x \in S_1: g \left({x}\right)\)	\(=\)	\(\displaystyle y\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of a Surjection