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

How would one proceed to prove this statement?

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

I've been trying to solve this for quite a while, however I don't even know where to start.

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.

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.