# Uncountability of faster-growing sequences of positive integer numbers

I found this problem but was unable to solve it. I just don't know what I'm missing. Here it is:

A sequence of positive integer numbers $\{b_i\}_{i = 0}^\infty$ is called faster growing than $\{a_i\}_{i = 0}^\infty$ if $\lim\limits_{n\to\infty}\frac{a_n}{b_n} = 0$. Let the set $H$ satisfies the following condition: for every sequence $\alpha$ there exists another sequence $\beta \in H$ such that $\beta$ is faster growing than $\alpha$. Prove that $H$ is uncountable.

I tried to find some fundamental properties of this kind of sequences but without any success. Any help would be appreciated.

-
Strictly speaking, what you've given isn't quite a definition of $H$; it's just a condition that must hold for $H$, but there are many sets of sequences that satisfy the condition. – Steven Stadnicki Feb 23 '13 at 23:33
@StevenStadnicki you are right – Peter Dimov Feb 23 '13 at 23:40

The way to prove that $H$ must be uncountable is to show that if $S$ is any countable set of sequences, there is a sequence that grows faster than every sequence in $S$.

Let $S=\{\sigma_n:n\in\Bbb N\}$ be a countable set of sequences of positive integers. For $n\in\Bbb N$ let $\sigma_n=\left\langle m^{(n)}_k:k\in\Bbb N\right\rangle$; the superscripts are just labels to identify to which sequence a term belongs, not exponents. Now construct a new sequence $\sigma=\langle m_k:k\in\Bbb N\rangle$ by setting

$$m_k=k\max_{i\le k}m^{(i)}_k\;,$$

and verify that $\dfrac{m_k}{m^{(i)}_k}\ge k$ for all $k\ge i$, so that $\dfrac{m^{(i)}_k}{m_k}\le\dfrac1k$ for $k\ge i$ and hence

$$\lim_{k\to\infty}\frac{m^{(i)}_k}{m_k}=0$$ for each $i\in\Bbb N$.

In particular, if $H$ were countable, we could find a sequence growing faster than any sequence in $H$, contradicting the hypothesis on $H$.

-

Hint: Use a variant of the Cantor diagonalization argument. Suppose to the contrary that the functions in $H$ can be listed as $h_0,h_1,h_2,\dots$. Obtain a contradiction by modifying the diagonal (by suitable summing) so that it grows faster than anything in $H$.

Remark: There is good reason to think that the diagonalization argument so intimately associated with Cantor was in fact first used by du Bois-Reymond, precisely in this setting of analyzing orders of growth.

-