Functional equation

Obviously, the function f(n)=n satisfy the condition. We will prove that it is the only possible case.

Let n be a natural number. Suppose f(k)=n. We will show that k=n. This is equivalent to say that f(n)=n for all n.

Firstly, we prove k=<n.

For the case n=1. If k=>2, then

1=f(k)>f(f(k-1)), hence f(f(k-1))=0, which is impossible since the range of f is N.

Therefore we must have k=1.

Use MI. Suppose the statement holds for all cases f(k)=1,...,n-1. Suppose f(k)=n. Then either k=1=<n, or we will have

n=f(k)>f(f(k-1)), hence f(f(k-1))=<n-1. Let f(f(k-1))=r=<n-1, by induction hypothesis, f(k-1)=<r. By induction hypothesis again, k-1=<r. Therefore k=<r+1=<n.

So by MI, we have proven that if f(k)=n, then k=<n. This is equivalent to say that f(k)=>k for all k.

Next we prove that k=>n. This is equivalent to say that f(k)=<k for all k. We will prove that latter statement.

To show this, suppose on the contrary that f(k)=n>k for some k. Note that n=>k+1. Consider the sequence

f(k+1),..., f(n).

Since f(n)=f(f(k))<f(k+1), we cannot have n=k+1, and the sequence is NOT monotonic increasing. Hence there must exist two consecutive terms in the sequence such that

f(r+1)<f(r). On the other hand, we have f(r+1)>f(f(r)). Hence we have

f(f(r))<f(r+1)<f(r). Write f(f(r))=s<f(r). By what we have proven in the first part, we have

f(r)=<s<f(r), which is a contradiction. Therefore we must have f(k)=<k for all k.

Combining the two parts, we have f(n)=n for all n.

這一條正是質變量變律、對立統一律、否定之否定律三大定律的具體表現。