Proving the set of the strictly increasing sequences of natural numbers is not enumerable.

As other answers note, there are lots of fancy ways to prove this. But we can always go back to the basics. A straightforward diagonalization proof-by-contradiction suffices. Suppose there is such an enumeration. Maybe this is it:

1 --> 1, 2, 3, 5, ...
2 --> 4, 5, 7, 100, ...
3 --> 1, 2, 3, 8, ...
4 --> 2, 4, 5, 6, ...

Now take the first number of sequence one, and add one to it. That's our first number: 2.

Now take the second number of sequence two - 5 - and the number from the previous step - 2. Take the larger and add one: 6.

Now take the third number of sequence three - 3 - and the number from the previous step - 6. Take the larger and add one: 7.

Now take the fourth number of sequence four - 6 - and the number from the previous step - 7. Take the larger and add one: 8.

Keep doing that and construct the sequence of monotone increasing naturals:

2, 6, 7, 8, ...

By assumption, this sequence is in our enumeration, but where can it be? It cannot be at spot n for any n because by its construction the nth element of this sequence is larger than the element at spot n of the nth sequence.

That's a contradiction, and therefore there cannot be any such enumeration.

Map any strictly increasing sequence $(a_n)$ to a sequence $(b_n)$ of its increments modulo $2$: $$\{0,1\}\ni b_n \equiv a_{n+1}-a_n \pmod 2$$ This is, of course, not bijective or even injective, but it is surjective mapping, hence the cardinality of the set of $a$ sequences is not less than that of $b$ sequences.

And the latter is known to be strictly greater than $|\mathbb N|$ because $b$ are binary sequences, which are one-to-one representation of $2^\mathbb N$. They can also be bijectively mapped onto $\mathbb R$.

We can define a very simple injection from the real numbers in the interval $[1,10)$ to your set by mapping $x \in [1,10)$ to the sequence $$\lfloor x \rfloor, \lfloor 10x \rfloor, \lfloor 100x \rfloor, \lfloor 1000x \rfloor, \dots.$$ For example, $\pi$ would map to the sequence $$3, 31, 314, 3141, 31415, 314159, \dots.$$ There is some straightforward checking to do that

• the resulting sequence is increasing, and
• two different real numbers map to different sequences.

Once we've done that, this argument shows that the strictly increasing sequences have at least the cardinality of the set $[1,10)$, which is continuum.