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? 

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