# Is the set of positive rational sequences diverging to infinity countable?

I came up with a positive proof for the title's question; however, it seems very counter-intuitive to me because the set of binary sequences seems much smaller, yet is uncountable. Moreover, we can forgo positivity as a condition, but I won't for simplicity.

Perhaps I have made an elementary mistake?

Proof.

Suppose $q_n$ is a positive sequence of rationals diverging to infinity. Since it diverges there are only finitely many $q_n$ below any given $i\in\mathbb{N}$.

The set of positive rationals below $i$, $Q_i$, is countable.

The set of orderings of any finite subset of $Q_i$ is finite; in turn, for any finite subset of $Q_i$, the set of all its finite sequences is finite. The number of subsets of $Q_i$ of a given size is countable; as is the number of sizes. In turn, the set of all ordered finite subsets of $Q_i$, $\tilde{Q}_i$ is countable.

Then the set $\bigcup_{i\in\mathbb{N}} \tilde{Q}_i$ is countable, and the set of positive rational sequences diverging to infinity injects into it.

• The answer is in fact no. Your argument could be adapted to binary sequences (there are a countably finite number of different binary sequences if you only look at the first $i$ terms) but that does not make the number of infinite binary sequences countable – Henry Dec 10 '16 at 15:48
• Write a real number in $[0,1]$ as $a=.a_1a_2a_3\cdots$. Then define a sequence $A=\{1+.a_1,2+.a_1a_2,3+.a_1a_2a_3, \cdots\}$. $A$ diverges to infinity, clearly, but we can recover the real number $a$ from it easily. – lulu Dec 10 '16 at 15:51

I don't understand how the last sentence of your argument is supposed to work -- how do you clam that the set you're talking about injects into $\bigcup_i \bar Q_i$? -- but what you're trying to prove is certainly a falsehood.

You know that there are uncountably many infinite binary sequences; however, if $(b_n)$ is a infinite binary sequence, then $$c_n = n + b_n$$ is an infinite rational sequence that diverges to $+\infty$, and the mapping from $(b_n)$s to $(c_n)$s is injective, so even just there you have uncountably many different rational sequences that diverge to infinity.

• Changed "infinitely" to "uncountably" in the last sentence to emphasize meaning. – Martin Argerami Dec 10 '16 at 17:12

This is indeed incorrect. What you've shown is that the set of all finite increasing sequences of rationals is countable, which is true (and this is what your $\bigcup \tilde{Q}$ represents - each $\tilde Q$ is a set of finite sequences, so the union of the $\tilde{Q}$s is again a set of finite sequences, not a set of infinite sequences). However, in the same way that the set of finite binary sequences is countable while the set of infinite binary sequences isn't, the set of infinite increasing rational sequences (or divergent ones) is uncountable.

To see uncountability, note that there is an injection from infinite binary sequences to rational sequences diverging to infinity, as follows: given an infinite binary sequence $f$, let $S$ be the sequence of rationals given by

• $S(0)=0$,

• $S(i+1)=S(i)+f(i)+1$.

So e.g. if $f=00110101...$ then $$S=0,1,2,4,6,7,9,10,12,...$$

• Ah, thank you; I was implicitly considering the fact that each rational sequence corresponds to some ordered finite subset of each $\tilde{Q}_i$; but that's just secretly hiding an $\mathbb{N}\rightarrow\mathbb{N}$ mapping! – VF1 Dec 10 '16 at 15:54

Consider binary sequences that are not eventually zero (i.e., most of them*). This set is also uncountable. Now for such a sequence, $b$, consider its partial sums, $S(b)$:

$$b_0, b_0 + b_1, \ldots$$ where the bits are treated as integers. The result is a diverging integer sequence. It's easy to show $S$ is injective. Hence the set of diverging integer sequences contains an uncountable subset.

(*) Proving that the set $C$ of cofinitely zero sequences form a small subset of the set $E$ of all binary sequences --- i.e., the remainder $E - C$ has the same cardinality as $E$ --- is left as a small exercise.

There are many ways with which we can "decode" a binary sequence from a sequence converging to $+\infty$: for example, if $q_n$ is a sequence converging to $\infty$, consider $a_n=0$ if $q_n$ is not of the form $2^k$ for some $k\in\Bbb N$, and $a_n=1$ if there is some $k$ for which $q_n=2^k$.

Not only it is not hard to verify that this is a well-defined way to decode a sequence, note also that every binary sequence can be obtained like this. Namely, this is a surjective map from the rational sequences converging to $+\infty$, onto the infinite binary sequences.

But perhaps what is simplest is to take one injective sequence, for example $1,2,3,4,\ldots$, and then consider all of its subsequences. How many of these are which diverge to $+\infty$?

This answer is not to prove or disprove your proof, it is to show another perspective on the question.

A simple proof of this set's uncountability is Cantor's diagonal method.

Suppose we have the list of positive rational sequences diverging to infinity, and the first three are:

$1,2,3,4,5,6,7,8,9,10,\cdots$

$2,4,6,8,10,12,14,16,18,20,\cdots$

$4.5,6.37,9.3333...,20,47.84,28.297,56.001,87.01,92,1000,\cdots$

We can create a new sequence that differ at least in one term terms with any of the ones in the list. Given the ones here, an option would be

$2,5,10,\cdots$

There are infinitly countably many numbers in a sequence diverging to infinity. There are infinitly countable many rational numbers. Therefore there are infinitly many series not equal from the ones in the list. Therefore, the list is incomplete and will always be; so it can't exist.

• I'm no mathematician nor natural english speaker, so sorry for any mistake and any criticism is welcome. – Massimiliano Tron Dec 11 '16 at 3:20