Surjection iff Cardinal Inequality

Theorem

Let $S$ and $T$ be sets.

Let $S$ be non-empty.

Then:

$0 < \card T \le \card S$

there exists a surjection $f: S \to T$

where $\card S$ denotes the cardinality of $S$.

Suppose $f: S \to T$ is a surjection.

Then $\Img f = T$ by definition.

$\card T \le \card S$

Furthermore, if $S$ is non-empty, then $\map f x \in T$ for some $x \in S$.

Thus, $T$ is non-empty and $0 < \card T$ by Cardinality of Empty Set.

$\Box$

Suppose that $0 < \card T \le \card S$.

By Injection iff Cardinal Inequality, it follows that $g: T \to S$ for some injection $g$.

Take an arbitrary $y \in T$.

Define the function $f: S \to T$ as follows:

$\map f x = \begin{cases} \map {g^{-1} } x & : x \in \Img g \\ y & : x \notin \Img g \end{cases}$

For any $z \in T$, $\map g z \in \Img g$.

Thus, $\map f x = z$ for some $x \in S$.

It follows that $f: S \to T$ is a surjection.

$\blacksquare$