Mapping from Finite Set to Itself is Injection iff Surjection

From ProofWiki
Jump to navigation Jump to search


Let $S$ be a finite set.

Let $f: S \to S$ be a mapping.

Then $f$ is injective if and only if $f$ is surjective.


Let $f$ be an injection.

From Injection to Image is Bijection, $S$ is equivalent to the image $\Img f$ of $f$.

We are given that $S$ is finite.

It follows from Infinite Set is Equivalent to Proper Subset that $\Img f = S$.

It follows by definition that $f$ is surjective.


Let $f$ be a surjection.

Then by Surjection iff Right Inverse there exists a mapping $g: S \to S$ such that:

$f \circ g = I_S$

where $I_S$ is the identity mapping.

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

By the above, it follows that $g$ is also a surjection.

Thus $g$ is a bijection.

It follows that $f = g^{-1}$ is also a bijection and so by definition an injection.