How many non-increasing sequences are there over the natural numbers?

Question

How many non-increasing sequences are there over the natural numbers? By splitting it to categories, I sort of got it has to be $\aleph_0$. Nevertheless, I haven't seen such a question and therefore I don't know if I am even correct in my result. I would appreciate your help.

Answer 1

You are correct.

Since the sequences are not increasing, they contain a minimal element. By adding $1$ to every entry, you have a bijection between the sequences with minimal element $n$ and those with minimal element $n+1$. It is therefore sufficient to show that the sequences with minimal element $0$ are countable, because the countable union of countable sets is countable. These sequences are sequences of finite length (i.e. the index of the last nonzero entry), and by the same argument as above it is sufficient to show that the sequences of a fixed length $\ell$ form a countable set. But in fact, the set of sequences of length $\ell$ is just $\mathbb N^\ell$, which is countable.

Answer 2

Let $(a_k)_k$ be such a sequence and let $m=\inf\{\,a_k:k\in\mathbb N\,\}$. Then almost all $a_k$ equal $m$, and we can "encode" the infinite sequence by writing down only the initial terms until the first occurrence of $m$. This way, the set of nonincreasing sequences can be viewed as subset of the set of finite sequences, which is countable.

Answer 3

Call a sequence $(u_1,u_2,\ldots)$ $n$-bounded if

• $u_1 \le n$, and
• for all $m > n, u_m = u_n$.

Then all non-increasing sequences are $n$-bounded for some $n$, and for any $n$, the number of $n$-bounded sequences is finite. So the number of non-increasing sequences is countable.

Answer 4

To a weakly decreasing sequence $a=(a_n)_{n\in\Bbb N}$ one can associate a function $f(a):\Bbb N\to\Bbb N\cup\{\omega\}$ mapping $m\mapsto\#\{\, n\in\Bbb N\mid a_n>m\,\}$. One can recover* $a$ from $f(a)$, and $f(a)$ takes only finitely many nonzero values, so the number of possibilities for $f(a)$ are countable. (In fact $f$ establishes a bijection to the set of weakly decreasing functions $\Bbb N\to\Bbb N\cup\{\omega\}$ of finite support.)

*One has $a_n=\#\{ \,m\in\Bbb N \mid f(m)>n\,\}$ for all $n$, considering that $0\in\Bbb N$.

Answer 5

In order to fix ideas denote such a sequence by ${\bf x}=(x_0,x_1,x_2,\ldots)$ with $x_0\geq x_1\geq \ldots\geq0$. Note that only finitely many differences $x_{k-1}-x_k$ are $\geq1$. Let $S$ be the set of all these sequences.

Let $(p_k)_{k\geq1}$ be the sequence of prime numbers. Then $$\phi:\quad S\to{\mathbb N}_{\geq1}, \qquad{\bf x}\mapsto 2^{x_0} \>\prod_{k=1}^\infty p_k^{\>x_{k-1}-x_k}$$ is injective. This proves $\#(S)=\aleph_0$.