Thread: Prove that the set of increasing sequences...

1. Prove that the set of increasing sequences...

Prove that the set of increasing sequences of natural numbers (n1<n2<...) is uncountable.

2. Originally Posted by jefferson_lc
Prove that the set of increasing sequences of natural numbers (n1<n2<...) is uncountable.
Suppose we can enumerate them, for example,
$\left< \boxed{4}, 5, 11, 19, 121, ... \right>$
$\left< 2, \boxed{7}, 12, 13, 99, ... \right>$
$\left< 7, 8, \boxed{9}, 10, 12, ... \right>$
$\left< 1, 2, 99, \boxed{100},222, ... \right>$
...

Define a new sequence:
$\left< 4+1,7+4,9+7,100+9, ... \right>$

I hope you can see how we defined this sequence? The first term is the boxed term +1, then the second term is the last term plus the second boxed term, and so on. This creates a new increasing sequence which is not found on this list.
(This was the diagnol argument)

EDIT: Mistake fixed.

3. Originally Posted by ThePerfectHacker
Suppose we can enumerate them, for example,
$\left< \boxed{4}, 5, 11, 19, 121, ... \right>$
$\left< 2, \boxed{7}, 12, 13, 99, ... \right>$
$\left< 7, 8, \boxed{9}, 10, 12, ... \right>$
$\left< 1, 2, 99, \boxed{100},222, ... \right>$
...

Define a new sequence:
$\left< 4+1,7+4,9+7,100+9, ... \right>$

I hope you can see how we defined this sequence? The first term is the boxed term +1, then the second term is the last term plus the second boxed term, and so on. This creates a new increasing sequence which is now found on this list.
(This was the diagnol argument)