Question 14 Post Write

14. Statement: If X is a finite set and f is an injective function from X→X, then f is bijective.
Proof: Let f be an injective function from a set X to a set Y, both with cardinality n. The statement is vacuously true for n=0. We can then assume that for any two sets that each have equal cardinality less than some positive integer n, any injection between them is also surjective. Now remove the point (a, f(a)) from the set. By injection, f(a) has only the preimagine a and by virtue of being a function, a only has the imagine f(a); removing this pair removes a from the domain and f(a) from the codomain. The resulting function is a set with cardinality n-1, and by the assumption, it is assumed to be surjective. Any function that is both injective and surjective is bijective.

Comments - Andrew Furash
Great work!

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