Consider the following two problems, from Herstein's Abstract Algebra:

  1. if $S$ is a finite set and $f$ is a mapping of $S$ onto itself, show that $f$ must be 1-1.
  2. if $S$ is a finite set and $f$ is a 1-1 mapping of $S$ into itself, show that $f$ must be surjective.

Intuitively I can grasp why these propositions are true, but I would like to see a full formal proof of this.

My attempt.

1) Let $S=\{x_1,\dots,x_n\}$, with $n = \#S$, the number of elements in $S$. Since $f$ is onto, for any $x_i\in S$, there exists $x_j\in S$ s.t. $x_i=f(x_j)$. Start with $x_1$ chosen in any order, and call $x_{s(1)}$ the element of $S$ s.t. $f(x_{s(1)})=x_1$. This element certainly exists because $f$ is surjective. Move on to the next element $x_2$. Certainly there exists $x_{s(2)}$ that is the preimage of $x_2$ under $f$. It must be $x_{s(2)}\ne x_{s(1)}$, otherwise $f$ would be multiple valued. Generalising this reasoning, it follows that for the $n$ elements of $S$, there must be $n$ distinct preimages. Since the sets $S$ and $\{x_{s(i)}\}_{i=1}^n$ are both finite and have the same number of elements, and each $x_{s(i)}$ is just a reordering of the elements of $S$, it follows that the two sets are actually the same set. By construction, all the $x_{s(i)}$ are distinct, so $f(x_{s(i)})\ne f(x_{s(j)})$ for $i\ne j$, which is the definition of injectivity for $f$.

I tried to be as rigorous as I could, but it is not clear to me how these simple problems, which can be grasped intuitively, should be addressed in full formal rigor.

  • 1
    $\begingroup$ By how you've reasoned so far, perhaps you would prefer an inductive proof (assuming that you've come across induction, that is) on the size of $S$. That would give your reasoning a more formal structure. $\endgroup$ – Bill Wallis May 18 '18 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.