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

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.

• The horrible term "non-increasing" could either mean "not increasing", as logic would suggest, or (more likely) weakly decreasing. The answer to the question depends on this distinction, so it might be useful to be unambiguous here. Feb 9, 2015 at 14:58
• @MarcvanLeeuwen: good comment, to me a 'non-increasing sequence' is a sequence that is not increasing. Feb 9, 2015 at 15:00
• Feb 9, 2015 at 17:05
• @AlexH. Unfortunately most of the time you'll be wrong by interpreting properly, (i.e., the way you do). Feb 9, 2015 at 17:06
• @GitGud See also why do we use 'non-increasing' instead of decreasing? (in fact I've now flagged the other one as a duplicate) Feb 9, 2015 at 17:28

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.

• Any sequence of natural numbers contains a minimal element, it doesn't have to be non-increasing. Feb 9, 2015 at 14:02
• @dtldarek: Very true - the mental image was, of course, that this is so-to-speak the "limit point" of the sequence. Feb 9, 2015 at 18:56
• I didn't use functions but I did use combinatorics when looking at different kinds of non-increasing sequences so as to show that even when the aforementioned sequence is infinite, it might have countable number of elements, but once you determine the first, you only have a finite number of elements to work with. i.e, you will make $\aleph_0$ choices but every choice is finite. Thus applying the rule of product it cannot exceed $\aleph_0$... Feb 9, 2015 at 20:17

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.

• This is how I would do it, though I might use words like injection or one-to-one. Feb 9, 2015 at 13:20

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.

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$.

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$.