Prove that any injective function from $\{ 1, \dots, n \}$ to itself is bijective. 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:



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.

*

*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$.

*Since $f$ and $g$ are injective, $h$ is also injective.

*I also see that $g$ undoes what $f$ does to $n + 1$, hence $h(n + 1) = n + 1$.

*The function $h$ is almost the same as $f$, except for the swapping done by $g$ as described in 1.

*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.
 A: 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 inective map from $\{1,2,\ldots,n+1\}$ into itself. There are two possibilities:

*

*$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.

*$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.

A: You have all of the pieces. You know that $h\upharpoonright\{1,\ldots,n\}$ is an injection from $\{1,\ldots,n\}$ to itself, so by the induction hypothesis it is a bijection. You also know that $h(n+1)=n+1$, so $h$ is a bijection from $\{1,\ldots,n+1\}$ to itself. Finally, you can easily verify that $f=g\circ h$, and $g$ is clearly a so $f$ is a composition of bijections from $\{1,\ldots,n+1\}$ to itself and is therefore also such a bijection.
Your first attempt is basically just handwaving.
A: Let our induction hypothesis be that, if a function from a set with n elements to a set with n elements is injective, then it is bijective.
(Notice that we are making a slightly broader statement than talking about this one set, which will allow us to avoid messiness with the casework)
Now, we prove the n+1 case. Let f be an injective function between two sets of size n+1. $f: X \rightarrow Y, |X| = n+1, |Y|=n+1$
Take an arbitrary element from $X$, say $x$, and consider the function from mapping X without x to Y without f(x). This new function, $f^*$, is defined, because no two points got sent to the same element in Y. By induction hypothesis, this function is surjective and thus bijective. Now we can conclude that f defined on all of X is surjective when sent to Y, as the only remaining element was f(x), which is in the image of x.
Basically, we are removing one element, looking at f defined on X\{x}, and arguing that it is surjective to Y{f(x)}. Then we look at X, Y and can see that if X\{x} to Y\{f(x)} is surjective, then f is surjective from X to Y.
