Surjection from Finite Set to Itself is Permutation

From ProofWiki
Jump to navigation Jump to search


Let $S$ be a finite set.

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

Then $f$ is a permutation.


From Surjection iff Right Inverse, $f$ has a right inverse $g: S \to S$.

From Right Inverse Mapping is Injection, $g$ is an injection.

From Injection from Finite Set to Itself is Permutation, $g$ is a permutation and so a bijection.

From Inverse of Bijection is Bijection, $f$ is also a bijection.

Thus as $f$ is a bijection to itself, it is by definition a permutation.