Given that $\phi$ is an increasing map from $\{1,2,\cdots,n\}$ to itself, prove that $\phi$ has a fixed point.
My attempt (induction) :
The result holds for $n=1,2$.
Assume it true for $n$ and let $f$ be an increasing map from $\{1,2,\cdots,n+1\}$ to itself.
If $f(n+1)=n+1$ , $n+1$ is a fixed point for $f$ and we're done.
Otherwise the increasingness of $f$ implies that $ f(k) \le f(n+1) \le n$ for all $k \in \{1,2,\cdots,n\}$
Thus the function $\tilde{f}$ defined on $\{1,2,\cdots,n\}$ to itself by $\tilde{f}(k)=f(k)$ is well defined. Moreover, it's also increasing since $f$ is. We then can apply the induction hypothesis to $\tilde{f}$ to see that it has a fixed point.
That terminates the proof.
Is the proof correct and sound.
Thanks.