Cardinality of Surjection

Theorem

Let $\left|{S}\right| = n$.

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

Then $\left|{T}\right| \le n$.

Also, $\left|{T}\right| = n$ iff $f$ is a bijection.

Proof

• Since $\left|{S}\right| = n$, there is a surjection from $S$ to $T$ iff there is a surjection from $\N_n$ to $T$ from the definition of cardinality.

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

For each $x \in T$, the set $f^{-1} \left({\left\{{x}\right\}}\right) \ne \varnothing$ as $f$ is a surjection.

By naturally ordered semigroup: NO 1, $S = \N_n$ is well-ordered as it is a subset of $\N$, a well-ordered set.

Similarly, as $f^{-1} \left({\left\{{x}\right\}}\right) \subseteq S$, $f^{-1} \left({\left\{{x}\right\}}\right)$ is also well-ordered so therefore has a minimal element.

So we may define a mapping $g: T \to S$:

$\forall x \in T: g \left({x}\right) =$ the minimal element of $f^{-1} \left({\left\{{x}\right\}}\right)$.

If $x \in T$, then $g \left({x}\right) \in f^{-1} \left({\left\{{x}\right\}}\right)$, so $f \left({g \left({x}\right)}\right) = x$.

Thus $f \circ g = I_T$ and by Identity Mapping is a Bijection $I_T: T \to g \left({T}\right)$ is a bijection.

By Cardinality of Subset of Finite Set, $\left|{g \left({T}\right)}\right| \le n$.

• Let $\left|{g \left({T}\right)}\right| = m$. By Set Equivalence an Equivalence Relation, $\left|{T}\right| = m$ elements.

Suppose $m = n$.

Then by Cardinality of Subset of Finite Set, $g \left({T}\right) = S$, so $g: T \to S$ is a bijection.

Therefore:

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

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

$\blacksquare$

Sources

• Seth Warner: Modern Algebra (1965)... (previous)... (next): $\S 17$: Theorem $17.6$
• H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability (1996): Appendix $\text{A}.10$: Proposition $\text{A}.10.1: 2$