Is the set of decreasing functions from $\Bbb N$ to $\Bbb N$ countable? I want to prove the set of decreasing functions from $\Bbb N$ to $\Bbb N$ is countable.
I considered a decreasing function, $f$, with a least element, $n$, and let $x$ be the smallest number such that $f(x)=n$.
Is it ok that since $f$ is decreasing that for all $y>x$, $f(y)=f(x)=n$? 
By doing so $i$ can then show non-increasing functions can be defined by the set $\{f(1),\dotsc,f(x)\}$ and I think I can do the rest.
 A: Define
$$S_N:=\{f:\mathbb{N}\to\mathbb{N}\;|\; f \text{ is non-increasing and } f(1)\leq N\}$$
Then, your set is
$$S=\bigcup_{N=1}^\infty S_N$$
Since a union of countable sets is countable, it suffices to show that each $S_N$ is countable. Now, argue by induction on $N$.
ADDED (the induction argument): $S_1$ is countable since its only element is the function $f(n)=1,\forall n\in\mathbb{N}$. Now suppose $S_N$ is countable. A function in $S_{N+1}$ is either the constant function $f(n)=N+1,\forall n\in\mathbb{N}$, or it achieves some number $m=f(n_0)\leq N$ at some point $n_0\in\mathbb{N}$. Now after this $n_0$, the function can be considered as a function of $S_N$. Hence, to give a function in $S_{N+1}$ is to give an integer $n_0$ and a function in $S_{N}$. That is, $S_{N+1}$ is in bijection with $\mathbb{N}\times S_{N}$, which is countable since $S_N$ is countable (by the induction hypothesis). Hence, $S_{N+1}$ is countable.
A: HINT: Every [strictly] decreasing sequence of natural numbers is finite. Observe that a decreasing function is fully determined by a finite set of natural numbers, and conclude the countability.
A: Hint $\ $ By coding a decreasing sequence by a finite sequence of naturals (e.g. list the finite number of places where it changes value) the set is a subset of $\,\bigcup_{\,k=1}^{\,\infty}\! \Bbb N^k,$ a countable union of countables.
A: Yes; the number of  non-decreasing functions $f: \mathbb N \rightarrow \mathbb N$  is countable:
0)We know that these functions must be eventually constant, since f(1) is a finite value, and there are infinitely many values {$f(2),f(3),....$}. Say the functions is constant after $f(k)$.
1)Turn a function into a decimal string, by {$f(1),f(2),..,f(k),f(k),..$} $\rightarrow 0.f(1)f(2)....f(k)f(k)....$
2)Split the decimal image into the sum: $$0.f(1)f(2)...f(k-1)0000...0 +0.0000f(k)f(k)...f(k)...$$
3)Each of the terms of the sum is a Rational number, so the string represents a Rational number.
4)The collection then injects into the Rationals. But we know the set of  constant functions $f(n)=k; k=1,2,3,...$ is also non-decreasing. So the collection is countably-infinite.

Extended Explanation:
The set of non-decreasing functions is countable because every string $f(1),f(2),...,f(n)$ , when seen as a decimal expansion $0.f(1)f(2)....$, is a Rational  number. This is because the sequence {$f(1),f(2),...$} must be eventually-constant, i.e., there is an integer $k$ after which $f(k)=f(k+1)=....=f(k+n)=.....$. 
So we have the assignment: $$ f(1),f(2),...,f(n),... \rightarrow 0.f(1)f(2)....f(n).. ..$$
And the claim is that the expression on the right, seen as a Real number, is Rational.
The proof of the claim is that , since the string is eventually-constant, say after the $k$-th spot, you can write the string as:
$\frac {.f(1).....f(k-1)}{10^{k-1}} + 0.00000000.f(k)f(k)....f(k)....=$ (where the first $f(k)$ starts at the $k-$th spot), which is a sum of Rationals, and it is then a Rational. So the (image) of the sequence of non-decreasing maps is a subset of the Rationals. EDIT: What we do is, if $f(k)$ has $n$ digits, we turn each digit into a term in the decimal expansion, e.g., if $f(x)=753$ , then $753 \rightarrow 0.00000753753...753....$
Note that the collections is infinite, since the constant sequence $f(n)=k; k=1,2,3,...$ does the job, i.e., it is non-decreasing.
A: Note for nerds: the following avoids the axiom of choice, but is not intuitionistically valid.
Let $f\colon \Bbb N \to \Bbb N$ be a decreasing function, where $\Bbb N = \{0,1,\dotsc\}$ (I am including $0$).
Let $n-1$ be the smallest number at which $f$ takes on its smallest value. Then we can represent $f$ as a finite sequence, an $n$-tuple, $f(0),f(1),\dotsc,f(n-1)$. The set of all such representations is then a subset of the set $\Bbb N^{<\omega}$ of tuples of natural numbers.
We want to show, then, that $T:=\Bbb N^{<\omega}$ is countable. Since a subset of a countable set is countable, this will prove the theorem.
Note for nerds: what remains is entirely constructive, as far as I can see.
There are many classic bijections from $\Bbb N\times \Bbb N$ to $\Bbb N$. Pick your favorite and call it $p_2$. For each $n\ge 2$, let $p_{n+1}\colon \Bbb N^n\to n$ be defined by $p_{n+1}(x_0,x_1,\dots,x_n)=p_2(x_0,p_n(x_1,\dots,x_n))$. For completeness, let $p_1$ be the identity function on $\Bbb N$. By induction, you can easily see that $p_n$ is a bijection from $\Bbb N^n$ to $\Bbb N$ for each $n$.
Now that we have all these $p_n$s, let's put them together. For each tuple $(x_0,\dots,x_{n-1})$, let $q(x_0,\dots,x_{n-1})=p_2(n,p_n(x_0,\dots,x_{n-1}))$. That is, we're using $p_2$ to bundle up the length of the tuple with the result of applying $p_n$ to that tuple. But then $q$ is exactly what we're looking for: a bijection from $\Bbb N^{<\omega}$ to $\Bbb N$.
