Finalized Number 14

14. Using induction, prove that if X is a finite set and f is an injective function from X to X, then f is bijective.
Let $f$ be an injective function from a finite set X to itself. Suppose the cardinality of $X$ is $n$. Then the cardinality of both sets is $n$.
The statement is thus vacuously true if $n=0$.
Towards induction, assume that any two sets with equal cardinality less than $n$, an injective function between them is also surjective. If a pair $(a,f(a))$ is removed, then both $a$ is removed only from the image $f(a)$ and no other images in $X$ and $f(a)$ is removed from $X$ as well. The resulting set $X$ would then have cardinality $n-1$ or $n-2$. By the inductive hypothesis, it is assumed to be surjective.
Therefore, if it is both injective and surjective it is also bijective.
Thus, $f$ is bijective.

Comments - Andrew Furash
You make a weird choice for your inductive step: assuming it is true for something less than n instead of n. Still valid, but an uncommon stylistic decision. The resulting cardinality after removing the pair (a, f(a)) will be n-1 NOT n-2 (because of injection).

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License