Prove that any injective function from $\{ 1, \dots, n \}$ to itself is bijective.

elementary-set-theoryfunctionsinductionsolution-verification

This is Exercise 1 from page 50 of Analysis I by Amann and Escher. I have found similar questions here and here but neither of those questions has a solution that uses what's hinted at in the text.

Exercise:

enter image description here

My attempt:

It seems simple to argue that, since an injective function sends each element in its domain to a different element in the codomain, it has to "hit" all the elements in $\{ 1, \dots, n \}$. I am not sure if this is formal enough, and at any rate it doesn't use the hint given.

If I use the hint, then the base case of an injective function $\{ 1 \} \to \{ 1 \}$ is definitely bijective. Assume that any injective function from $\{ 1, \dots, n \}$ to $\{ 1, \dots, n \}$ is bijective, and consider the injective function $f \colon \{ 1 , \dots, n + 1 \} \to \{ 1 , \dots, n + 1 \}$ as described. We want to show that $f$ is bijective.

It seems to me that there are at least two basic ways to show that $f$ is bijective. First, we can show that it's surjective, which involves considering some element $l \in \{ 1 , \dots, n + 1 \}$ and showing there exists an element $m$ in the same set such that $f(m) = l$. The second way is to show that there exists a function $i$ such that $f \circ i$ is the identity function. However, an inductive proof should really use the inductive assumption, and I'm not sure either of these tactics do.

I find the hint given pretty mystifying, but I have collected a few thoughts regarding the hint below.

  1. I see that $g$ is bijective. It is almost the identity function except that it sends $k$ to $n + 1$ and $n + 1$ to $k$.
  2. Since $f$ and $g$ are injective, $h$ is also injective.
  3. I also see that $g$ undoes what $f$ does to $n + 1$, hence $h(n + 1) = n + 1$.
  4. The function $h$ is almost the same as $f$, except for the swapping done by $g$ as described in 1.
  5. The restriction $h \mid \{ 1, \dots, n\}$ does not send any element to $n + 1$, because the only element that $h$ sends to $n + 1$ is $n + 1$, and $n + 1$ is outside the restriction.

I have no idea how to cobble this into a proof. I appreciate any help.

Best Answer

As you wrote, the case $n=1$ is easy. Assume that every injective map from $\{1,2,\ldots,n\}$ into itself is bijective and let $f$ be an injective map from $\{1,2,\ldots,n+1\}$ into itself. There are two possibilities:

  1. $f(n+1)=n+1$: Then, since $f$ is injective, $f\bigl(\{1,2,\ldots,n\}\bigr)\subset \{1,2,\ldots,n\}$. So, by the induction hypothesis, each $k\in\{1,2,\ldots,n\}$ is equal to $f(l)$, for some $l\in\{1,2,\ldots,n\}$. Since $f(n+1)=n+1$, $f$ is bijective.
  2. $f(n+1)=k$, for some $k<n+1$: Then $g\circ f$ maps $n+1$ into $n+1$ and what was written in the previous paragraph shows that $g\circ f$ is bijective. Since $g$ is bijective, $f=g^{-1}\circ(g\circ f)$ and so $f$ is bijective too.
Related Question