Injection from Finite Set to Itself is Surjection

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ be a finite set.

Let $f: S \to S$ be an injection.


Then $f$ is also a surjection.


Corollary

Let $S$ be a finite set.

Let $f: S \to S$ be an injection.


Then $f$ is a permutation.


Proof

Let $a \in S$.

We need to show that there exists $b \in S$ such that $a = \map f b$.


Consider what happens when $f$ is applied repeatedly on $S$.

Let $f^2$ denote $f \circ f$ and, generally, $f^n := f \circ f^{n-1}$.

Consider the sequence of elements of $S$:

$a, \map f a, \map {f^2} a, \ldots$

Because $S$ is a finite set, there must be repetitions.

That is, there must exist $r, s \in \N$ such that:

$\map {f^r} a = \map {f^s} a$

where $r \ne s$.

Without loss of generality, assume $r > s$.

$f$ is an injection.

Therefore by Composite of Injections is Injection, $f^s$ is an injection.

By Injection iff Left Cancellable, $f^s$ is left cancellable.

Thus:

\(\ds \map {f^r} a\) \(=\) \(\ds \map {f^s} a\)
\(\ds \leadsto \ \ \) \(\ds \map {f^s \circ f^{r - s} } a\) \(=\) \(\ds \map {f^s} a\)
\(\ds \leadsto \ \ \) \(\ds \map {f^{r - s} } a\) \(=\) \(\ds a\) Definition of Left Cancellable Mapping

That is, $b = \map {f^{r - s - 1} } a$.

$\blacksquare$


Sources