A nonidentity permutation $\sigma$ satisfies $\sigma(i)<i$ for some $i$

Question

If a permutation $\sigma: N\to N$ is not the identity, prove that there exists an $i \in \{1,...,n\} $ such that $\sigma(i)<i$.

Answer 1

We prove that if $\sigma(i)\geq i$ for all $i$, then $\sigma$ is the identity. We do this by induction on $n$. Clearly it is true if $n=1$. Otherwise, note that $\sigma(n)\geq n$, hence $\sigma(n)=n$ since $n$ is the largest element. Then $\sigma$ restricted to $[n-1]$ is a permutation with the same property on the smaller set, hence is the identity.

Answer 2

Suppose the contrary, that $\sigma (i)\ge i\,,\forall i$. Then there is a minimum $\hat i$ for which $\sigma (\hat i)\gt\hat i$. Now the only remaining choices for $\sigma ^{-1}(\hat i)$ are all greater than $\hat i$. So if $\sigma (k)=\hat i$, then $k\gt\sigma (k)$.