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 --&gt; 1, 2, 3, 5, ...
2 --&gt; 4, 5, 7, 100, ...
3 --&gt; 1, 2, 3, 8, ...
4 --&gt; 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.
Let $\{{s_i}_j\}$ be a countable list of strictly increasing sequences; define $\{c_i\}$ via $c_i = \max (c_{i-1}, {s_i}_i)+1$ and .... presto, Cantor!

But it  could be simpler (depending on one's idea of simple) to reduce to things we already know are uncountable.

For simplicity, we can consider the sequence of differences between terms and not have to worry about the terms being increasing. i.e $a_{i+1} &gt; a_i$ so $b_{i+1} = a_{i+1} - a_i &gt; 0$ so $b_{i+1} \in \mathbb N$ and if $b_0 = a_0$. We have a one-to-one correspondence between $\{$ all increasing sequence of natural numbers $\}$ and $\{$ all sequences of natural numbers $\}$.

$\{$ all sequences of natural numbers $\} \supset \{$ all sequences of 1.... 10$\} \cong \{$ all sequences of 0....9 $\} \cong \{$all real numbers between 0 and 1$\}$ which is uncountable.