Decreasing functions $f:\mathbb{N} \rightarrow \mathbb{N}$ Let $P=\{f:\mathbb{N} \rightarrow \mathbb{N}; f(i+1)\leq f(i) \ \forall \ i \in \mathbb{N}\}.$
I need to show 2 elements of $P$ and prove that $P$ is countable (or not).
I think that $P$ only have constant functions, and if this is right, i can prove that $P$ is countable. There is some counter-example for this?
 A: This answer builds on a nice principle outlined in a post by @Riemann'sPointyNose that has been deleted because of an argumentation gap, which I believe is closed in the following.
The idea is to assign to any function $f: \mathbb{N}\to\mathbb{N}$ a real number in such a way that every $f\in P$ is mapped to a rational number.
Let for example $f(1) = 245$, $f(2) = 123$, $f(3) = 10$, $f(4) = 4$, $f(5) = 4$, ...
Then concatenate the decimal representations to get an infinite string
$$\color{red}{2451231044\ldots}$$
However we cannot uniquely reconstruct the function $f$ from this string because we don't know where the boundaries of the numbers are.
To fix this, we interleave it with another sequence consisting of 0's and 1's, where we put a 1 whenever a "new number begins". That is:
$$\color{red}{2}\color{blue}{0}\color{red}{4}\color{blue}{0}\color{red}{5}\color{blue}{1}\color{red}{1}\color{blue}{0}\color{red}{2}\color{blue}{0}\color{red}{3}\color{blue}{1}\color{red}{1}\color{blue}{0}\color{red}{0}\color{blue}{1}\color{red}{4}\color{blue}{1}\color{red}{4}\color{blue}{1}\ldots$$
This enables us to uniquely reconstruct the function $f$.
Now note that if $f$ becomes constant eventually, the resulting string will be periodic eventually.
Hence, if we regard it as a decimal expansion of a number in $[0,1]$, the number will be rational.
Since every function in $P$ becomes constant eventually, this gives us an injective mapping
$$P \to \mathbb{Q}$$
and $P$ must therefore be countable.
A: It is not true that every $f\in P$ is constant. Take, say,$$f(n)=\begin{cases}2&\text{ if }n=1\\1&\text{ otherwise.}\end{cases}$$However, it is true that, if $f\in P$, then there is some $N\in\Bbb N$ such that $n\geqslant N\implies f(n)=f(N)$. And it is not hard to deduce from this that $P$ is indeed countable.
A: I'll leave the rigorous formulations to you, here are the main ideas: (Note also that I use $0\not\in\mathbb N$; all my arguments have to be slightly adapted if you want to use $0\in\mathbb N$, but the ideas are exactly the same).

First we show that every $f\in P$ is eventually constant by contradiction. The intuition is that any non-eventually constant $f\in P$ has to go down by at least $1$ infinitely often, but $f$ can't go down by $1$ more than $f(1)$ times.
Expressed rigorously: If there exists a $f\in P$ that is not eventually constant, then there exist infinitely many $n_1<n_2<n_3<\dots$ in $\mathbb N$ such that $f(n_i+1)\le f(n_i)-1$ for every $i\in\mathbb N$.
So
\begin{split}
&f(n_{f(1)}+1)&\le &f(n_{f(1)})-1 \\
\le &f(n_{f(1)-1}+1)-1 
&\le &f(n_{f(1)-1})-2 \\
\le &f(n_{f(1)-2}+1)-2 &\le &f(n_{f(1)-2})-3 \\
\le &\dots &\le &\dots \\
\le &f(n_{f(1)-(f(1)-1)}+1)-(f(1)-1)&\le & f(n_{f(1)-(f(1)-1)})-f(1), \\
\end{split}
but $f(n_{f(1)-(f(1)-1)})-f(1)=f(n_1)-f(1)\le 0$, which means that $f(n_{f(1)}+1)\le0$ which is a contradiction to $f(n_{f(1)}+1)\in\mathbb N$.

Now to show that $P$ is countable, you might want to use that the set of all eventually constant functions $f:\mathbb N\to\mathbb N$ is bijective to $\bigcup_{k\in\mathbb N} \mathbb N^k$.
