Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

6 Answers 6

up vote 6 down vote accepted

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.

share|improve this answer

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$.

share|improve this answer

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

share|improve this answer
    
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).

share|improve this answer
    
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.

share|improve this answer

Your argument is generally correct.

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.

You may need to slightly add some details here and there. But generally this proof is straightforward and simple. The details from the second part are often assumed to be true from previously proved theorems, exercises, and otherwise.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.