Prove that no function exists from $\mathbb{N}$ to $\mathbb{N}$ such that $f(n) \gt f(n+1)$

Question

The recursion theorem says that if we have a function called $G$ from $A \times \mathbb{N} \to A$ there exists a function called $f$ from $\mathbb{N} \to A$ such that $f(0)$ equals to one of the members of $A$ and $f(n+1)=g(f(n),n)...$ so how can we prove that if $A$ is equal to the set of natural numbers , there is no function such that $f(n)\gt f(n+1)$.

Answer 1

If such a function $f\colon \mathbb{N} \rightarrow \mathbb{N}$ exists, consider the image set of it \begin{equation*} Im(f) = \{ f(n) \}_{n \in \mathbb{N}} \end{equation*} Which is a subset of $\mathbb{N}$, so there exists an element there $f(n_0)$ which is the smallest, i.e. $f(n_0) \leq f(n)$ for all $n \in \mathbb{N}$. But then \begin{equation*} f(n_0) > f(n_0+1) \end{equation*} contradicting the minimality of $f(n_0)$. So such a function cannot exist.

Answer 2

There is no infinite descending sequence of natural numbers. That is, there is no sequence of natural numbers $$ n_0 > n_1 > n_2 > n_3 \ldots .$$ Intuitively, that fact is obvious: $n_0$ is some finite number, and you can't start at some finite number and descend infinitely. More formally, you can show the following by induction:

For all natural numbers $n_0$, $n_0$ can't start an infinite descending sequence.

Base case: $n_0 = 0$. There is no natural number less than 0, so there is no possible choice of $n_1 < n_0$ to continue the sequence.

Inductive case: assume we know that, for all $n < n_0$, $n$ can't start an infinite descending sequence. Then $n_0$ can't start one either: if there were a sequence $n_0 > n_1 > n_2 > \ldots$, we would have an infinite descending sequence $n_1 > n_2 > n_3 > \ldots$ starting at $n_1 < n_0,$ contradicting the hypothesis.

We've now shown the claim. From here, we see that you can't have a function $f : \mathbb{N} \to \mathbb{N}$ such that $f(n) > f(n+1)$, since it would give a sequence $$f(0) > f(1) > f(2) > f(3) > \ldots,$$ which we know can't happen.