17
$\begingroup$

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.

$\endgroup$
14
  • 5
    $\begingroup$ Are "enumerable" and "denumerable" both synonyms for "countable"? I've heard/read the latter before, but not the former. $\endgroup$ Sep 22, 2017 at 1:48
  • $\begingroup$ Have you tried binary strings with diagonal argument. Like $$1000...$$ $$01000...$$ $$11000...$$ $$001...$$ then the diagonal $1100...$ isn't in this infinite list type proof, by the name of cantors something or other. $\endgroup$ Sep 22, 2017 at 14:40
  • 1
    $\begingroup$ @marshalcraft The diagonalization argument does not give a method to find all sequences. That is the point of the diagonalization argument. $\endgroup$ Sep 22, 2017 at 22:35
  • 1
    $\begingroup$ Possible duplicate of Is the power set of the natural numbers countable? $\endgroup$ Sep 23, 2017 at 13:17
  • 1
    $\begingroup$ @marshalcraft Isn't the set of strictly increasing sequences of natural numbers a proper subset of the power set of natural numbers? Doesn't that mean the proof in the accepted answer in the candidate duplicate doesn't answer this question? $\endgroup$ Sep 23, 2017 at 18:26

13 Answers 13

54
$\begingroup$

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.

$\endgroup$
4
  • 7
    $\begingroup$ Or: if the diagonal elements are $d_1$, $d_2$, \ldots, then define $a_n = \max(d_1,\ldots,d_n) + n$. Then $(a_n)$ is a strictly increasing sequence and $a_n \ne d_n$ for all $n$. $\endgroup$
    – user133281
    Sep 22, 2017 at 3:21
  • 2
    $\begingroup$ @user133281 Thanks. I had a hard time deciphering the rule from the strange numbers in the text. I think that should be added to the answer. $\endgroup$
    – JiK
    Sep 22, 2017 at 11:47
  • $\begingroup$ Your answer was really helpful, thank you for your help! $\endgroup$
    – Iorpim
    Sep 22, 2017 at 17:22
  • $\begingroup$ @Iorpim: You're welcome! The key thing here is to remember that for these sorts of problems you can almost always just go back to a fundamental technique, and explain it in simple terms without a lot of jargon. $\endgroup$ Sep 22, 2017 at 17:25
24
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Very nice idea! In the same spirit: take number in $(0,1)$, with the decimal expansion $0,a_1a_2 a_3 \ldots$, then your sequence is $a_1$, $a_2a_1$, $a_3a_2a_1$, $\ldots$. But in fact it's similar to other ideas presented here. $\endgroup$
    – orangeskid
    Sep 22, 2017 at 16:37
  • $\begingroup$ @orangeskid You have to be careful with variants of this construction: your map doesn't always work, sending $\frac{\sqrt2}{2}$ (for example) to $7, 7, 707, 1707, \dots$. Of course, there are ways to fix this, but we lose much of the simplicity that way. $\endgroup$ Sep 23, 2017 at 16:51
  • $\begingroup$ Oh I see, one can have some zeroes..,. Oops! $\endgroup$
    – orangeskid
    Sep 23, 2017 at 17:16
21
$\begingroup$

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

$\endgroup$
13
$\begingroup$

The map from $\{0,1\}^{\mathbb N}$ into the set of strictly increasing sequences of natural numbers given by

$$(a_n) \to (1+a_1,3+a_2, 5+a_3,7+a_4, \dots)$$

is injective. Since $\{0,1\}^{\mathbb N}$ is uncountable, we're done.

$\endgroup$
2
  • 3
    $\begingroup$ A similar, possibly a bit simpler sequence: $$(2+a_1, 4+a_2, 6+a_3, \dots 2n+a_n, \dots)$$ $\endgroup$
    – CiaPan
    Sep 22, 2017 at 5:46
  • $\begingroup$ @CiaPan Believe it or not I was just coming in to change it along those lines. I used odd integers so I'll write those in, but your answer is even simpler. Thank you. $\endgroup$
    – zhw.
    Sep 22, 2017 at 15:52
9
$\begingroup$

For any infinite subset of the natural numbers, you can list its members in increasing order, and then you have a sequence that is strictly increasing.

Moreover, if you take two distinct infinite subsets of the natural numbers, you get two different sequences. (There is some number $k$ that is in one of the subsets and not the other, and this number occurs in one sequence and not the other.)

So the number of strictly increasing sequences of natural numbers is at least as great as the number of infinite subsets of natural numbers.

$\endgroup$
1
  • $\begingroup$ Curiously, I notice that every answer to this question has exactly one downvote at this time. $\endgroup$
    – David K
    Sep 23, 2017 at 16:34
5
$\begingroup$

Given a sequence $(a_0, a_1, \ldots, )$, map it to the sequence $(a_1-a_0, a_2-a_1, \ldots)$.

