# Cardinality of Surjection

## Theorem

Let $S$ be a set.

Let:

$\card S = n$

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

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

Then $\card T \le n$.

The equality:

$\card T = n$

occurs if and only if $f$ is a bijection.

## Proof

We have that $\card S = n$.

Then by definition of cardinality:

there is a surjection from $S$ to $T$
there is a surjection from $\N_n$ to $T$.

So we need consider the case only when $S = \N_n$.

By definition of surjection:

$\forall x \in T: f^{-1} \sqbrk {\set x} \ne \O$

where $f^{-1} \sqbrk {\set x}$ denotes the preimage of $\set x$ under $f$.

From the Well-Ordering Principle, $\N$ is well-ordered.

Therefore by Subset of Well-Ordered Set is Well-Ordered, $S = \N_n$ is well-ordered.

We have that $f^{-1} \sqbrk {\set x} \subseteq S$.

Therefore $f^{-1} \sqbrk {\set x}$ is also well-ordered.

Therefore, by definition of well-ordered set, $f^{-1} \sqbrk {\set x}$ has a smallest element.

Let $g: T \to S$ be the mapping defined as:

$\forall x \in T: g \paren x =$ the smallest element of $f^{-1} \sqbrk {\set x}$

Let $x \in T$.

Then:

$g \paren x \in f^{-1} \sqbrk {\set x}$

so:

$f \paren {g \paren x} = x$

Thus:

$f \circ g = I_T$
$I_T: T \to g \sqbrk T$ is a bijection.
$\card {g \sqbrk T} \le n$

Let $\card {g \sqbrk T} = m$.

$\card T = m$

Suppose $m = n$.

$g \sqbrk T = S$

so $g: T \to S$ is a bijection.

Therefore:

 $\displaystyle f$ $=$ $\displaystyle f \circ I_S$ $\displaystyle$ $=$ $\displaystyle f \circ g \circ g^{-1}$ $\displaystyle$ $=$ $\displaystyle I_S \circ g^{-1}$ $\displaystyle$ $=$ $\displaystyle g^{-1}$

So $f: S \to T$ is a bijection.

$\blacksquare$

## Also presented as

This result can also be presented as:

The mapping $f: S \to T$ cannot be a surjection if $\card S < \card T$.