Specific poof by induction of the pigeonhole principle I have real trouble understanding this formal proof of the pigeonhole principle. I must also state that I struggle with understanding proofs by induction in general. I still haven't gotten the hang of them.
I have added my questions in brackets.
Theorem: Let $m > n \geqslant 1$ be natural numbers. Then there is no injective function from $\{1, \dots, m\} \to \{1, \dots, n\}$.
Proof: We first prove by induction on $n$ that there can be no injective function $\{1, \dots, n+1\} \to \{1,\dots,n\}$.
Base case: For $n=1$ we only have the constant function $f: \{1,2\} \to \{2\}$, given by $f(1) = 1$ and $f(2) = 1$, which is not injective.
Inductive step: We assume that there is no injective function $\{1, \dots, n+1\} \to \{1,\dots,n\}$. Let $f: \{1, \dots, n+2\} \to \{1,\dots,n+1\}$ be any function and let $k=f(n+2)$. If there is a $j \in \{1,\dots,n+1\}$ with $f(j)=k=f(n+2)$, then (f) is not injective. We assume that there is no such (j).
If $k=n+1$, we consider the restricted function $g:\{1,\dots,n+1\} \to \{1,\dots,n\}, \ j \mapsto f(j)$. Based on the assumption that there is no $j \in \{1,\dots,n+1\}$ with $f(j)=k=n+1$, the function is well-defined [How is the function now well-defined? And how could $k=n+1$ anyway? Isn't the function only mapping to $\{1,\dots,n\}$?]. Because of the inductive step, we know that $g$ cannot be injective. Therefore, there exists $i \neq j \in \{1, \dots, n+1\}$, where $f(i)=f(j)=g(i)=g(j)$ [I understand that because $g$ is injective, there must exist $g(i)=g(j)$. But why does that also apply to $f(i)=f(j)$?].
If $k < n+1$, we define
$\sigma: \{1,\dots,n+1\} \to \{1,\dots,n+1\}, j \mapsto \begin{cases} 
    n+1 \text{ if } j = k \\
    k \text{ if } j = n+1 \\
    j \text{ if } j \neq k \text{ and } j \neq n+1
 \end{cases}$
and get a new function $F= \sigma f$, which satisfies $F(n+2)= \sigma(k) = n+1$ [What happened here? What is this function and why do we compose it like that? And how and why does it satisfy $F(n+2)= \sigma(k) = n+1$?]. We know that $F$ is not injective [why?]. But because $\sigma$ is bijective [why?] and $f= \sigma \circ F$, $f$ is also not injective [again, why?].
This concludes the proof. We have now proven that for a natural number $n \geqslant 1$, there is no Injection from $\{1, \dots, n+1\}$ to $1, \dots, n$. For $m > n \geqslant 1$ we can conclude that there is no Injection from $\{1, \dots, m\}$ to $\{1, \dots, n\}$ [Is it because we can repeat the above steps?].
 A: I was going to write a step-by-step explanation of the proof, answering your questions, but then I decided that the real issue here is that the proof is poorly presented. It does not explain what it is doing well, so the reader is left to work it out from context. And for those without much experience, this is very difficult to do.
So instead, I am going to rewrite the inductive step of the proof in what I think is a more clear description. The proof itself is still the same. I'm just trying to be more clear as to what it is doing, and why.
To make the notation a little easier, let me define for integers $i \le j$,
$$\langle i, j\rangle := \{i, i + 1, \dots, j\}$$

Inductive step: We assume that there is no injective function $\langle 1, n+1\rangle \to \langle 1, n\rangle$.
Let $f : \langle 1, n+2\rangle \to \langle 1, n+1\rangle$ be any function. Divide the proof into four cases:

*

*There is a $j < n+2$ with $f(j) = f(n+2)$.

*There exist $j \ne i$ with $f(j) = n+1$ and $f(i) = n+1$

*For all $j < n+2, f(j) < n+1$.

*All functions not satisfying the other three cases.

These four cases cover all possible $f$.
Case 1 is trivial. Since $j \ne n+2$ but $f(j) = f(n+2)$, $f$ is not injective.
Case 2 is also trivial. $f(j) = f(i)$ with $j \ne i$, so $f$ is not injective.
Case 3: Because for all $j \in \langle 1,n+1\rangle, f(j) < n+1$, we can restrict both the domain and codomain of $f$ to define a new function:
$$g : \langle 1, n+1\rangle \to \langle 1, n\rangle : j \mapsto f(j)$$
(Note that instead of just defining $g$, then showing why $g$ is "well-defined", I chose to justify the definition before giving it. $f$ can take on $n+1$ as a value, $g$ cannot, so we have to know that $f(j) \ne n+1$ for any $j$ in the domain of $g$.)
By the induction hypothesis, $g$ cannot be injective. So there is some $i,j \in \langle 1, n+1\rangle$ with $i \ne j$ and $g(i) = g(j)$. But $g$ is just the restriction of $f$, so $f(i) = g(i), f(j) = g(j)$ and therefore $f(i) = f(j)$. $f$ is not injective.
Case 4:
Because case $3$ is false, there is some $j < n+2$ with $f(j) = n+1$. Because case 2 is false, there is no other $i$ with $f(i) = n+1$. In particular $f(n+2) < n+1$.
Define the mapping $$\sigma : \langle 1, n+1\rangle \to \langle 1, n+1\rangle : i \mapsto \begin{cases}
i, & i \ne n+1 \text{ and } i \ne f(n+2)\\
n+1, & i = f(n+2)\\
f(n+2), & i = n+1
\end{cases}$$
$\sigma$ flips $f(n+2)$ and $n+1$ while leaving the other numbers unchanged. $\sigma$ is a bijection. (You asked about this, but quite frankly, you should try harder to see it yourself. The definition of $\sigma$ is right there, and it is simple to show.) So it has an inverse $\sigma^{-1}$.
Define a function $F = \sigma f$. Then

*

*For all $i < n+2$, if $i \ne j$ then $f(i) \ne n+1$, and because case 1 is false, $f(i) \ne f(n+2)$. So $F(i) = \sigma(f(i)) = f(i)$. In particular $F(i) < n+1$.

*$F(j) = \sigma(f(j)) = \sigma(n+1) = f(n+2) < n+1$.

So $F : \langle 1, n+2\rangle \to \langle 1, n+1\rangle$ is a function such that for all $i < n+2, F(i) < n+1$. Thus by Case 3 with $F$ playing the role of $f$, $F$ cannot be injective.
So there is some $i, k \in \langle 1, n+2\rangle$ with $i \ne k$, but $F(i) = F(k)$. But then $f(i) = \sigma^{-1}(F(i)) =  \sigma^{-1}(F(k)) = f(k)$, and therefore $f$ is not injective either.
In all cases, $f$ cannot be injective.
