Surjection iff Cardinal Inequality

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ and $T$ be sets such that $S \sim \card S$ and $T \sim \card T$.

Furthermore, let $S$ be non-empty.


Then:

$0 < \card T \le \card S$ if and only if there exists a surjection $f: S \to T$.


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