# 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$

and by Identity Mapping is Bijection:

- $I_T: T \to g \sqbrk T$ is a bijection.

By Cardinality of Subset of Finite Set:

- $\card {g \sqbrk T} \le n$

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

By Set Equivalence behaves like Equivalence Relation:

- $\card T = m$

Suppose $m = n$.

Then by Cardinality of Subset of Finite Set:

- $g \sqbrk T = S$

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

Therefore:

\(\ds f\) | \(=\) | \(\ds f \circ I_S\) | ||||||||||||

\(\ds \) | \(=\) | \(\ds f \circ g \circ g^{-1}\) | ||||||||||||

\(\ds \) | \(=\) | \(\ds I_S \circ g^{-1}\) | ||||||||||||

\(\ds \) | \(=\) | \(\ds 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$.

## Sources

- 1965: Seth Warner:
*Modern Algebra*... (previous) ... (next): Chapter $\text {III}$: The Natural Numbers: $\S 17$: Finite Sets: Theorem $17.6$ - 1996: H. Jerome Keisler and Joel Robbin:
*Mathematical Logic and Computability*... (previous) ... (next): Appendix $\text{A}.10$: Finite Sequences: Proposition $\text{A}.10.1: \ 2$ - 2008: David Joyner:
*Adventures in Group Theory*(2nd ed.) ... (previous) ... (next): Chapter $2$: 'And you do addition?': $\S 2.1$: Functions: Ponderable $2.1.4$