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