Surjection iff Image equals Codomain

From ProofWiki

Jump to: navigation, search

Theorem

A mapping $f: S \to T$ is a surjection iff its image equals its codomain:

$\operatorname{Im} \left({f}\right) = \operatorname{Cdm} \left({f}\right)$

That is, iff $f \left({S}\right) = T$.

Some sources use this as the definition of a surjection.

Let $f: S \to T$ be a mapping.

First suppose that $\operatorname{Im} \left({f}\right) = T$.

Then by the definition of set equality, $T \subseteq \operatorname{Im} \left({f}\right)$.

Hence:

	$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle y$	$\in$	$\displaystyle T$	$\displaystyle $	$\displaystyle $	$\displaystyle $
	$\displaystyle $	$\displaystyle \implies$	$\displaystyle $	$\displaystyle y$	$\in$	$\displaystyle \operatorname{Im} \left({f}\right)$	$\displaystyle $	$\displaystyle $	$\displaystyle $

So by the definition of the image of $f$, $\exists x \in \operatorname{Dom} \left({f}\right): f \left({x}\right) = y$.

Thus $f$ is a surjection.

$\Box$

Now suppose that $f: S \to T$ is a surjection.

We already have $\operatorname{Im} \left({f}\right) \subseteq T$ from Image is Subset of Codomain.

So all we need to do is prove that $T \subseteq \operatorname{Im} \left({f}\right)$.

Thus:

$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle y$	$\in$	$\displaystyle T$	$\displaystyle $	$\displaystyle $	$\displaystyle $
$\displaystyle $	$\displaystyle \implies$	$\displaystyle $	$\displaystyle \exists x \in \operatorname{Dom} \left({f}\right): f \left({x}\right)$	$=$	$\displaystyle y$	$\displaystyle $	$\displaystyle $	$\displaystyle $	Definition of Surjection
$\displaystyle $	$\displaystyle \implies$	$\displaystyle $	$\displaystyle y$	$\in$	$\displaystyle \operatorname{Im} \left({f}\right)$	$\displaystyle $	$\displaystyle $	$\displaystyle $	Definition of image of $f$

By the definition of a subset, this proves that $T \subseteq \operatorname{Im} \left({f}\right)$.

Thus by the definition of set equality, $T = \operatorname{Im} \left({f}\right)$ and the proof is complete.

$\blacksquare$

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle y\)	\(\in\)	\(\displaystyle T\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle y\)	\(\in\)	\(\displaystyle \operatorname{Im} \left({f}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle y\)	\(\in\)	\(\displaystyle T\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle \exists x \in \operatorname{Dom} \left({f}\right): f \left({x}\right)\)	\(=\)	\(\displaystyle y\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Surjection
\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle y\)	\(\in\)	\(\displaystyle \operatorname{Im} \left({f}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of image of $f$