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.

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.

share|improve this question
2  
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

2 Answers 2

up vote 4 down vote accepted

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

share|improve this answer

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.

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.