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$.
Proof
Necessary Condition
Suppose $f: S \to T$ is a surjection.
Then $\Img f = T$ by definition.
From Cardinality of Image of Mapping not greater than Cardinality of Domain:
- $\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$
Sufficient Condition
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$
Sources
- 1971: Gaisi Takeuti and Wilson M. Zaring: Introduction to Axiomatic Set Theory: $\S 10.27$