Cardinality of Surjection

From ProofWiki
Jump to navigation Jump to search

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$

if and only if:

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$

elements.


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

Retrieved from "https://proofwiki.org/w/index.php?title=Cardinality_of_Surjection&oldid=585921"