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.
PF:
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).

page revision: 2, last edited: 26 Feb 2018 20:27
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License