Equivalence of Definitions of Surjection

From ProofWiki
Jump to navigation Jump to search

Theorem

The following definitions of the concept of Surjection are equivalent:

Definition 1

$f: S \to T$ is a surjection if and only if:

$\forall y \in T: \exists x \in \Dom f: \map f x = y$

That is, if and only if $f$ is right-total.

Definition 2

$f: S \to T$ is a surjection if and only if:

$f \sqbrk S = T$

or, in the language and notation of direct image mappings:

$\map {f^\to} S = T$


That is, $f$ is a surjection if and only if its image equals its codomain:

$\Img f = \Cdm f$


Proof

Definition 1 implies Definition 2

Let $f$ be a mapping which fulfils the condition:

$\forall y \in T: \exists x \in \Dom f: f \paren x = y$

From Image is Subset of Codomain:

$\Img f \subseteq T$

It remains to be proved that:

$T \subseteq \Img f$


Thus:

\(\displaystyle y\) \(\in\) \(\displaystyle T\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle \exists x \in \Dom f: f \paren x\) \(=\) \(\displaystyle y\) by hypothesis
\(\displaystyle \leadsto \ \ \) \(\displaystyle y\) \(\in\) \(\displaystyle \Img f\) Definition of Image of Mapping
\(\displaystyle \leadsto \ \ \) \(\displaystyle T\) \(\subseteq\) \(\displaystyle \Img f\) Definition of Subset


Thus by definition of set equality:

$\Img f = T$

and by definition of image of mapping:

$f \sqbrk S = T$


Hence $f$ is a surjection by definition 2.

$\Box$


Definition 2 implies Definition 1

Let $f$ be a mapping which fulfils the condition:

$f \sqbrk S = T$

that is:

$\Img f = T$

Then by definition of set equality:

$T \subseteq \Img f$

Hence:

\(\displaystyle y\) \(\in\) \(\displaystyle T\)
\(\displaystyle \implies \ \ \) \(\displaystyle y\) \(\in\) \(\displaystyle \Img f\)

So by the definition of the image of $f$:

$\exists x \in \Dom f: f \paren x = y$

Hence $f$ is a surjection by definition 1.

$\blacksquare$


Sources