# What is the order type of monotone functions, $f:\mathbb{N}\rightarrow\mathbb{N}$ modulo asymptotic equivalence? What about computable functions?

I was reading the blog "who can name the bigger number" ( http://www.scottaaronson.com/writings/bignumbers.html ), and it made me curious. Let $f,g:\mathbb{N}\rightarrow\mathbb{N}$ be two monotonicly increasing strictly positive functions. We say that these two functions are asymptotically equivalent if $$\lim_{n \to \infty} \frac{f(n)}{g(n)}= \alpha\in(0,\infty)$$ We will say that $f>g$ if $$\lim_{n \to \infty} \frac{f(n)}{g(n)}=\infty$$ It is quite clear that this is a partial order. What if any thing can be said about this order type?

-
The second limit should be of $n$ and not $\theta$. – Asaf Karagila Aug 22 '12 at 19:04
Please feel free to edit the tags as I am not sure about the one I used. – Baby Dragon Aug 22 '12 at 19:04
Sorry, I did not know the command for limits, so I copied and pasted from another question. – Baby Dragon Aug 22 '12 at 19:05
It is quite clear that it is not a total order. There are lots of incomparable monotone sequences. Consider, for example, $\displaystyle f(n) := \sum_{k\le n, k\text{ even}} k!$ and $\displaystyle g(n) := \sum_{k\le n, k\text{ odd}} k!$. The lower and upper limits of $f(n)/g(n)$ are $0$ and $\infty$, respectively. – Alexander Shamov Aug 22 '12 at 19:11
Why would the order type be equivalent to an ordinal? Ordinals are well order types. If you consider real valued functions then $f_\varepsilon(n)=n^{\varepsilon}$ form a chain of order type $\mathbb R$. – Asaf Karagila Aug 22 '12 at 19:11

Quite a bit can be said about this partial order. Coincidentally, I've been reading about this the last few days, so let me mention some history. The first person to study it was Du Bois-Reymond, in the early 1870s. He was interested in "the boundary between convergence and divergence". His work is not easy to read due to his lack of rigor and propensity to include "philosophical" ideas through his essays. He did prove that if $f_1<f_2<\dots<f$, then there is a $g$ with $f_i<g<f$ for all $i\in\mathbb N$. Similarly for $f_1>f_2>\dots>f$. (Actually, he worked with real-valued functions of a real variable, but there is nothing essential, at least at this level, that is lost if we consider functions with domain (or domain and range) $\mathbb N$.)

His work was not well received, partly because of his lack of rigor. Hardy remarked that "it is generally easier to find new proofs of Du Bois-Reymond's assertions than to satisfy oneself that he has proved them". Also against him was the fact that Cantor attacked his work profusely, perhaps because he wanted the community to accept his own approach to infinity as "the only possible" approach, and Du Bois-Reymond intended to use the partial order to talk about orders of infinite and infinitesimals. (Cantor was particularly opposed to infinitesimals. He talks of "this infinitary cholera bacillus".)

Hardy and others considered certain subcollections of this partial order, the so-called Hardy fields mentioned in another answer being a particular example, as they were interested in collections of functions where the order was total, or a scale was easily identifiable. A scale is a linearly ordered collection of functions that is cofinal, so any other function in the partial order is smaller than one of them. The terminology is still used in set theory.

Hausdorff proved the existence of $(\omega_1,\omega_1^*)$-gaps, and was really the first to consider the structure of the partial order seriously. He actually noticed that there are many ways of defining the order that lead to similar results. For example, $f/g\to\infty$ iff $\ln(f)-\ln(g)\to\infty$, so we may as well consider a fixed strictly increasing, diverging $F$, and set $f>g$ iff $F(f(n))-F(g(n))\to\infty$ as $n\to\infty$. And we may in fact just take $F$ to be the identity, or even simply require that $f(n)>g(n)$ for all but finitely many $n$, which is the way the poset is presented nowadays.

An $(\omega_1,\omega_1^*)$-gap is a collection $(f_\alpha,g_\alpha\mid\alpha<\omega_1)$ of functions in the poset with $f_\alpha<f_\beta<g_\beta<g_\alpha$ whenever $\alpha<\beta$, and such that there is no $f$ in between, that is, no $f$ satisfies $f_\alpha<f<g_\alpha$ for all $\alpha$. The classification of all possible gaps in the poset is much more recent, and uses the assumption of the Proper Forcing Axiom, PFA.

Hausdorff was also interested in questions of homogeneity, whether all "intervals" in the poset where isomorphic, or whether a "similar" poset could be obtained with this additional property.

For more on this history, I recommend

• "The infinite and infinitesimal quantities of du Bois-Reymond and their reception", by Gordon Fisher, Arch. Hist. Exact Sci. 24 (1981), no. 2, 101–163, MR632567.

For more on the mathematics, which, as hinted by the mention of PFA above, involves both purely combinatorial results, and also forcing, you may want to consult

• "Gaps in $\omega^\omega$", by Marion Scheepers, in "Set theory of the reals" (Ramat Gan, 1991), 439–561, Israel Math. Conf. Proc., 6, Bar-Ilan Univ., Ramat Gan, 1993. MR1234288,

and

• "Hausdorff gaps and limits", by Ryszard Frankiewicz, and Paweł Zbierski, Studies in Logic and the Foundations of Mathematics, 132. North-Holland Publishing Co., Amsterdam, 1994. MR1311476.
-
Wow, this is nice. – Baby Dragon Aug 23 '12 at 22:30

If you want useful classes of "orders of growth" that are totally ordered, perhaps you should learn about things like Hardy fields. And even in this case, of course, Asaf's comment applies, and it should not resemble a well-order at all.

-

Suppose that $f < g$ in the definition given, so $\lim_{n \to \infty} \frac{g(n)}{f(n)} = \infty$.

We will define a function $h$ with $f < h < g$. To do so, we first define a sequence $a_k$ such that $a_0 = 0$ and $a_{k+1}$ is the minimal $n > a_k$ such that, for all $m > a_{k+1}$, we have $g(m)/f(m) > 2^{k+1}$. Because $f < g$, the sequence $(a_k)$ is defined for all $k$, and hence by construction $\lim_{k \to \infty} a_k = \infty$.

Now, define $h(n)$ as follows. Given $n$ choose the maximal $k$ such that $n \geq a_k$. Let $h(n) = k\cdot f(n)$. Then $h$ is also monotonic and tends to infinity.

Because $\lim_{k \to \infty}a_k = \infty$, we have $f < h$. Because $\lim_{k \to \infty} 2^kk^{-1} = \infty$, and $f < g$ already, we have $h < g$.

It may seem at first as if this construction is noneffective, because the definition of $(a_k)$ requires looking at an infinite number of values of $g$ and $f$. However, the argument can be made to work effectively, by using a priority construction to approximate the sequence, and if $f$ and $g$ are computable monotonic functions with $f < g$ we can find a computable monotonic $h$ with $f < h < g$.

-
In particular, the set of functions comparable with an arbitrary fixed $f$ will never be an ordinal. – Carl Mummert Aug 22 '12 at 20:03

A very useful observation is that this order has, in some sense, no countable base (excuse me if my wording is not accurate). I mean the following claim:

For any countable set of monotone sequences there exists a single sequence that dominates them all.

To prove this, let ${f_n}$ be a countable set of sequences, and consider, say,

$\displaystyle g(n) := n \sum_{k=1}^n f_k(n)$.

-