The image of such map would be the sequence of all natural numbers . Indeed the map is surjective since given a sequence of natural number $(b_0, b_1, \ldots)$, we can find a preimage $(a_0, a_1, \ldots)$ which satisfy $a_0 =1$, $a_{i+1} = b_i + a_i , \forall i \geq 0$. That is the cardinality of the set of increasing sequence of natural number is at least as big as the set of sequence of natural number.

By Cantor diagonalization, we know the set of all sequence of natural number is not countable.

$\endgroup$
1
  • 2
    $\begingroup$ With a slight modification, you could even make the map bijective. $\endgroup$
    – user14972
    Sep 22, 2017 at 0:31
5
$\begingroup$

There are uncountably many subsets of $\Bbb N$, but only countably many finite subsets, hence uncountably many infinite subsets. Every strictly increasing sequence of naturals corresponds to an infinite subset of $\Bbb N$.

$\endgroup$
2
  • $\begingroup$ Consider only the strictly increasing sequences of naturals where the increase is always by one. So 1, 2, 3, ... and 2, 3, 4, ... and 3, 4, 5, ..... Each one of those corresponds to an infinite subset of the naturals, but there are countably many such subsets. Am I missing your point, or is this not a proof of the desired statement? $\endgroup$ Sep 22, 2017 at 12:34
  • 1
    $\begingroup$ @EricLippert The last sentence in the answer is written in the wrong order. The sequences and the subsets are in a direct bijection, but the answer exposes injectivity instead of surjectivity, hence the desired result doesn't follow. It should be rather said that 'every infinite subset of $\mathbb N$ corresponds to a unique strictly increasing sequence', which would imply $|\{sequences\}| \ge |\{subsets\}| \gt |\mathbb N|$, as desired. $\endgroup$
    – CiaPan
    Jun 1, 2023 at 8:17
3
$\begingroup$

Hint: Could you uniquely associate to a sequence of $1$s and $2$s a strictly increasing sequence of natural numbers?

$\endgroup$
5
  • $\begingroup$ Ok, I'm still a little lost, could you please elaborate a little further? $\endgroup$
    – Iorpim
    Sep 21, 2017 at 19:29
  • 3
    $\begingroup$ You really need to show more effort so we can help you with where you're stuck. Since initially you didn't show your thinking, I gave a fairly general (but potentially useful) hint. $\endgroup$
    – paw88789
    Sep 21, 2017 at 19:34
  • $\begingroup$ At the risk of undermining paw88789's fire, could you uniquely associated to a sequence of natural numbers then need not be increasing? $\endgroup$
    – fleablood
    Sep 22, 2017 at 16:37
  • 1
    $\begingroup$ @paw88789 Sorry, this was a helpful tip, the reason I was still stuck was my inability at the time to remember the existence of Cantor's Diagonal, remembering it pretty much solved everything. $\endgroup$
    – Iorpim
    Sep 22, 2017 at 17:18
  • 1
    $\begingroup$ I think the point of this answer was that if $a_{i+1} = a_i+b_i,$ where $a_0=1$ and each $b_i\in\{1,2\},$ then $(a_i)$ is a strictly increasing sequence of natural numbers. The sequences you can get in this way are a proper subset of the set of all strictly increasing sequences, but this subset is already uncountable and therefore so is the entire set. $\endgroup$
    – David K
    Sep 23, 2017 at 22:32
2
$\begingroup$

For a countably infinite set $F$ of strictly increasing functions from $\Bbb N$ to $\Bbb N$ let $F=\{f_n:n\in \Bbb N\}.$ Define $g:\Bbb N \to \Bbb N$ by $g(n)=1+\sum_{j=1}^n f_j(n).$

Then $g(n+1)-g(n)=f_{n+1}(n+1)+\sum_{j=1}^n (f_j(n+1)-f_j(n))>0$ so $g$ is strictly increasing.

And $g\not \in F$ because $g(n)\geq 1+f_n(n)>f_n(n)$, so $g\ne f_n$ for any $n.$

$\endgroup$
2
$\begingroup$

For $\alpha > 1$ consider the strictly increasing sequence $f_{\alpha}(n)= [n \alpha]$

The map $\alpha \mapsto f_{\alpha}(\cdot)$ is injective, since $\lim_{n\to \infty} \frac{[n\alpha]}{n} = \alpha$.

$\endgroup$
0
$\begingroup$

There are uncountable number of positive real numbers, take {An}=cn where c is a positive real number Do this with every positive numbers it is increasing and uncountable.

$\endgroup$
0
$\begingroup$

The family of all strictly increasing sequences of natural numbers, if regarded as a family of functions from naturals into naturals, is a dominating family under both pointwise and mod finite orders, so it size has to be larger than or equal to the dominating number $\mathfrak{d}$, which is a well-known uncountable cardinal invariant of the continuum.

$\endgroup$
-1
$\begingroup$

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} > a_i$ so $b_{i+1} = a_{i+1} - a_i > 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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .