# How many monotonically increasing sequences of natural numbers?

Could you please offer a straightforward idea to demonstrate that the set of monotonically increasing sequences of natural numbers is indeed uncountable?

I was asked to show the cardinality of this set but the best I can do right now is the following

1. Monotonically increasing sequences are equivalent to infinite subsets (trivial).
2. Number of finite subsets is countable (by mapping to rational numbers within $[0;1]$ like $\{4,5,6\} \rightarrow 1/2^4+1/2^5+1/2^6$).
3. Number of all subsets is uncountable (by similarly mapping to all numbers within $[0;1]$).
4. Hence the number of infinite subsets is uncountable.

However working with a couple of proofs seems cumbersome and is hopefully redundant for the original task.

-

If $\sigma=\langle n_k:k\in\Bbb N\rangle$ is monotonically non-decreasing, let $\hat\sigma=\langle n_{k+1}-n_k:k\in\Bbb N\rangle$; then $\hat\sigma$ is an arbitrary sequence in $\Bbb N$. (My $\Bbb N$ includes $0$.) (If you meant $\sigma$ to be strictly increasing, replace $n_{k+1}-n_k$ by $n_{k+1}-n_k-1$.) The map $\sigma\mapsto\hat\sigma$ is a bijection between the set of monotonically non-decreasing sequences in $\Bbb N$ and the set of all sequences in $\Bbb N$. If you know that the latter set is uncountable, you’re done. If not, observe that it contains the set of sequences of zeroes and ones, which are just the indicator (or characteristic) functions of subsets of $\Bbb N$, so there are uncountably many of them.

-

The following proof uses the monotonic sequences $${\bf a}=(a_1,a_2,a_3,\ldots)$$ themselves. Assume $$\phi:\quad k\mapsto{\bf a}^{(k)}\qquad(k\geq1)$$ is a counting of all these sequences. Let $s_0:=0$ and define a new sequence ${\bf s}=(s_n)_{n\geq1}$ recursively as follows: $$s_n:=\min\bigl\{ k\>\bigm|\> k>s_{n-1}\ \wedge\ k\ne a_n^{(n)}\bigr\}\ .$$ Then the sequence ${\bf s}$ is monotonically increasing and $\ne{\bf a}^{(k)}$ for all $k\geq1$.

-

Hint: Set up a bijection between $(a_n)$ and $(\sum_0^n a_i)$.

-
Won't this result in yet another monotonically increasing sequence? – Pranasas Aug 6 '13 at 13:02
@Pranasas This will result in a monotonically increasing sequence starting from an arbitrary sequence $(a_n)$. This is essentially the reverse map to Brian's answer. – ronno Aug 6 '13 at 14:04

Hint:

bijection :

for each sequence $$A: a_1,a_2,a_3,a_4, ...$$

construct value

$$B = a_1 + \cfrac{1}{(a_2-a_1)+\cfrac{1}{(a_3-a_2)+\cfrac{1}{(a_4-a_3) + ...}}}.$$

Set of values $B$ is the set of all irrational numbers, which are greater than 1 (set is uncountable).

-
I guess it would be precisely like that for monotonically increasing integer sequences. Since my sequences consist of natural numbers maybe $B$ values are within the set $[1;+\infty]\backslash \mathbb{Q}$ ? – Pranasas Aug 6 '13 at 13:07
@Pranasas, yes, you are right. Exactly as you wrote. I'll correct my answer. – Oleg567 Aug 6 '13 at 13:09
Other (similar) bijection: $B = \cfrac{1}{a_1 + \cfrac{1}{(a_2-a_1)+\cfrac{1}{(a_3-a_2)+\cfrac{1}{(a_4-a_3) + ...}}}}$ - set of all irrational numbers in $(0;1)$. – Oleg567 Aug 6 '13 at 13:14

Inside the set of increasing sequences, you have the set of sequences where $a_n\in \{2n,2n+1\}$ for all $n$. But this set is easily identified with the set of sequences with values in $\{0,1\}$, which can be identified with the powerset of $\mathbb{N}$, which shows that the full set of increasing sequences is uncountable.

-

Given a sequence $\langle n_i\mid i\in\Bbb N\rangle$, we can consider the set $\{n_i\mid i\in\Bbb N\}$. The map from sequence to range is a bijection between the infinite strictly increasing sequences, and infinite subset of $\Bbb N$ -- the inverse is simply enumerating the subset using the usual order of the natural numbers.
It is not hard to show that there are uncountably many infinite subsets of $\Bbb N$. The reason is that we can prove that there is only a countable number of finite ones, and the power set is uncountable. The union of two countable sets is countable, so it cannot be the case that the infinite subsets of $\Bbb N$ is a countable set as well.