Proving that $f(n)=n$ if $f(n+1)>f(f(n))$

Claim 1: If $f(k) = 0$ then $k =0$.

Proof: Suppose not. Then there exists $k$ such that $0 = f(k) > f(f(k-1))$, which is not possible, as $f: \mathbb{N} \mapsto \mathbb{N}$.

Claim 2: $f(0) = 0$.

Proof: Let $S = \{f(k) | k > 0\}$. Let $a$ be the smallest number in $S$. Then there exists $k >0$ such that $a = f(k) > f(f(k-1))$. But this means $f(k-1) = 0$. Thus $k=1$, and $f(0) = 0$.

Claim 3: $f(n) = n$.

Proof: Assume, for all $0 \leq m < n$, that $f(k) = m$ iff $k = m$. Now we proceed as in the proofs of Claims 1 and 2.

If $f(k) = n$, then $f(f(k-1)) < n$, which means $k-1 = f(k-1) = f(f(k-1)) < n$. So $k < n+1$, which means that $k = n$.

Let $S = \{f(k) | k > n\}$. Let $a$ be the smallest number in $S$. Thus there exists $k >n$ such that $a = f(k) > f(f(k-1))$. Therefore $f(k-1) \leq n$. But if $f(k-1) < n$, then $f(k-1) = k-1$, and so $k \leq n$. But $k>n$. Therefore, $f(k-1) = n$, and so $k= n+1$ and $f(n) = n$.